算法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;
}