算法04：整數劃分遞歸算法

整數劃分是指将正整數n劃分成若幹整數之和，如3的劃分：1+1+1、1+2、3共三種（1+2和2+1為同一個劃分）

給定一個整數n，求n劃分的個數，通常的做法是引用一個正整數m，q(n,m)表示n的劃分中最大整數不超過m，進而建立遞歸函數

如整數6的劃分：

1.求整數n=6的所有劃分相當于求最大整數不超過6的劃分，m=6即求q（6,6），此時如果m>n和m=n=6的結果一樣，可得出：

   q(n,m)=q(n,n),m≥n 

2.要求q(6,6)，對于最大整數6有兩種情況：（1）6在劃分中；（2）6不在劃分中。（1）隻有一種結果即6；（2）可表示為最大整數不超過5的劃分即q(6,5)，可得出：

   q(n,n)=1+q(n,n-1)

3.要求出q(6,5)，對于最大整數5有兩種情況：（1）5不在劃分中；（2）5在劃分中。（1）為最大整數不超過4的劃分即q(6,4);（2）可表示為5+1，即5加上6減去5的整數的劃分q(1,5)，可得出：

  q(n,m)=q(n,m-1)+q(n-m,m),n>m>1

4.當n=1，隻有一種劃分即1，可得出：

  q(1,m)=1

5.當m=1時，q(6,1)=1+1+1+1+1+1也隻有一種劃分，可得出：

   q(n,1)=1

綜上：q(6,6)=1+q(6,5)=1+q(6,4)+q(1,5)=......,可得到如下遞歸關系：

完整算法如下：

#include <cstdlib>
#include <iostream>

using namespace std;

int split_count(int n, int m)
{
    if(n < 1||m < 1) return 1;  
    
    else if(n == 1||m == 1) return 1;  
    
    else if(n < m) return split_count(n, n);
    
    else if(n == m) return 1+split_count(n, n-1);
    
    else return split_count(n, m-1)+split_count(n-m , m);
} 

int main()
{
    int n;
    while(cin>>n){
          cout<<split_count(n,n)<<endl; 
    }
    system("PAUSE");
    return 0;
}