对于区间[a,b]上连续不断且f(a)·f(b)<0的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值的方法叫二分法。
简介
一般地,对于函数f(x),如果存在实数c,当x=c是f(c)=0,那么把x=c叫做函数f(x)的零点。
解方程即要求f(x)的所有零点。
先找到a、b,使f(a),f(b)异号,说明在区间(a,b)内一定有零点,然后求f【(a+b)/2】,
现在假设f(a)<0,f(b)>0,a
如果f【(a+b)/2】=0,该点就是零点,
如果f【(a+b)/2】<0,则在区间((a+b)/2,b)内有零点,按上述方法在求该区间中点的函数值,这样就可以不断接近零点
如果f【(a+b)/2】>0,同上
通过每次把f(x)的零点所在小区间收缩一半的方法,使区间的两个端点逐步迫近函数的零点,以求得零点的近似值,这种方法叫做二分法。
由于计算过程的具体运算复杂,但每一步的方式相同,所以可通过编写程序来运算。
例:(C语言)
方程式为:f(x) = 0,示例中f(x) = 1+x-x^3
使用示例:
input a b e: 1 2 1e-5
solution: 1.32472
源码如下:
#include
#include
#include
#include
double f(double x)
{
return 1+x-x*x*x;
}
int main()
{
double a = 0, b = 0, e = 1e-5;
printf("input a b e: ");
scanf("%lf%lf%lf", &a, &b, &e);
e = fabs(e);
if (fabs(f(a)) <= e)
{
printf("solution: %lg\n", a);
}
else if (fabs(f(b)) <= e)
{
printf("solution: %lg\n", b);
}
else if (f(a)*f(b) > 0)
{
printf("f(%lg)*f(%lg) > 0 ! need <= 0 !\n", a, b);
}
else
{
while (fabs(b-a) > e)
{
double c = (a+b)/2.0;
if (f(a)* f ( c ) < 0)
b = c;
else
a = c;
}
printf("solution: %lg\n", (a+b)/2.0);
}
return 0;
}
证明方法
二分法(dichotomie) 即一分为二的方法. 设[a,b]为R的紧区间. 逐次二分法就是造出如下的区间序列([an,bn]):a0=a,b0=b,且对任一自然数n,[an+1,bn+1]或者等于[an,cn],或者等于[cn,bn],其中cn表示[an,bn]的中点
求法
给定精确度ξ,用二分法求函数f(x)零点近似值的步骤如下:
1 确定区间[a,b],验证f(a)·f(b)<0,给定精确度ξ.
2 求区间(a,b)的中点c.
3 计算f(c).
(1) 若f(c)=0,则c就是函数的零点;
(2) 若f(a)·f(c)<0,则令b=c;
(3) 若f(c)·f(b)<0,则令a=c.
(4) 判断是否达到精确度ξ:即若|a-b|<ξ,则得到零点近似值a(或b),否则重复2-4.
计算机应用
由于计算过程的具体运算复杂,但每一步的方式相同,所以可通过编写程序来运算。
Java语言
public int binarySearch(int[] data,int aim){//以int数组为例,aim为需要查找的数
int start = 0;
int end = data.length-1;
int mid = (start+end)/2;//a
while(data[mid]!=aim&&end>start){//如果data[mid]等于aim则死循环,所以排除
if(data[mid]>aim){
end = mid-1;
}else if(data[mid] start = mid+1; } mid = (start+end)/2;//b,注意a,b } return (data[mid]!=aim)?-1:mid;//返回结果 } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 //针对已经排序好的数组进行查找(对上面代码进行的改进) publicstaticbooleanbinarySearch(int[]array,inttarget){ intleft=0; intright=array.length-1; intmid=(left+right)/2; while(array[mid]!=target&&right>left){ if(array[mid]>target){ right=mid+1; } elseif(array[mid] left=mid+1; } mid=(left+right)/2; //判断在缩小范围后,新的left或者right是否会将target排除 if(array[right] break;//若缩小后right比target小,即target不在数组中 } elseif(array[left]>target){ break;//若缩小后left比target大,即target不在数组中 } } return(array[mid]==target); } C语言 方程式为:f(x) = 0,示例中f(x) = 1+x-x^3 使用示例: input a b e: 1 2 1e-5 solution: 1.32472 源码如下: #include #include #include #include double f(double x) { return 1+x-x*x*x; } int main() { double a = 0, b = 0, e = 1e-5; printf("input a b e: "); scanf("%lf%lf%lf", &a, &b, &e); e = fabs(e); if (fabs(f(a)) <= e) { printf("solution: %lg\n", a); } else if (fabs(f(b)) <= e) { printf("solution: %lg\n", b); } else if (f(a)*f(b) > 0) { printf("f(%lg)*f(%lg) > 0 ! need <= 0 !\n", a, b); } else { while (fabs(b-a) > e) { double c = (a+b)/2.0; if (f(a)* f ( c ) < 0) b = c; else a = c; } printf("solution: %lg\n", (a+b)/2.0); } return 0; } C++语言 [类C编写]. |f(x)|<10^-5 f(x)=2x^3-4x^2+3x-6 #include"iostream" #include"stdio.h" #include"math.h" #define null 0 double fx(double); //f(x)函数 void main() { double xa(null),xb(null),xc(null); do { printf("请输入一个范围x0 x1:"); std::cin>>xa>>xb; //输入xa xb的值 printf("%f %f",xa,xb); } while(fx(xa)*fx(xb)>=0); //判断输入范围内是否包含函数值0 do { if(fx((xc=(xa+xb)/2))*fx(xb)<0) //二分法判断函数值包含0的X取值区间 { xa=xc; } else { xb=xc; } } while(fx(xc)>pow(10.0,-5)||fx(xc)<-1*pow(10.0,-5));//判断x根是否在接近函数值0的精确范围内 printf("\n 得数为:%f",xc); } double fx(double x) { return(2.0*pow(x,3)-4.0*pow(x,2)+3*x-6.0); } C++语言中的二分查找法 算法:当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的。 基本思想:假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值等于x,则查找成功;若x小于当前位置值,则在数列的前半段中查找;若x大于当前位置值则在数列的后半段中继续查找 ,直到找到为止。 假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2. 1.开始令front=0(指向3),end=7(指向88),则mid=3(指向36)。因为mid>x,故应在前半段中查找。 2.令新的end=mid-1=2,而front=0不变,则新的mid=1。此时x>mid,故确定应在后半段中查找。 3.令新的front=mid+1=2,而end=2不变,则新的mid=2,此时a[mid]=x,查找成功。 如果要查找的数不是数列中的数,例如x=25,当第三次判断时,x>a[mid],按以上规律,令front=mid+1,即front=3,出现front>end的情况,表示查找不成功。 例:在有序的有N个元素的数组中查找用户输进去的数据x。 算法如下: 1.确定查找范围front=0,end=N-1,计算中项mid(front+end)/2。 2.若a[mid]=x或front>=end,则结束查找;否则,向下继续。 3.若a[mid] 代码: #include #define N 10 using namespace std; int main() { int a[N],front,end,mid,x,i; cout<<"请输入已排好序的a数组元素:"< for(i=0;i cin>>a[i]; cout<<"请输入待查找的数x:"< cin>>x; front=0; end=N-1; mid=(front+end)/2; while(front { if(a[mid] if(a[mid]>x)end=mid-1; mid=front + (end - front)/2; } if(a[mid]!=x) cout<<"没找到!"< else cout<<"找到了!在第"< return 0; } MATLAB语言 function y=f(x) y=f(x); %函数f(t)的表达式 i=0; %二分次数记数 a=a; %求根区间左端 b=b; %求根区间右端 fa=f(a); %计算f(a)的值 fb=f(b); %计算f(b)的值 c=(a+b)/2; %计算区间中点 fc=f(c); %计算区间中点f(c) while abs(fc)>=ε; %判断f(c)是否为零点 if fa*fc>=0; %判断左侧区间是否有根 fa=fc; a=c; else fb=fc; b=c; end c=(a+b)/2; fc=f(c); i=i+1; end fprintf('\n%s%.6f\t%s%d','c,'迭代次数i=',i) %计算结果输出 快速排序伪代码(非随机) 下面的过程实现快速排序: QUICKSORT(A,p,r) 1 ifp 2 thenq ← PARTITION(A,p,r) 3 QUICKSORT(A,p,q-1) 4 QUICKSORT(A,q+1,r) 为排序一个完整的数组A,最初的调用是QUICKSORT(A,1,length[A])。 快速排序算法的关键是PARTITION过程,它对子数组A[p..r]进行就地重排: PARTITION(A,p,r) 1 x ← A[r] 2 i ← p-1 3 forj ← ptor-1 4 do ifA[j]≤x 5 theni ← i+1 6 exchange A[i]←→A[j] 7 exchange A[i+1]←→A[r] 8 returni+1 快速排序伪代码(随机) 对PARTITION和QUICKSORT所作的改动比较小。在新的划分过程中,我们在真正进行划分之前实现交换: (其中PARTITION过程同快速排序伪代码(非随机)) RANDOMIZED-PARTITION(A,p,r) 1 i ← RANDOM(p,r) 2 exchange A[r]←→A[i] 3 return PARTITION(A,p,r) 新的快速排序过程不再调用PARTITION,而是调用RANDOMIZED-PARTITION。 RANDOMIZED-QUICKSORT(A,p,r) 1 ifp 2 thenq ← RANDOMIZED-PARTITION(A,p,r) 3 RANDOMIZED-QUICKSORT(A,p,q-1) 4 RANDOMIZED-QUICKSORT(A,q+1,r) Pascal, 递归快排1 procedure work(l,r: longint); var i,j,tmp: longint; begin if l i:=l;j:=r;tmp:=stone[i]; while i begin while (i if(i begin stone[i]:=stone[j]; inc(i); end; while (i if i begin stone[j]:=stone[i]; dec(j); end; end; stone[i]:=tmp; work(l,i-1); work(i+1,r); end; end;//本段程序中stone是要排序的数组,从小到大排序,stone数组为longint(长整型)类型。在主程序中的调用命令为“work(1,n);”不含引号。表示将stone数组中的1到n号元素进行排序。 Pascal, 递归快排2 Program quiksort; //快速排序法 const max=100; var n:integer; a:array[1..max] of longint; procedure sort(l,r: longint); var i,j,x,y: longint; begin i:=l; j:=r; x:=a[(l+r) div 2]; repeat while a[i] while x if i<=j then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); dec(j); end; until i>j; if l if i end; begin //生成数组; randomize; for n:=1 to max do begin a[n]:=random(1000); write(a[n]:5); end; writeln; //排序 sort(1,max); //输出 for n:=1 to max do write(a[n]:5);writeln; end. Delphi 递归快排3 TNTA=array of integer; var A:TNTA; procedure QuicSort(var Arr:TNTA;AStart,AEnd:Integer); var I,J,Sign:integer; procedure Switch(A,B:Integer); var Tmp:Integer; begin Tmp:=Arr[A]; Arr[A]:=Arr[B]; Arr[B]:=Tmp; end; begin if AEnd<=AStart then Exit; Sign:=(AStart+AEnd)div 2; {Switch value} Switch(Sign,AEnd); {Start to sort} J:=AStart; for I := AStart to AEnd-1 do begin if (Arr[I] begin Switch(J,I); Inc(J); end; end; Switch(J,AENd); QuicSort(Arr,AStart,J); QuicSort(Arr,J+1,AEnd); end; procedure TForm1.btn1Click(Sender: TObject); const LEN=10000; var I: Integer; Start:Cardinal; begin SetLength(A,LEN); Randomize; for I := Low(A) to High(A) do A[I]:=Random(LEN*10); Start:=GetTickCount; QuicSort(A,Low(A),High(A)); ShowMessageFmt('%d large quick sort take time:%d',[LEN,GetTickCount-Start]); end; Pascal, 非递归快排1 var s:packed array[0..100,1..7]of longint; t:boolean; i,j,k,p,l,m,n,r,x,ii,jj,o:longint; a:packed array[1..200000]of longint; function check:boolean; begin if i>2 then exit(false); case i of 1:if (s[k,3] 2:if s[k,1] end; exit(false); end; procedure qs; /非递归快速排序 begin k:=1; t:=true; s[k,1]:=1; s[k,2]:=n; s[k,3]:=1; while k>0 do begin r:=s[k,2]; l:=s[k,1]; ii:=s[k,3]; jj:=s[k,4]; if t then if (r-l>30) then begin x:=a[(r-l+1)shr 1 +l]; ii:=s[k,1];jj:=s[k,2]; repeat while a[ii] while a[jj]>x do dec(jj); if ii<=jj then begin m:=a[ii]; a[ii]:=a[jj]; a[jj]:=m; inc(ii);dec(jj); end; until ii>jj; s[k,3]:=ii; s[k,4]:=jj; end else begin for ii:=l to r do begin m:=a[ii];jj:=ii-1; while (m0) do begin a[jj+1]:=a[jj]; dec(jj); end; a[jj+1]:=m; end; t:=false; dec(k); end; if t then for i:=1 to 3 do if check then break; if not t then begin i:=s[k,5]; repeat inc(i); until (i>2)or check; end; if i>2 then begin t:=false; dec(k);end else t:=true; if t then begin s[k,5]:=i; inc(k); case i of 1:begin s[k,1]:=s[k-1,3];s[k,2]:=s[k-1,2];end; 2:begin s[k,1]:=s[k-1,1];s[k,2]:=s[k-1,4];end; end; end; end; end; begin readln(n); for i:=1 to n do read(a[i]); k:=1; qs; for i:=1 to n do //输出 write(a[i],' '); writeln; end. 经测试,非递归快排比递归快排快。 Pascal, 非递归快排2 //此段快排使用l队列储存待处理范围 var a:Array[1..100000] of longint; l:Array[1..100000,1..2] of longint; n,i:longint; procedure fs;//非递归快排 var s,e,k,j,ms,m:longint; begin s:=1;e:=1;l[1,1]:=1;l[1,2]:=n; while s<=e do begin k:=l[s,1];j:=l[s,2];m:=random(j-k+1)+k; ms:=a[m];a[m]:=a[k]; while k begin while (k if k while (k if k end; a[k]:=ms; if l[s,1] if j+1 inc(s); end; end; begin randomize; read(n); for i:=1 to n do read(a[i]); fs; for i:=1 to n do write(a[i],' '); end. 实战 Problem:大整数开方 NOIP2011普及组初赛完善程序第二题 题目描述 输入一个正整数n(1 代码 Const SIZE = 200; Type hugeint = Record len : Integer; num : Array[1..SIZE] Of Integer; End; //len表示大整数的位数;num[1]表示个位、num[2]表示十位,以此类推 Var s : String; i : Integer; target, left, middle, right : hugeint; Function times(a, b : hugeint) : hugeint; // 计算大整数 a 和 b 的乘积 Var i, j : Integer; ans : hugeint; Begin FillChar(ans, SizeOf(ans), 0); For i := 1 To a.len Do For j := 1 To b.len Do ans.num[i + j - 1] := ans.num[i + j - 1] + a.num[i] * b.num[j]; For i := 1 To a.len + b.len Do Begin ans.num[i + 1] := ans.num[i + 1] + ans.num[i] DIV 10; ans.num[i] := ans.num[i] mod 10; If ans.num[a.len + b.len] > 0 Then ans.len := a.len + b.len Else ans.len := a.len + b.len - 1; End; times := ans; End; Function add(a, b : hugeint) : hugeint; // 计算大整数 a 和 b 的和 Var i : Integer; ans : hugeint; Begin FillChar(ans.num, SizeOf(ans.num), 0); If a.len > b.len Then ans.len := a.len Else ans.len := b.len; For i := 1 To ans.len Do Begin ans.num[i] :=ans.num[i] + a.num[i] + b.num[i]; ans.num[i + 1] := ans.num[i + 1] + ans.num[i] DIV 10; ans.num[i] := ans.num[i] MOD 10; End; If ans.num[ans.len + 1] > 0 Then Inc(ans.len); add := ans; End; Function average(a, b : hugeint) : hugeint; // 计算大整数 a 和 b 的平均数的整数部分 Var i : Integer; ans : hugeint; Begin ans := add(a, b); For i := ans.len DownTo 2 Do Begin ans.num[i - 1] := ans.num[i - 1] + (ans.num[i] mod 2) * 10; ans.num[i] := ans.num[i] DIV 2; End; ans.num[1] := ans.num[1] DIV 2; If ans.num[ans.len] = 0 Then Dec(ans.len); average := ans; End; Function plustwo(a : hugeint) : hugeint; // 计算大整数 a 加 2 后的结果 Var i : Integer; ans : hugeint; Begin ans := a; ans.num[1] := ans.num[1] + 2; i := 1; While (i <= ans.len) AND (ans.num[i] >= 10) Do Begin ans.num[i + 1] := ans.num[i + 1] + ans.num[i] DIV 10; ans.num[i] := ans.num[i] MOD 10; Inc(i); End; If ans.num[ans.len + 1] > 0 Then inc(ans.len); plustwo := ans; End; Function over(a, b : hugeint) : Boolean; // 若大整数 a > b 则返回 1, 否则返回 0 Var i : Integer; Begin If (a.len Begin over := FALSE; Exit; End; If a.len > b.len Then Begin over := TRUE; Exit; End; For i := a.len DownTo 1 Do Begin If a.num[i] < b.num[i] Then Begin over := FALSE; Exit; End; If a.num[i] > b.num[i] Then Begin over := TRUE; Exit; End; End; over := FALSE; End; Begin Readln(s); FillChar(target.num, SizeOf(target.num), 0); target.len := Length(s); For i := 1 To target.len Do target.num[i] := Ord(s[target.len - i + 1]) - ord('0'); FillChar(left.num, SizeOf(left.num), 0); left.len := 1; left.num[1] := 1; right := target; Repeat middle := average(left, right); If over(times(middle, middle), target) Then right := middle Else left := middle; Until over(plustwo(left), right); For i := left.len DownTo 1 Do Write(left.num[i]); Writeln; End. 经济学方面 传统的经济学家把经济分为实物经济和货币经济两部分,其中,经济理论分析实际变量的决定,而货币理论分析价格的决定,两者之间并没有多大的关系,这就是所谓的二分法。 哲学方面 又称二分说,爱利亚学派芝诺四大著名悖论之一 证明运动是不可能的。 其主要思路是:假设一个存在物经过空间而运动,为了穿越某个空间,就必须穿越这个空间的一半。为了穿越这一半,就必须穿越这一半的一半;以此类推,直至无穷。所以,运动是不可能的 一般使用方面 即将所有的事物根据其属性分成两种。错误的分类可能导致逻辑谬论,如:非黑即白,不是忠的就是奸的。这很明显忽略了中间状态的存在。正确的分类法应如:白-非白。