#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}
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.
