如何用計算工具實施二分法

Ⅰ C語言中何為二分法，如何使用

（二分法。就是將方程的有根取間對分,然後在選擇比原區間縮小一半的有根區間,一直這樣繼續下去,直到得到滿足精度要求的根。二分法計算過程簡單,程序容易實現.可在大范圍內求根,但該方法收斂較慢,且不能求偶數重根和復根,一般用於求根的。。。）（筆記） SB，我筆記不是借你看過的嘛。。。

Ⅱ 藉助計算器或計算機，用二分法求方程

方程有問題，但程序如下應該是對的：
#include<stdio.h>
#include<math.h>
float f(float x)
{
float y;
y=pow(0.8,x)-1-log(x);//自定義方程
return(y);
}
float xpoint(float x1,float x2)
{
float y;
y=(x1*f(x2)-x2*f(x1))/(f(x2)-f(x1));//求 x軸點 交點坐標
return(y);
}
float root(float x1,float x2)
{
float x,y,y1;
y1=f(x1);
do
{
x=xpoint(x1,x2);
y=f(x);
if(y*y1>0)
{
y1=y;
x1=x;
}
else x2=x;
}
while(fabs(y)>=1e-1);
return(x);
}
void main(){
float x1,x2,f1,f2,x;
do
{
printf("請輸入方程解得范圍x1,x2(注意中間用逗號隔開):\n");
scanf("%f,%f",&x1,&x2);
f1=f(x1);
f2=f(x2);
}
while(f1*f2>=0);
x=root(x1,x2);
printf("A root of equation is %.1f\n",x);
}

Ⅲ 二分法的計算機應用

由於計算過程的具體運算復雜，但每一步的方式相同，所以可通過編寫程序來運算。
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;//返回結果
} //針對已經排序好的數組進行查找（對上面代碼進行的改進）(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>doublef(doublex){return1+x-x*x*x;}intmain(){doublea=0,b=0,e=1e-5;printf(inputabe:);scanf(%lf%lf%lf,&a,&b,&e);e=fabs(e);if(fabs(f(a))<=e){printf(solution:%lg ,a);}elseif(fabs(f(b))<=e){printf(solution:%lg ,b);}elseif(f(a)*f(b)>0){printf(f(%lg)*f(%lg)>0!need<=0! ,a,b);}else{while(fabs(b-a)>e){doublec=(a+b)/2.0;if(f(a)*f(c)<0)b=c;elsea=c;}printf(solution:%lg ,(a+b)/2.0);}return0;}C++語言
[類C編寫].
|f(x)|<10^-5 f(x)=2x^3-4x^2+3x-6 #include<iostream>#include<cmath>usingnamespacestd;doublef(doublex);constdoubleAccu=pow(10.0,-5.0);//defineaccuracyintmain(){doublea,b,c;a=b=c=0;do{cout<<Enterarange:;cin>>a>>b;}while(!cin||f(a)*f(b)>=0);//badinputorf(a)*f(b)>=0do{c=(a+b)/2.0;//cistheaveragenumberofaandbif(f(a)*f(c)<0)b=c;elseif(f(b)*f(c)<0)a=c;elsebreak;}while(f(c)<Accu);//ifdeviationissmallerthanpow(10.0,-5.0)cout<<Solution:<<c;return0;}doublef(doublex){return(2*x*x*x-4*x*x+3*x-6);//or2*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(' %s%.6f %s%d','c,'迭代次數i=',i) %計算結果輸出
快速排序偽代碼（非隨機）
下面的過程實現快速排序：
QUICKSORT(A，p，r)
1ifp<r
2thenq ← PARTITION(A，p，r)
3QUICKSORT(A，p，q-1)
4QUICKSORT(A，q+1，r)
為排序一個完整的數組A，最初的調用是QUICKSORT(A，1，length[A])。
快速排序演算法的關鍵是PARTITION過程，它對子數組A[p..r]進行就地重排：
PARTITION(A，p，r)
1x ← A[r]
2i ← p-1
3forj ← ptor-1
4do ifA[j]≤x
5theni ← i+1
6exchange A[i]←→A[j]
7exchange A[i+1]←→A[r]
8returni+1
快速排序偽代碼（隨機）
對PARTITION和QUICKSORT所作的改動比較小。在新的劃分過程中，我們在真正進行劃分之前實現交換：
（其中PARTITION過程同快速排序偽代碼（非隨機））
RANDOMIZED-PARTITION(A，p，r)
1i ← RANDOM(p，r)
2exchange A[r]←→A[i]
3return PARTITION(A，p，r)
新的快速排序過程不再調用PARTITION，而是調用RANDOMIZED-PARTITION。
RANDOMIZED-QUICKSORT(A，p，r)
1ifp<r
2thenq ← RANDOMIZED-PARTITION(A，p，r)
3RANDOMIZED-QUICKSORT(A，p，q-1)
4RANDOMIZED-QUICKSORT(A，q+1，r)
Pascal，遞歸快排1
procere 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;
procere 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;
procere QuicSort(var Arr:TNTA;AStart,AEnd:Integer);
var
I,J,Sign:integer;
procere 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;
procere 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;
procere 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;
procere 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)，試用二分法計算它的平方根的整數部分。
代碼
ConstSIZE = 200;
Typehugeint = Recordlen : Integer;num : Array[1..SIZE] Of Integer;End; //len表示大整數的位數;num[1]表示個位、num[2]表示十位,以此類推
Vars : String;i : Integer;target, left, middle, right : hugeint;
Function times(a, b : hugeint) : hugeint; // 計算大整數 a 和 b 的乘積Vari, j : Integer;ans : hugeint; BeginFillChar(ans, SizeOf(ans), 0);For i := 1 To a.len DoFor j := 1 To b.len Doans.num[i + j - 1] := ans.num[i + j - 1] + a.num[i] * b.num[j];For i := 1 To a.len + b.len DoBeginans.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] > 0Then ans.len := a.len + b.lenElse ans.len := a.len + b.len - 1;End;times := ans; End;
Function add(a, b : hugeint) : hugeint; // 計算大整數 a 和 b 的和Vari : Integer;ans : hugeint; BeginFillChar(ans.num, SizeOf(ans.num), 0);If a.len > b.lenThen ans.len := a.lenElse ans.len := b.len;For i := 1 To ans.len DoBeginans.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] > 0Then Inc(ans.len);add := ans;End;
Function average(a, b : hugeint) : hugeint; // 計算大整數 a 和 b 的平均數的整數部分Vari : Integer;ans : hugeint; Beginans := add(a, b);For i := ans.len DownTo 2 DoBeginans.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] = 0Then Dec(ans.len);average := ans; End;
Function plustwo(a : hugeint) : hugeint; // 計算大整數 a 加 2 後的結果Vari : Integer;ans : hugeint; Beginans := a;ans.num[1] := ans.num[1] + 2;i := 1;While (i <= ans.len) AND (ans.num[i] >= 10) DoBeginans.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] > 0Then inc(ans.len);plustwo := ans; End;
Function over(a, b : hugeint) : Boolean; // 若大整數 a > b 則返回 1, 否則返回 0Vari : Integer; BeginIf (a.len<b.len) ThenBeginover := FALSE;Exit;End;If a.len > b.len ThenBeginover := TRUE;Exit;End;For i := a.len DownTo 1 DoBeginIf a.num[i] < b.num[i] ThenBeginover := FALSE;Exit;End;If a.num[i] > b.num[i] ThenBeginover := TRUE;Exit;End;End;over := FALSE; End;
BeginReadln(s);FillChar(target.num, SizeOf(target.num), 0);target.len := Length(s);For i := 1 To target.len Dotarget.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;Repeatmiddle := average(left, right);If over(times(middle, middle), target)Then right := middleElse left := middle;Until over(plustwo(left), right);For i := left.len DownTo 1 DoWrite(left.num[i]);Writeln;End.

