零点二分法使用的条件 二分法 二分法-简介,二分法-使用示例

二分法所属现代词,指的是数学领域的概念,经常用于计算机中的查找过程中。数学方面牛顿二分法 一般地,对于函数f(x),如果存在实数c,当x=c时,若f(c)=0,那么把x=c叫做函数f(x)的零点。解方程即要求f(x)的所有零点。假定f(x)在区间(x,y)上连续先找到a、b属于区间(x,y),使f(a),f(b)异号,说明在区间(a,b)内一定有零点,然后求f[(a+b)/2], 现在假设f(a)<0,f(b)>0,a。

二分法_二分法 -简介

一般地,对于函数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<b

如果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 <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: %lgn", a);

}

else if (fabs(f(b)) <= e)

{

printf("solution: %lgn", 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: %lgn", (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语言


publicintbinarySearch(int[]data,intaim){//以int数组为例,aim为需要查找的数

intstart=0;

intend=data.length-1;

intmid=(start+end)/2;//a

while(data[mid]!=aim&&end>start){//如果data[mid]等于aim则死循环,所以排除

if(data[mid]>aim){

end=mid-1;

}elseif(data[mid]<aim){

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]<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

使用示例:

inputabe:121e-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:%lgn",a);

}

elseif(fabs(f(b))<=e)

{

printf("solution:%lgn",b);

}

elseif(f(a)*f(b)>0)

{

printf("f(%lg)*f(%lg)>0!need<=0!n",a,b);

}

else

{

while(fabs(b-a)>e)

{

doublec=(a+b)/2.0;

if(f(a)*f(c)<0)

b=c;

else

a=c;

}

printf("solution:%lgn",(a+b)/2.0);

}

return0;

}

C++语言


[类C编写].

|f(x)|<10^-5f(x)=2x^3-4x^2+3x-6

#include"iostream"

#include"stdio.h"

#include"math.h"

#definenull0

doublefx(double);//f(x)函数

voidmain()

{

doublexa(null),xb(null),xc(null);

do

{

printf("请输入一个范围x0x1:");

std::cin>>xa>>xb;//输入xaxb的值

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);

}

doublefx(doublex)

{

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]<x,说明待查找的元素值只可能在比中项元素大的范围内,则把mid+1的值赋给front,并重新计算mid,转去执行步骤2;若a[mid]>x,说明待查找的元素值只可能在比中项元素小的范围内,则把mid-1的值赋给end,并重新计算mid,转去执行步骤2。

代码:

#include<iostream>

#defineN10

usingnamespacestd;

intmain()

{

inta[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;

return0;

}

MATLAB语言


functiony=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)

whileabs(fc)>=ε;%判断f(c)是否为零点

iffa*fc>=0;%判断左侧区间是否有根

fa=fc;

a=c;

elsefb=fc;

b=c;

end

c=(a+b)/2;

fc=f(c);

i=i+1;

end

fprintf('n%s%.6ft%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

4doifA[j]≤x

5theni←i+1

6exchangeA[i]←→A[j]

7exchangeA[i+1]←→A[r]

8returni+1

快速排序伪代码(随机)

对PARTITION和QUICKSORT所作的改动比较小。在新的划分过程中,我们在真正进行划分之前实现交换:

(其中PARTITION过程同快速排序伪代码(非随机))

RANDOMIZED-PARTITION(A,p,r)

1i←RANDOM(p,r)

2exchangeA[r]←→A[i]

3returnPARTITION(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



procedurework(l,r:longint);

vari,j,tmp:longint;

begin

ifl<rthenbegin

i:=l;j:=r;tmp:=stone[i];

whilei<jdo

begin

while(i<j)and(tmp<stone[j])dodec(j);

if(i<j)then

begin

stone[i]:=stone[j];

inc(i);

end;

while(i<j)and(tmp>stone[i])doinc(i);

ifi<jthen

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


Programquiksort;

//快速排序法

constmax=100;

varn:integer;

a:array[1..max]oflongint;

proceduresort(l,r:longint);

vari,j,x,y:longint;

begin

i:=l;j:=r;x:=a[(l+r)div2];

repeat

whilea[i]<xdoinc(i);

whilex<a[j]dodec(j);

ifi<=jthen

begin

y:=a[i];a[i]:=a[j];a[j]:=y;

inc(i);dec(j);

end;

untili>j;

ifl<jthensort(l,j);

ifi<rthensort(i,r);

end;

begin

//生成数组;

randomize;

forn:=1tomaxdo

begin

a[n]:=random(1000);

write(a[n]:5);

end;

writeln;

//排序

sort(1,max);

//输出

forn:=1tomaxdowrite(a[n]:5);writeln;

end.

Delphi

递归快排3


TNTA=arrayofinteger;

var

A:TNTA;

procedureQuicSort(varArr:TNTA;AStart,AEnd:Integer);

var

I,J,Sign:integer;

procedureSwitch(A,B:Integer);

var

Tmp:Integer;

begin

Tmp:=Arr[A];

Arr[A]:=Arr[B];

Arr[B]:=Tmp;

end;

begin

ifAEnd<=AStartthen

Exit;

Sign:=(AStart+AEnd)div2;

{Switchvalue}

Switch(Sign,AEnd);

{Starttosort}

J:=AStart;

forI:=AStarttoAEnd-1do

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;

procedureTForm1.btn1Click(Sender:TObject);

const

LEN=10000;

var

I:Integer;

Start:Cardinal;

begin

SetLength(A,LEN);

Randomize;

forI:=Low(A)toHigh(A)do

A[I]:=Random(LEN*10);

Start:=GetTickCount;

QuicSort(A,Low(A),High(A));

ShowMessageFmt('%dlargequicksorttaketime:%d',[LEN,GetTickCount-Start]);

end;

Pascal,非递归快排1


var

s:packedarray[0..100,1..7]oflongint;

t:boolean;

i,j,k,p,l,m,n,r,x,ii,jj,o:longint;

a:packedarray[1..200000]oflongint;

functioncheck:boolean;

begin

ifi>2thenexit(false);

caseiof

1:if(s[k,3]<s[k,2])thenexit(true);

2:ifs[k,1]<s[k,4]thenexit(true);

end;

exit(false);

end;

procedureqs;/非递归快速排序
begin

k:=1;

t:=true;

s[k,1]:=1;

s[k,2]:=n;

s[k,3]:=1;

whilek>0do

begin

r:=s[k,2];

l:=s[k,1];

ii:=s[k,3];

jj:=s[k,4];

iftthen

if(r-l>30)then

begin

x:=a[(r-l+1)shr1+l];

ii:=s[k,1];jj:=s[k,2];

repeat

whilea[ii]<xdoinc(ii);

whilea[jj]>xdodec(jj);

ifii<=jjthen

begin

m:=a[ii];

a[ii]:=a[jj];

a[jj]:=m;

inc(ii);dec(jj);

end;

untilii>jj;

s[k,3]:=ii;

s[k,4]:=jj;

end

elsebegin

forii:=ltordo

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;

iftthen

fori:=1to3do

ifcheckthenbreak;

ifnottthen

begin

i:=s[k,5];

repeat

inc(i);

until(i>2)orcheck;

end;

ifi>2thenbegint:=false;dec(k);end

elset:=true;

iftthen

begin

s[k,5]:=i;

inc(k);

caseiof

1:begins[k,1]:=s[k-1,3];s[k,2]:=s[k-1,2];end;

2:begins[k,1]:=s[k-1,1];s[k,2]:=s[k-1,4];end;

end;

end;

end;

end;

begin

readln(n);

fori:=1tondoread(a[i]);

k:=1;

qs;

fori:=1tondo//输出

write(a[i],'');

writeln;

end.

经测试,非递归快排比递归快排快。

Pascal,

非递归快排2


//此段快排使用l队列储存待处理范围

var

a:Array[1..100000]oflongint;

l:Array[1..100000,1..2]oflongint;

n,i:longint;

procedurefs;//非递归快排
var

s,e,k,j,ms,m:longint;

begin

s:=1;e:=1;l[1,1]:=1;l[1,2]:=n;

whiles<=edo

begin

k:=l[s,1];j:=l[s,2];m:=random(j-k+1)+k;

ms:=a[m];a[m]:=a[k];

whilek<jdo

begin

while(k<j)and(a[j]>ms)dodec(j);

ifk<jthenbegina[k]:=a[j];inc(k);end;

while(k<j)and(a[k]<ms)doinc(k);

ifk<jthenbegina[j]:=a[k];dec(j);end;

end;

a[k]:=ms;

ifl[s,1]<k-1thenbegininc(e);l[e,1]:=l[s,1];l[e,2]:=k-1;end;

ifj+1<l[s,2]thenbegininc(e);l[e,1]:=j+1;l[e,2]:=l[s,2];end;

inc(s);

end;

end;

begin

randomize;

read(n);

fori:=1tondoread(a[i]);

fs;

fori:=1tondowrite(a[i],'');

end.

二分法_二分法 -实战


Problem:大整数开方NOIP2011普及组初赛完善程序第二题

题目描述

输入一个正整数n(1<n<10^100),试用二分法计算它的平方根的整数部分。

代码

Const
SIZE=200;

Type
hugeint=Record
len:Integer;
num:Array[1..SIZE]OfInteger;
End;
//len表示大整数的位数;num[1]表示个位、num[2]表示十位,以此类推

Var
s:String;
i:Integer;
target,left,middle,right:hugeint;

Functiontimes(a,b:hugeint):hugeint;
//计算大整数a和b的乘积
Var
i,j:Integer;
ans:hugeint;
Begin
FillChar(ans,SizeOf(ans),0);
Fori:=1Toa.lenDo
Forj:=1Tob.lenDo
ans.num[i+j-1]:=ans.num[i+j-1]+a.num[i]*b.num[j];
Fori:=1Toa.len+b.lenDo
Begin
ans.num[i+1]:=ans.num[i+1]+ans.num[i]DIV10;
ans.num[i]:=ans.num[i]mod10;
Ifans.num[a.len+b.len]>0
Thenans.len:=a.len+b.len
Elseans.len:=a.len+b.len-1;
End;
times:=ans;
End;

Functionadd(a,b:hugeint):hugeint;
//计算大整数a和b的和
Var
i:Integer;
ans:hugeint;
Begin
FillChar(ans.num,SizeOf(ans.num),0);
Ifa.len>b.len
Thenans.len:=a.len
Elseans.len:=b.len;
Fori:=1Toans.lenDo
Begin
ans.num[i]:=ans.num[i]+a.num[i]+b.num[i];
ans.num[i+1]:=ans.num[i+1]+ans.num[i]DIV10;
ans.num[i]:=ans.num[i]MOD10;
End;
Ifans.num[ans.len+1]>0
ThenInc(ans.len);
add:=ans;
End;

Functionaverage(a,b:hugeint):hugeint;
//计算大整数a和b的平均数的整数部分
Var
i:Integer;
ans:hugeint;
Begin
ans:=add(a,b);
Fori:=ans.lenDownTo2Do
Begin
ans.num[i-1]:=ans.num[i-1]+(ans.num[i]mod2)*10;
ans.num[i]:=ans.num[i]DIV2;
End;
ans.num[1]:=ans.num[1]DIV2;
Ifans.num[ans.len]=0
ThenDec(ans.len);
average:=ans;
End;

Functionplustwo(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]DIV10;
ans.num[i]:=ans.num[i]MOD10;
Inc(i);
End;
Ifans.num[ans.len+1]>0
Theninc(ans.len);
plustwo:=ans;
End;

Functionover(a,b:hugeint):Boolean;
//若大整数a>b则返回1,否则返回0
Var
i:Integer;
Begin
If(a.len<b.len)Then
Begin
over:=FALSE;
Exit;
End;
Ifa.len>b.lenThen
Begin
over:=TRUE;
Exit;
End;
Fori:=a.lenDownTo1Do
Begin
Ifa.num[i]<b.num[i]Then
Begin
over:=FALSE;
Exit;
End;
Ifa.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);
Fori:=1Totarget.lenDo
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);
Ifover(times(middle,middle),target)
Thenright:=middle
Elseleft:=middle;
Untilover(plustwo(left),right);
Fori:=left.lenDownTo1Do
Write(left.num[i]);
Writeln;
End.

二分法_二分法 -经济学方面

零点二分法使用的条件 二分法 二分法-简介,二分法-使用示例
传统的经济学家把经济分为实物经济和货币经济两部分,其中,经济理论分析实际变量的决定,而货币理论分析价格的决定,两者之间并没有多大的关系,这就是所谓的二分法。

二分法_二分法 -哲学方面

又称二分说,爱利亚学派芝诺四大著名悖论之一证明运动是不可能的。其主要思路是:假设一个存在物经过空间而运动,为了穿越某个空间,就必须穿越这个空间的一半。为了穿越这一半,就必须穿越这一半的一半;以此类推,直至无穷。所以,运动是不可能的

二分法_二分法 -一般使用方面

即将所有的事物根据其属性分成两种。错误的分类可能导致逻辑谬论,如:非黑即白,不是忠的就是奸的。这很明显忽略了中间状态的存在。正确的分类法应如:白-非白。

  

爱华网本文地址 » http://www.413yy.cn/a/8103420103/92537.html

更多阅读

信用卡办理的条件及流程 信用卡办理的注意事项

信用卡办理的条件及流程——简介信用卡,现在已经越来越多的被人们使用,但是怎么样才能拥有一张自己的信用卡呢?下面我把我所了解到的办卡流程分享给大家,希望大家能够受用。信用卡办理的条件及流程——方法/步骤信用卡办理的条件及流程

《Word97吴氏打印简谱法》的快捷应用 拳皇97快捷键

《Word97吴氏打印简谱法》的快捷应用不用“打谱软件”只用Word就能打印出歌谱无疑给广大音乐爱好者开辟了新天地。经过几年的使用和积累,使用复制、粘贴、模板应用等手法,使打谱的速度和质量有了显著的提高。一、简谱的基本组成就是

声明:《零点二分法使用的条件 二分法 二分法-简介,二分法-使用示例》为网友西红柿小生分享!如侵犯到您的合法权益请联系我们删除