算法設(shè)計(jì)與分析之循環(huán)與遞歸

前言：

    循環(huán)與遞歸可以說(shuō)是算法設(shè)計(jì)中最基本但卻也是最重要的工具方法。循環(huán)和遞歸對(duì)于學(xué)習(xí)過(guò)高級(jí)程序設(shè)計(jì)語(yǔ)言的人來(lái)說(shuō)都并不陌生，但還是有必要仔細(xì)的探究一下循環(huán)和遞歸之間的相似和區(qū)別。循環(huán)與遞歸最大的相似之處莫不是在于他們?cè)谒惴ㄔO(shè)計(jì)中的工具作用，它們都起到了“以不變應(yīng)萬(wàn)變”的作用。“不變應(yīng)萬(wàn)變”不正是程序設(shè)計(jì)的核心內(nèi)容嗎？正因?yàn)槿绱?，更有必要探究一下這兩種不同的設(shè)計(jì)工具的區(qū)別。本文先從利用循環(huán)和遞歸工具設(shè)計(jì)算法時(shí)的設(shè)計(jì)要點(diǎn)來(lái)認(rèn)識(shí)循環(huán)和遞歸，然后再給出幾個(gè)具體的實(shí)例來(lái)說(shuō)明循環(huán)和遞歸的差異和優(yōu)劣。

1.循環(huán)設(shè)計(jì)要點(diǎn)

    循環(huán)設(shè)計(jì)的要點(diǎn)可以概括為三個(gè)部分：效率、正向思維、具體到抽象。下面以不同的具體實(shí)例來(lái)討論這三個(gè)要點(diǎn)。

1.1效率

    例1.1 求1/1!-1/3!+1/5!-1/7!+....+(-1)^(n+1)/(2n-1)!

    算法1：使用二重循環(huán)實(shí)現(xiàn)，循環(huán)不變式為：s(n)=s(n-1)+(-1)^(n+1)/(2n-1)!。這樣的算法的時(shí)間復(fù)雜度為O(n^2)。針對(duì)本題有沒(méi)有時(shí)間復(fù)雜度為O(n)的算法呢？

    算法2：循環(huán)不變式：s(n)=s(n-1)+(-1)^(n+1)A(n); A(n)=A(n-1)*1/((2*n-2)*(2*n-1))。這個(gè)算法的時(shí)間復(fù)雜度為O(n)。其C++代碼實(shí)現(xiàn)如下：   

#include <iostream>
using namespace std;

int main(void){
 int n;
 cout<<"Please input a number:"<<endl;
 cin>>n;
 float sum=1; //存儲(chǔ)結(jié)果
 float t=1;// 存儲(chǔ)階乘
 int sign=1; //存儲(chǔ)負(fù)號(hào)

 //循環(huán)
 for(int i=2; i<=n; i++){
  sign=-sign;
  t=t*(2*i-2)*(2*i-1);
  sum+=sign/t;
 }
 cout<<"Result is: "<<sum<<endl; 
}

1.2正向思維

    正向思維的方法是從全局到局部、從概略到詳細(xì)的設(shè)計(jì)方法。是對(duì)一個(gè)問(wèn)題由整體到分解和細(xì)化的方法。這也是循環(huán)設(shè)計(jì)的一般方法。下面求完數(shù)的例子可以說(shuō)明正向思維設(shè)計(jì)要點(diǎn)的過(guò)程。

    例1.2  一個(gè)數(shù)如果恰好等于它的因子之和（包括1但不包括這個(gè)數(shù)本身），這個(gè)數(shù)就成為完數(shù)。

    1）頂層算法

        for（i=1; i<=n; i++){

            判斷i是否為完數(shù)；

            是完數(shù)，輸出；

        }

    2）判斷i是否為完數(shù)的算法

        for(j=2; j<i; j++)

            計(jì)算i的因子，并累加；

            如果累加的值為i，輸出i；

    3）進(jìn)一步細(xì)化判斷i是否為完數(shù)的算法

        s=1;

        for(j=2; j<i; j++){

            if(i mod j ==0)

                s += j;

        }

        if(s==i)

            輸出i；

1.3具體到抽象

    具體到抽象的方法也可以說(shuō)成是數(shù)學(xué)歸納法。數(shù)學(xué)歸納法可以說(shuō)是算法設(shè)計(jì)中非常重要的一種方法。算法設(shè)計(jì)的本質(zhì)，可以說(shuō)就是在看似雜亂無(wú)章的信息中總結(jié)歸納出一種不變的規(guī)律，以不變應(yīng)萬(wàn)變。下面的這個(gè)打印規(guī)則圖形的例子可以說(shuō)明這點(diǎn)。

    例1.3  打印具有下圖規(guī)律的圖形

        1

        5     2

        8     6    3

        10   9    7    4

算法C++實(shí)現(xiàn)如下：

#include<iostream>
#define N 10
using namespace std;
int main(void){
 int a[N+1][N+1];
 int k=1;
 for(int i=1; i<=N; i++)
  for(int j=1; j<=N+1-i; j++)
   a[i+j-1][j]=k++;

 for(int i=1; i<=N;i++){
  for(int j=1; j<=i; j++)
   cout<<a[i][j]<<" "; 
  cout<<endl; 
 }  
} 

