快好知 kuaihz订阅看过栏目

 

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

代码:

#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 (istone[i])do inc(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]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]

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 (kms) do dec(j);

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.

经济学方面

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

哲学方面

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

一般使用方面

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

投稿
非常不爽,删了吧! 相关词条:文化 语言文字 词语 函数 实数 零点 方程 区间 假设 端点 逻辑 正确