Ⅳ 怎樣用計算器，是···計算器！來用二分法求函數零點急求！！！急急急！！

你好！

舉例說明如下

f(x)=e^x + x -2
顯然f(x)是增函數，故最多有一個零點。
∵f(0)= -2<0，f(1) = e-1>0
∴零點在(0,1)內

取(0,1)中點0.5
f(0.5)=0.1487>0
∴零點在(0，0.5)

取中點0.25，f(0.25)= -0.4660 <0
∴零點在(0.25，0.5)

取中點0.375，f(0.375)= - 0.1700 <0
∴零點在(0.375，0.5)

取中點0.4375，f(0.4375)= - 0.01367 <0
∴零點在(0.4375，0.5)

取中點0.46875，f(0.46875)= 0.06675 >0
∴零點在(0.4375，0.46875)

如此反復，直到達到你想要的精確度。

Ⅳ 二分法的演算法步驟是什麼

在有序的有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。

(5)如何用計算工具實施二分法擴展閱讀

基本思想：假設數據是按升序排序的，對於給定值key，從序列的中間位置k開始比較，

如果當前位置arr[k]值等於key，則查找成功；

若key小於當前位置值arr[k]，則在數列的前半段中查找，arr[low，mid-1]；

若key大於當前位置值arr[k]，則在數列的後半段中繼續查找arr[mid+1，high]，

直到找到為止，時間復雜度:O(log(n))。

Ⅵ 二分法的計算方法和步驟

我把書上原文給你打出來，挺好理解的！我們已經知道，函數F(x)=lnx+2x-6在區間(2,3)內有零點，進一步的問題是，如何找出這個零點？
一個直觀的想法是：如果能夠將零點所在的范圍盡量縮小，那麼在一定精確度下，我們可以得到零點的近似值。為了方便，用「取中點」地方法逐步縮小零點所在的范圍。
取區間（2,3）的中點2.5，用計算器算的f(2.5)約等於 －0.084。因為F(2.5)f(2.75)＜0，所以零點在區間(2.5,2075)內
所以零點所在的范圍就縮小了。我們可以在有限次重復相同步驟後，將所得的零點所在區間內的任意一點作為函數零點的近似值，特別的，可將區間斷電作為零點的近似值。
對於在區間[a,b]上連續不斷且f(a)f(b)＜0的函數y=f(x),通過不斷地把函數f(x)的零點所在的區間一分為二，將區間的兩個端點逐漸逼近零點，進而得到零點近似值地方法叫二分法。

Ⅶ 二分法 計算步驟

對於在區間[，]上連續不斷且滿足·＜0的函數，通過不斷地把函數的零點所在的區間一分為二，使區間的兩個端點逐步逼近零點，進而得到零點近似值的方法叫做二分法(bisection)．

2.給定精確度，用二分法求函數零點近似值的步驟如下：

(1)確定區間，，驗證·＜0，給定精確度；

(2)求區間，的中點；

(3)計算：

1若=，則就是函數的零點；

2若·＜0，則令=（此時零點）；

3若·＜0，則令=（此時零點）；

(4)判斷是否達到精確度；即若＜，則得到零點近似值（或）；否則重復步驟2-4．