2.遞歸設(shè)計(jì)要點(diǎn)

    遞歸設(shè)計(jì)方法，也可以叫做逆向思維方法（對(duì)比與循環(huán)設(shè)計(jì)的正向思維）。遞歸設(shè)計(jì)通常有以下三個(gè)步驟：

    （1）尋找遞歸關(guān)系：找出大規(guī)模問(wèn)題于小規(guī)模問(wèn)題的關(guān)系，這樣通過(guò)遞歸是問(wèn)題的規(guī)模逐漸變小。

    （2）找出遞歸停止的條件，即算法可解的最小規(guī)模問(wèn)題。

    （3）設(shè)計(jì)函數(shù)，確定函數(shù)所需參數(shù)。

    下面給出一個(gè)整數(shù)劃分問(wèn)題的遞歸算法設(shè)計(jì)：

    列2.1  求一個(gè)整數(shù)劃分的種類(lèi)數(shù)。列如6有11種劃分如下：

        6

        5+1

        4+2                    4+1+1

        3+3                    3+2+1                    3+1+1+1

        2+2+2                2+2+1+1                2+1+1+1+1

        1+1+1+1+1+1+1

算法描述及C++實(shí)現(xiàn)：

/*
*定義一個(gè)函數(shù)Q(n,m)表示整數(shù)n的任何加數(shù)都不超過(guò)m的劃分?jǐn)?shù)目
*n的所有劃分?jǐn)?shù)目P(n)就應(yīng)該表示為Q(n,n).
*
*一般Q(n,m)有如下遞歸關(guān)系：
*Q(n,n)=1+Q(n,n-1);
*Q(n,m)=Q(n,m-1)+Q(n-m,m)
*右邊第一部分表示不包含m的劃分，第二部分表示包含m的劃分
*那么就意味著剩下的部分就是對(duì)n-m進(jìn)行不超過(guò)m的劃分。
*
*遞歸的停止條件：
*Q(n,1)=1,表示當(dāng)最大的被加數(shù)是1時(shí)，該整數(shù)n只有一種劃分
*Q(1,m)=1,表示整數(shù)1只有一個(gè)劃分，不管最大被加數(shù)的上限
*是多少。
*
*算法的穩(wěn)健性：
*如果n<m,則Q(n,m)是無(wú)意義的，此時(shí)Q(n,m)=Q(n,n)
*同樣的當(dāng)n<1或m<1時(shí)，Q(n,m)也是無(wú)意義的。 
*/

#include<iostream>
using namespace std;

int Divinteger(int n, int m){

 if( n<1||m<1 )//錯(cuò)誤條件 
  cout<<"Error input!"<<endl;

 else if( n==1||m==1 )//停止條件 
  return 1;

 else if( n<m )//穩(wěn)健條件 
  return Divinteger(n, n);

 else if( n==m )// Q(n,n)=1+Q(n,n-1)
  return (1+Divinteger(n, n-1)); 

 else //Q(n,m)=Q(n,m-1)+Q(n-m,m)
  return (Divinteger(n, m-1)+Divinteger(n-m, m));
} 

int main(void){
 int n;
 cout<<"Please input a number:"<<endl;
 cin>>n;
 cout<<"Result is: "<<Divinteger(n,n)<<endl;
}

3.循環(huán)與遞歸的比較

    這個(gè)部分以不同的例子引出三個(gè)結(jié)論。

3.1結(jié)論1：在具體實(shí)現(xiàn)時(shí)，方便的情況下應(yīng)該把遞歸算法轉(zhuǎn)化成等價(jià)的循環(huán)結(jié)構(gòu)算法，以提高算法的時(shí)空效率。

    例3.1 將一個(gè)十進(jìn)制整數(shù)由低位到高位按位輸出。

/*
* 將一個(gè)十進(jìn)制整數(shù)從低位到高位逐位輸出 
* 循環(huán)不僅在時(shí)間而且在空間效率均高于遞
* 歸程序。 
*/

void for_low_to_high(int n){
 while(n){
  cout<<n%M<<" ";
  n=n/M;
 }
 cout<<endl;
}

void f_ltoh(int n){
 if(n<M)
  cout<<n<<endl;
 else{
  cout<<n%M<<" ";
  f_ltoh(n/M);
 }
}

    例3.2 將一個(gè)十進(jìn)制整數(shù)由高位到低位按位輸出。

/*
* 將一個(gè)十進(jìn)制整數(shù)從高位到低位逐位輸出 
* 循環(huán)與遞歸空間效率一樣，雖然時(shí)間效率
* 有差異，但遞歸程序間單可讀性好。 
*/ 

void for_high_to_low(int n){

 int i=0;int a[16];
 while(n){
  a[i]= n%M;
  n=n/M;
  i++;
 }
 for(int j=i-1; j>=0; j--)
  cout<<a[j]<<" ";
 cout<<endl;

} 

