二分法(數學領域術語)

二分法(數學領域術語)

本詞條是多義詞,共2個義項
更多義項 ▼ 收起列表 ▲

對於區間[a,b]上連續不斷且f(a)·f(b)<0的函式y=f(x),通過不斷地把函式f(x)的零點所在的區間一分為二,使區間的兩個端點逐步逼近零點,進而得到零點近似值的方法叫二分法。

基本介紹

  • 中文名:二分法
  • 外文名:Bisection method
  • 概念:一分為二的方法
定義,典型算法,求法,計算機套用,

定義

二分法(Bisection method) 即一分為二的方法. 設[a,b]為R的閉區間. 逐次二分法就是造出如下的區間序列([an,bn]):a0=a,b0=b,且對任一自然數n,[an+1,bn+1]或者等於[an,cn],或者等於[cn,bn],其中cn表示[an,bn]的中點.

典型算法

算法:當數據量很大適宜採用該方法。採用二分法查找時,數據需是排好序的。
基本思想:假設數據是按升序排序的,對於給定值key,從序列的中間位置k開始比較,
如果當前位置arr[k]值等於key,則查找成功;
若key小於當前位置值arr[k],則在數列的前半段中查找,arr[low,mid-1];
若key大於當前位置值arr[k],則在數列的後半段中繼續查找arr[mid+1,high],
直到找到為止,時間複雜度:O(log(n))。

求法

給定精確度ξ,用二分法求函式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]<aim){
start = mid+1;
}
mid = (start+end)/2;//b,注意a,b
}
return (data[mid]!=aim)?-1:mid;//返回結果
}
//針對已經排序好的數組進行查找(對上面代碼進行的改進)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]<target){left=mid+1;}mid=(left+right)/2;//判斷在縮小範圍後,新的left或者right是否會將target排除if(array[right]<target){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 <stdio.h>#include <stdlib.h>#include <math.h>#include <assert.h>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 <cmath>using namespace std;double f(double x);const double Accu = pow(10.0, -5.0); // define accuracyint main(){double a, b, c;a = b = c = 0;do{cout << "Enter a range: ";cin >> a >> b;} while (!cin || f(a) * f(b) >= 0); // bad input or f(a) * f(b) >= 0do{c = (a + b) / 2.0; // c is the average number of a and bif (f(a) * f(c) < 0)b = c;else if (f(b) * f(c) < 0)a = c;elsebreak;} while ( abs(f(c)) > Accu); // if deviation is smaller than pow(10.0, -5.0)cout << "Solution: " << c;return 0;}double f(double x){    return (2 * x * x * x - 4 * x * x + 3 * x - 6); // or 2 * pow(x, 3.0) - 4 * pow(x, 2.0) + 3 * x - 6}
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]<x,說明待查找的元素值只可能在比中項元素大的範圍內,則把mid+1的值賦給front,並重新計算mid,轉去執行步驟2;若a[mid]>x,說明待查找的元素值只可能在比中項元素小的範圍內,則把mid-1的值賦給end,並重新計算mid,轉去執行步驟2。
代碼:
#include<iostream>
#define N 10
using namespace std;
int main()
{
int a[N],front,end,mid,x,i;
cout<<"請輸入已排好序的a數組元素:"<<endl;
for(i=0;i<N;i++)
cin>>a[i];
cout<<"請輸入待查找的數x:"<<endl;
cin>>x;
front=0;
end=N-1;
mid=(front+end)/2;
while(front<end&&a[mid]!=x)
{
if(a[mid]<x)front=mid+1;
if(a[mid]>x)end=mid-1;
mid=front + (end - front)/2;
}
if(a[mid]!=x)
cout<<"沒找到!"<<endl;
else
cout<<"找到了!在第"<<mid+1<<"項里。"<<endl;
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(Apr)
1 ifp<r
2 thenq ← PARTITION(Apr)
3 QUICKSORT(Apq-1)
4 QUICKSORT(Aq+1,r)
為排序一個完整的數組A,最初的調用是QUICKSORT(A1length[A])。
快速排序算法的關鍵是PARTITION過程,它對子數組A[p..r]進行就地重排:
PARTITION(Apr)
1 x A[r]
2 i p-1
3 forj ptor-1
4 do ifA[j]≤x
5 thenii+1
6 exchange A[i]←→A[j]
7 exchange A[i+1]←→A[r]
8 returni+1
快速排序偽代碼(隨機)
對PARTITION和QUICKSORT所作的改動比較小。在新的劃分過程中,我們在真正進行劃分之前實現交換:
(其中PARTITION過程同快速排序偽代碼(非隨機)
RANDOMIZED-PARTITION(Apr)
1 i ← RANDOM(pr)
2 exchange A[r]←→A[i]
3 return PARTITION(Apr)
新的快速排序過程不再調用PARTITION,而是調用RANDOMIZED-PARTITION。
RANDOMIZED-QUICKSORT(Apr)
1 ifp<r
2 thenq ← RANDOMIZED-PARTITION(Apr)
3 RANDOMIZED-QUICKSORT(Apq-1)
4 RANDOMIZED-QUICKSORT(Aq+1,r)
Pascal,遞歸快排1
procedure work(l,r: longint);
var i,j,tmp: longint;
begin
if l<r then begin
i:=l;j:=r;tmp:=stone[i];
while i<j do
begin
while (i<j)and(tmp<stone[j])do dec(j);
if(i<j) then
begin
stone[i]:=stone[j];
inc(i);
end;
while (i<j)and(tmp>stone[i])do inc(i);
if i<j then
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]<x do inc(i);
while x<a[j] do dec(j);
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<j then sort(l,j);
if i<r then sort(i,r);
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
type
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]<Arr[AEnd]){ and (I<>J)} then
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]<s[k,2]) then exit(true);
2:if s[k,1]<s[k,4] then exit(true);
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]<x do inc(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 (m<a[jj])and(jj>0) 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<j do
begin
while (k<j)and(a[j]>ms) do dec(j);
if k<j then begin a[k]:=a[j];inc(k);end;
while (k<j)and(a[k]<ms) do inc(k);
if k<j then begin a[j]:=a[k];dec(j);end;
end;
a[k]:=ms;
if l[s,1]<k-1 then begin inc(e);l[e,1]:=l[s,1];l[e,2]:=k-1;end;
if j+1<l[s,2] then begin inc(e);l[e,1]:=j+1;l[e,2]:=l[s,2];end;
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<n<10^100),試用二分法計算它的平方根的整數部分。
代碼
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<b.len) Then
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.

熱門詞條

聯絡我們