0:幾種數學式的定義:
Fibonacci數列:
function Fibonacci(n:integer):integer;
begin
if n<1 then result:=1
else result:=Fibonacci(n-1)+Fibonacci(n-2)
end;
階乘,
function RankMulti(n:integer):integer;
begin
if n<1 then result:=1
else result:=RankMulti(n-1)*n
end;
Ackerman函數:(變態的老外什么都想的出來)
function Ackerman(n,m:integer):integer;
begin
result:=0;
if (n=1) and (m=0) then result:=2
else
if (n=0) and( m>=1) then result:=1
else
if (n>=2) and(m=0) then result:=n+2
else
if (m>=1) and (n>=1) then result:=Ackerman(Ackerman(n-1,m),m-1)
end;
具體的意義我就不羅嗦了，就是個定義而已。涉及到解題思路，就與上面的直接表示略有不同，書上一般都叫作分治法。就是把大問題劃分成n個子問題，再用同樣的方法去解決..這個東西已經被人們講爛了，我在講的話大家要扔磚頭了
遞歸的效率使得人們對他的評價褒貶不一。思路清晰使得性能下降其實也算是某種意義上的平衡。不過如果你去考試的話，一般沒有很便宜的事情讓你用分治法設計一個算法了事。而時間復雜度是必要考慮的，一般情況下要控制在O(n^2)之內.遞歸的時間復雜度可以用遞歸方程式求出來。一般情況下，在你的遞歸式之外的操作時間在O(n)之內的話，可以用遞歸式內的線性長度為底求遞歸次數的對數來估計時間復雜度。
比如:階乘的遞歸式很快，是個線性時間，而Fibonacci數列則是T(n)=T(n-1)+T(n-2)+O(1)的操作，也就是T(n)=2T(n)+O(1),由遞歸方程式可以知道他的復雜度T(n)是O(n^2)
有關復雜性分析可以參考http://algorithm.myrice.com/algorithm/complexity/chapter6.htm
本文用到的是方法3套用公式，其中的=可以改寫為<=或<，對于復雜度分析我們總是考慮最壞情況（有些隨機算法除外），所以不管寫只是個表達方法，本質都是一樣的。
其實對于復雜度了解清楚就不要總害怕他的低效率了，因為它的復雜度也不總是傳說中的指數級。
另外用堆棧改寫是不能降低復雜度。
有些算法是不能用一系列O(1)的算法來迭代改寫的。
下面是幾個分治算法的例子，全部模擬最初的解題思路來遞歸實現，未經優化。作為拋磚引玉。
==========================={CopyRight jinjazz}==========
1.求正整數劃分的個數:求一個正整數劃分為一系列正整數之和有多少不同的劃分方法 比如6有11種
function DivInteger(n:integer):integer;
function DivMax(n,m:integer):integer; //求最大子數不大于m的劃分個數
begin
result:=0;
if (m=1) or (n=1) then result:=1
else
if m>n then result:=DivMax(n,n)
else
if m=n then result:=1+DivMax(n,n-1)
else
if (n>m) and (M>1) then result:=divMax(n,m-1)+DivMax(n-m,m)
end;
begin
result:=DivMax(n,n)
end;
=========================={CopyRight jinjazz}=============
2.求全排列(定義:var PermVar:array[0..4] of Variant; 初始化時可以附任何類型的值)
PRocedure Perm(var JtVariant:array of Variant;k,m:integer;jtList:Tstrings);
var i:integer;
procedure swap(var a,b:Variant);
var tmp:Variant;
begin
tmp:=a;
a:=b;
b:=tmp;
end;
begin
if k<=m then
for i:=k to m do
begin
swap(JtVariant[k],JtVariant[i]);
Perm(JtVariant,k+1,m,JtList);
swap(JtVariant[k],JtVariant[i]);
end
else
begin
jtList.Add('Perm:');
for i:=0 to m do
jtList.Add(JtVariant[i]);
jtList.Add('==================')
end;
end;
//建議針對不同類型相應的將variant替換掉
============================={CopyRight jinjazz}=========
3.漢諾塔(雖然經常見但是有多少人親手寫過?)
procedure hanoi(n:integer;p1,p2,p3:char;JtList:Tstrings); //個數,盤子標志,輸出
procedure move(m:integer;ps,pd:char);
begin
JtList.Add(inttostr(m)+ ' from '+ ps+' to '+pd);
end;
begin
if n>0 then
begin
hanoi(n-1,p1,p3,p2,JtList);
move(n-1,p1,p2);
hanoi(n-1,p3,p2,p1,JtList);
end;
end;
//hanoi(3,'a','b','c',memo1.Lines)
==============================={CopyRight jinjazz}========
4.快速排序法
procedure QuickSort(var SortNum:array of integer;p,r:integer);
procedure swap(var a,b:integer); //交換
var tmp:integer;
begin
tmp:=a;
a:=b;
b:=tmp;
end;
function partition(var SortNum:array of integer;p,r:integer):integer; //劃分
var i,j,x:integer;
begin
i:=p;j:=r+1;
x:=SortNum[p];
while true do
begin
repeat inc(i)
until SortNum[i]<x;
repeat inc(j,-1)
until SortNum[j]>x;
if i>=j then break;
swap(SortNum[i],SortNum[j]);
end;
SortNum[p]:=SortNum[j];
SortNum[j]:=x;
result:=j;
end;
var q:integer;
begin
if p<r then
begin
q:=partition(SortNum,p,r);
QuickSort(SortNum,p,q-1);
QuickSort(SortNum,q+1,r);
end;
end;
=============================={CopyRight jinjazz}==
5.二分查找法.對已排序序列進行查找
function BinarySearch(SearchNum:array of integer;x,n:integer):integer;//序列,值,序列長度
var left,right,mid:integer;
begin
result:=-1;
left:=0;right:=n-1;
while(left<=right)do
begin
mid:=(left+right) div 2;
if x=SearchNum[mid] then
begin
result:=mid;
exit;
end;
if x>SearchNum[mid] then left:=mid+1
else right:=mid-1
end;
end;
=============================={CopyRight jinjazz}=========
6.無限位大整數加法(當然有更簡便的方法,但這只是個分治法解決問題的思路)
function InfiniteAdd(a,b:string):string;
var a1,a2,b1,b2,M,D:string;
i,k:integer;
begin
if length(a)<length(b) then
for i:=1 to length(b)-length(a) do a:='0'+a
else for i:=1 to length(a)-length(b) do b:='0'+b;
if length(a)<=18 then //int64最大19位，保證不溢出
result:=inttostr(strtoint64(a)+strtoint64(b))
else
begin
k:=length(a) div 2;
a1:=copy(a,1,k);a2:=copy(a,k+1,length(a)-k);
b1:=copy(b,1,k);b2:=copy(b,k+1,length(b)-k);
M:=InfiniteAdd(a2,b2);
D:=InfiniteAdd(a1,b1);
if length(M)>length(a2) then
result:=InfiniteAdd(D,'1')+copy(M,2,length(M)-1)
else
begin
if length(M)<length(a2) then
for i:=1 to length(a2)-length(M) do M:='0'+M;
result:=D+M;
end;
end;
end;
============================{CopyRight jinjazz}===============
7.無限位大整數整除2（模擬遞歸過程，沒經過優化）
function InfiniteDiv2(s:string):string; //這是個O(n)的計算 :-)
var i,k,w:integer;
s1,s2,D1,D2:string;
begin
if length(s)<=17 then
begin
result:=inttostr(strtoint64(s)div 2);
end
else
begin
k:=length(s) div 2;
s1:=copy(s,1,k);s2:=copy(s,k+1,length(s)-k);
D1:=InfiniteDiv2(s1);
D2:=InfiniteDiv2(s2);
if length(D2)<k then
for i:=1 to k-length(D2)+1 do D2:='0'+D2;
if byte(s1[length(s1)])mod 2=1 then
D2:=inttostr(strtoint(D2[1])+5)+copy(D2,2,length(D2)-1);
result:=D1+D2;
end;
end;
=========================={CopyRight jinjazz}======
8.無限位數乘法 （模擬遞歸過程，沒經過優化）
function InfiniteMulti(a,b:string):string; //時間復雜度有點高
var a1,a2,b1,b2,U,V,X,Y:string;
i,k:integer;
begin
if length(a)<length(b) then
for i:=1 to length(b)-length(a) do a:='0'+a
else for i:=1 to length(a)-length(b) do b:='0'+b;
//a*b=a1*b1(補0)+a1*b2(補0)+a2*b1（補0）+a2*b2 不能超過9位
if length(a) mod 2=1 then
begin
a:='0'+a;
b:='0'+b;
end;
if length(a)<=9 then //int64最大19位，保證不溢出
result:=inttostr(strtoint64(a)*strtoint64(b))
else
begin
k:=length(a) div 2;
a1:=copy(a,1,k);a2:=copy(a,k+1,length(a)-k);
b1:=copy(b,1,k);b2:=copy(b,k+1,length(b)-k);
U:=InfiniteMulti(a1,b1);
V:=InfiniteMulti(a1,b2);
X:=InfiniteMulti(a2,b1);
Y:=InfiniteMulti(a2,b2);
for i:=1 to k do
begin
U:=U+'00';
V:=V+'0';
X:=X+'0';
end;
result:=InfiniteAdd(U,V);
result:=InfiniteAdd(result,X);
result:=InfiniteAdd(result,Y);
end;
end;
新聞熱點
疑難解答