void f_htol(int n){
 if(n<M)
  cout<<n<<" ";
 else{
  f_htol(n/M);
  cout<<n%M<<" ";
 }
}
3.2結(jié)論2：當(dāng)問(wèn)題需要后進(jìn)先出的操作時(shí)，還是遞歸算法更有效 。如樹(shù)的遍歷和圖的深度優(yōu)先算法等都是如此。所以不能僅僅從效率上評(píng)價(jià)兩種控制重復(fù)操作機(jī)制的好壞。

    例3.3 用2的冪次方表示一個(gè)正整數(shù)。例如：137=2^7+2^3+2^0,則137可表示為： 2(7)+2(3)+2(0),進(jìn)一步：7=2^2+2+2^0,3=2+2^0 所以137可表示為：2(2(2)+2+2(0))+2(2+2(0))+2(0) 。

算法的C++實(shí)現(xiàn)：

#include<iostream>
using namespace std;

void tryf(int n, int r=0){//n為數(shù)，r為深度 
 if(n==1)//遞歸結(jié)束條件 
  cout<<"2("<<r<<")";
 else{//n除以2,深度加1 
  tryf(n/2,r+1);
  if(n%2==1)//如果余數(shù)不為0輸出2的r冪次 
   cout<<"+2("<<r<<")";
 }
}

void tryff(int n, int r=0){
 if(n==1){
  switch(r){
   case 0:cout<<"2(0)";break;
   case 1:cout<<"2";break;
   case 2:cout<<"2(2)";break;
   default:{cout<<"2(";tryff(r, 0);cout<<")";}
  }
 }else{
  tryff(n/2, r+1);
  if(n%2==1){
   switch(r){
    case 0:cout<<"+2(0)";break;
    case 1:cout<<"+2";break;
    case 2:cout<<"+2(2)";break;
    default:{cout<<"+2(";tryff(r, 0);cout<<")";}
   }//switch
  }//if 
 }//else
}

int main(void){
 int n;
 cout<<"Please input a number:"<<endl;
 cin>>n;
 if(n>1){
  tryf(n);
  cout<<endl;
  tryff(n);
 }else
  cout<<"Inupt Error!"<<endl;
} 

3.3結(jié)論3：遞歸是一種強(qiáng)有力的算法設(shè)計(jì)工具。遞歸是一種比循環(huán)更強(qiáng)、更好用的實(shí)現(xiàn)重復(fù)操作的機(jī)制。因?yàn)檫f歸不需要編程者自己構(gòu)造循環(huán)不變式，而只需找出遞歸關(guān)系和最小問(wèn)題的解。遞歸在很多算法策略中得以運(yùn)用，如分治策略、動(dòng)態(tài)規(guī)劃、圖的搜索等算法策略。

    由下面的例子可以看出遞歸的層次可以控制的，而循環(huán)嵌套的層次只能是固定的。

    例3.4 找出n個(gè)自然數(shù)（1,2,3,4,5,.....,n)中取r個(gè)數(shù)的組合。

算法C++實(shí)現(xiàn)：

#include <iostream>
#define N 5
#define R 3 
using namespace std;

void for_fun1(){
 int t=0;
 for(int i=1; i<=N; i++)
  for(int j=1; j<=N; j++)
   for(int k=1; k<=N; k++)
    if( (i<j) && (j<k) ){
     t++;
     cout<<i<<" "<<j<<" "<<k<<endl; 
    }
 cout<<"Total= "<<t<<endl;
}

//more efficiency
void for_fun2(){
 int t=0;
 for(int i=1; i<=N-R+1; i++)
  for(int j=i+1; j<=N-R+2; j++)
   for(int k=j+1; k<=N-R+3; k++){
    t++;
    cout<<i<<" "<<j<<" "<<k<<endl;
   }
}

//recruisive 
int a[100];
int t=0;
void comb(int n, int r){
 for(int i=n; i>=r; i--){//循環(huán)n-r+1次 
  a[r]=i;//n中選r個(gè)數(shù)，確定第一個(gè)數(shù) 
  if(r>1){//遞歸深度為r 
   comb(i-1,r-1);
  }
  else{//結(jié)束條件為深度r等于1 
   for(int j=a[0]; j>0; j--)
     cout<<a[j]<<" ";
    cout<<endl;
    t++;
  }
 }
} //算法復(fù)雜度O(n*r)
void rec_fun(){
 a[0]=R;
 comb(N,R);
 cout<<"Total= "<<t<<endl;
} 

int main(void){
 for_fun1();
 for_fun2();
 rec_fun();
}

    最后對(duì)遞歸說(shuō)明一點(diǎn)，遞歸可以說(shuō)是一種算法策略，也可以說(shuō)是一種算法設(shè)計(jì)的工具，不管從哪一方面來(lái)看對(duì)算法設(shè)計(jì)都是很好的幫助。遞歸在很多算法策略中得以運(yùn)用，如分治策略、動(dòng)態(tài)規(guī)劃、圖的搜索等算法策略。有很多數(shù)據(jù)結(jié)構(gòu)都是具有遞歸定義的，如鏈表，隊(duì)列，棧，二叉樹(shù)。