這個周末家裡有點事，回了趟家，就斷了一些學習計劃。。
抓緊補上！
第一個算法——遞歸與分治
都知道，分治算法基本思想是
將一個難以直接解決的問題，分割成一些規模小的相同問題，以便各個擊破，分而治之，
這樣，我們就可以將一個復雜的算法，類型不變，規模越來越小，最終使子問題容易求解，由此引出遞歸算法。
其實，分治和遞歸像一對孿生兄弟，經常可以同時使用在算法設計之中，並由此產生許多高效的算法。
一、遞歸
概念：直接或間接的調用自身的算法稱為遞歸算法，用函數自身給出定義的函數稱為遞歸函數。
下面列出幾個遞歸的經典例子：
① 階乘
定義：
n！等於 1 當n=0
等於n（n-1）！ 當n>0
int factorial(int n)
{
if( n == 0 ) return 1;
return n*factorial(n-1);
}
一個無窮的數列，序列為：1,1,2,3,5,8,13,21,34,55....
定義為：
F（n）= 1 當n=0
=1 當n=1
=F（n-1）+F（n-2） 當n>1
int fibonacci(int n)
{
if( n <= 1 ) return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
③Ackerman函數
這是一個雙遞歸函數，當一個函數及它的一個變量由函數自身定義時，稱這個函數為雙遞歸函數。
Ackerman函數A（n，m） 有兩個獨立的整型變量m≥0，n≥0，其定義如下：
A（1,0） = 2 m≥0
A（0,m） = 1 n≥2
A（n,0） = n+2 n≥2
A（n,m） = A（A（n-1，m），m-1） n,m≥1
int Ackerman( int n , int m )
{
if( n==1 && m==0 ) return 2;
if( n==0 ) return 1;
if( m==0 ) return n+2;
return Ackerman( Ackerman(n-1,m),m-1);
}
④排列問題
對n個元素進行全排列，
當n=1時，Perm（P）=（r），其中r是集合R中唯一的元素
當n>1時，Perm（P）由（r1）Perm（R1），（r2）Perm（R2），.......，（rn）Perm（Rn）構成
template< class Type >
inline void Swap(Type& a,Type& b)
{
Type temp = a;
a = b;
b = temp;
}
void Perm(Type list[],int k ,int m )
{
if( k==m )
{
for( int i = 0 ; i <= m; ++i ) cout<
⑤整數劃分問題將正整數n表示成一系列正整數之和，
n=n1+n2+...+nk（其中n1≥n2≥n3≥....≥nk）
例如，對於整數6的劃分：
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
總共11種劃分
按照最大加數n1不大於m的劃分個數記作q（n,m），可以建立如下遞歸關系：
<1> q(n,1) = 1 , n≥1—— 當最大加數n1不大於1時，任何正整數n只有一種劃分形式
<2> q(n,m)=q(n,n),n≥m—— 最大加數n1實際上不能大於n。因此q(1,m)=1
<3> q(n,m)=q(n,m-1)+q(n-m,m),n>m>1—— 正整數n的最大加數n1不大於m的劃分由n1=m的和n1≤m-1的劃分組成。
綜上所述，可以總結出：
q(n,m)=
1 n=1,m=1
q(n,n) n
1+q(n,n-1) n=m
q(n,m-1)+q(n-m,m)
n>m>1
int q( int n , int m )
{
if( (n<1) || (m<1) ) return 0;
if( (n==1) || (m==1) ) return 1;
if( n==m ) return q(n,m-1)+1;
return q(n,m-1)+q(n-m,m);
}
⑥Hanoi塔問題
非常經典的一個遞歸問題，問題就不贅述了，直接寫算法：
void hanoi( int n , int a , int b , int c )
{
if( n > 0 ){
hanoi( n-1,a,c,b);
move(a,b);
hanoi( n-1,c,b,a);
}
}
二、分治
之前也說過，分治法的基本思想就是，把一個規模大的問題，不斷分成相互獨立且與原問題相同的小規模問題。
它的算法設計模式如下：
divide-and-conquer(P)
{
if( |P| <= n0 ) adhoc(P);
divide P into smaller subinstances P1,P2,P3,...,Pk;
for( i = 1 ; i <= k ; ++i )
yi = divide-and-conquer(Pi);
return merge(y1,y2,...,yk);
}
這其中
|P| 表示問題P的規模，
n0 為一阙值，表示當前問題P的規模不超過n0時，問題容易求解，不必再繼續分解。
adhoc(P) 是該分治法中的基本子算法，對於容易求解的問題可以直接求解
merge(y1,y2...yk) 是合並子算法，用於將P的子問題P1，P2，...，Pk的解y1,y2,...,yk合並為P的解
分治法的計算效率通常用遞歸方程來分析，對於上述設計模式，解|P|=n的問題所需的計算時間，有：
T(n) = O(1) 當n=1
kT（n/m）+f（n） 當n>1
以上就是遞歸和分治的一些基本思想和原則，接下來的博文會有具體例子來說明。
***************************************轉載請注明出處：http://blog.csdn.net/lttree********************************************
