算法笔记之 整数划分

		例如：6 有如下11种划分则p(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;
在正整数n所有划分中，将最大加数n1不大于m的划分个数记作q(n, m).
我们可以建立如下递归关系:
(1) q(n, 1) = 1, n>=1
最大加数不大于1,则只有一种划分，n=1+1+1+...+1
(2) q(n, m) = q(n, n), m>=n
最大加数n1实际上不能大于n.因此q(1, m)=1
(3) q(n, n) = 1 + q(n, n-1)
正整数n的划分有n1=n的划分和n1<n-1的划分组成
(4) 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)的递归函数如下.显然p(n)=q(n,n)
 
 
int q(int n, int m)
{
    if((n<1) || (m<1))  return 0;
    if((n==1)|| (m==1)) return 1;
    if(n<m)             returnq(n, n);
    if(n==m)            return(q(n, m-1)+1);
    if(n>m)             return(q(n,m-1) + q(n-m, m));
}
 
为求n的所有划分,需要在上面求n的划分数的过程中将划分元素保存起来并输出.
 
[cpp]  
#include <iostream>  
using namespace std;  
  
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,n);  
    if(n==m)  
        return q(n, m-1) + 1;  
    return q(n,m-1) + q(n-m,m);  
//  return 0;  
}  
  
  
  
int main() {  
    //cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!  
    cout << q(10,10);  
    return 0;  
}  
 
						
		
	

补充：软件开发 , C++ ,

上一个：进制转换 （九度oj--大整数除法）
下一个：Internet选项 添加信任站点