recursive

recursive(遞迴)
簡潔易懂,但效率差,適合描述演算法
可分為以下3種:
direct recursion:直接呼叫自己
indirect recursion:先呼叫其它程序若干層後,最後又呼叫回自己
tail recursion:在最後一個命令又呼叫自己本身(由於尾端遞迴的返回位址是程式的結束指令,即時返回也不需進行處理)
若把此改掉,可以不需要儲存返回位址與程式狀態,而能夠提昇執行效率

遞迴函數=基本元素+建立其他新元素所需規則
遞迴演算法=遞迴關係+終止條件(需有一條路徑不再進行遞迴呼叫)
(若無法到達終止條件會造成無窮迴窮)

分析遞迴複雜度的工具:
遞迴樹:用樹狀結構表示遞迴的呼叫情況
遞迴關係式=用關係式表示呼叫遞迴的關係

當遞迴關係式可表示成為:
T(n)=aT(n/b)+cn^k,a與b=整數常數,c與k為正常數,a>=1,b>=2,在比較a,b^k大小關係,可以得到:
T(n)={
 O(n^logb(a)),if a< b^k

 O(n^k log n),if a=b^k
 O(n^k),if a< b^k 

removal of recursion 遞迴轉成非遞迴
1堆疊法:indirect recursion和direct recursion處理稍有不同
2folding(折疊法)

.................

fibonacci(費氏數列) O(2^n)
遞回迴關係式:t(n){0,if n=0; 1,if n=1; t(n-1)+t(n-2)+c,otherwise
推導過程:t(n-1)+t(n-2)+c=t(t(n-2)+t(n-3)+c)+t(t(n-3)+t(n-4)+c)+c=...2^(n-1)*t(1)+(2^(n-1)-1)*c
所以t(n)=(2^n-1)*c > big O(2^n)
int fibonacci(int n){
 if(n=0)return (0);
 else if(n=1)return (1);
 else return(fibonacci(n-1)+fibonacci(n-2));
}
int fibonacci(int n){
 int fib_n,fib_n_1,fib_n_2;
 if(n==0)return(0);
 else if(n==1)return(1);
 else{
  fib_n_2=0;fib_n_1=1;
  for(i=2;i<=n;i++){
   fib_n=fib_n_1+fib_n_2; fib_n_1=fib_n_2; fib_n_2=fib_n;
  }
 return(fib_n);
 }
}

hanoi(河內塔問題) O(2^n)
遞迴關係式:T(n){
2T(n-1)+c ,n>=2 where c屬於constant(遞迴關係)
c ,n=1 where c屬於constant(終止條件)
推導...
ps:搬動n個套環需2^n-1次

bin_search(二元搜尋),O(2底log n)
遞迴關係式:T(n)={
T(n/2)+c ,n>=2 where c屬於constant(遞迴關係)
c , n=1 where c屬於constant(終止條件)

最大/最小問題,O(n)
遞迴關係式:T(n)={
2T(n/2)+c ,n>=2 where c屬於constant(遞迴關係)
c , n=1 where c屬於constant(終止條件)

選擇問題 O(n^2)

矩陣乘法問題 O(n^3)
遞迴關係式,推導...

volker strassen O(n^2.81)
遞迴關係式,推導...

...

//找總數
int findsum(int n){ //1+2+...n
 if(n==1)return(1); //終止條件
 else return(findsum(n-1)+n); //遞迴條件
}
int findsum(int n){
 int result,i;
 for(i=n;i>1;i++){result+=i;}
 return result;
}

//找最大,尚未測試
int findmax(int a[],int max,int i){ //find(a,1,陣列元素);
 if(i==0){return max}
 else{
  if(max < a[i] )max=a[i];
  findmax(a,max,i-1);
 }
}

//找最大公因數
int findgcd(int x,int y){
 return((y==0)?x:findgcd(y,x%y))
}
int findgcd(int x,y){
 if(y==0)return(x);
 else return(findgcd(y,x%y));
}
int findgcd(int x,y){
int remainder=x%y;
 while(remainder!=0){
  x=y;y=remainder;
  remainder=x%y;
 }
 return(y);
}

找一字串的所有排列
void permutation(char list[],int i,int n){
 int j,temp;
 if(i==n){ printf("%s",list);}
 else{
  for(j=i;j<=n;j++){
   swap(list[i],list[j],temp);
   permutation(list,i+1,n);
   swap(list[i],list[j],temp);
  }
 }
}
t(n)={c ,if n=1; n*t(n-1)+c*n ,if n>=2;
t(n)=n*t(n-1)+c*n=n*t((n-1)*t((n-1)-1)+c*(n-1))+c*n=(n*(n-1))*t(n-2)+c*(n+(n-1))=.....=O(n!)

ackermann
......


2007-03-05 18:56:12發表 2014-04-22 23:20:47修改   

數據分析
程式開發
計算機組織與結構
資料結構與演算法

Database and MySql
manage tool
windows
unix-like
linux service
network
network layer3
network layer2
network WAN
network service
作業系統
數位鑑識
資訊安全解決方案
資訊安全威脅
Cisco security
Cisco network
Cisco layer3
Cisco layer2



  登入      [牛的大腦] | [單字我朋友] Powered by systw.net