// 将一个正整数n表示成一系列正整数之和，
// n = n1 + n2 + ... + nk ( 其中， n1 >= n2 >= ... >= nk , k >= 1 )
// 正整数n的一个这种表示称为正整数n的一个划分。
// 正整数n的不同的划分个数称为正整数n的划分数。
// 求划分数
// 将最大数n1不大于m的划分个数记作q(n,m)。
// 递归关系如下:
// 1、q(n,1) = 1 , n >= 1;
// 2、q(n,m) = q(n,n) , m >= n;
// 3、q(n,n) = 1 + q(n,n-1);
// 4、q(n,m) = q(n,m-1) + q(n-m,m) , n > m > 1;
////////////////////////////////////////
#include "iostream.h"
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 );
}
void main()
{
cout<<q(6,6)<<endl;
}
////////////////////////////////////////
////////////////////////////////////////
////////////////////////////////////////
////////////////////////////////////////
////////////////////////////////////////
// 求划分
//
#include "iostream.h"
#include "iomanip.h"
#define max 1024
void print( int *map , int len )
{
static int total = 1;
cout<<"划分"<<setw(4)<<total++<<" : ";
for( int i = 0 ; i < len ; i++ )
cout<<setw(5)<<map[i];
cout<<endl;
}
int p( int n , int m , int *map , int len )
{
if( n >= 1 && m == 1 )
{
// flag1:
// 当 m=1 时，只有一种分法，n = 1 + 1 + ...
// 与 flag2 合作，可以完成这种分解的输出
map[len] = 1;
p( n - 1 , m , map , len+1 );
return 1;
}
else if( n == 0 && m == 1 )
{
// flag2:
// 配合 flag1 ，完成对 m=1 划分的处理
print( map , len );
return 1;
}
else if( n == 1 && m > 1 )
{
// flag3:
// 当 n=1 时，分解已经完成，进行输出处理
map[len] = n;
print( map , len + 1 );
return 1;
}
else if( n < m )
{
// flag4:
// 由于所处位置的关系，此时及以下情况中的 m , n 都 > 1
return p( n , n , map , len );
}
else if( n == m )
{
// flag5:
// 这种情况下，map 位赋为 m，则可完成一种划分
map[len] = m;
print( map , len + 1 );
// 继续下种情况的处理
return p( n , m - 1 , map , len ) + 1;
}
else
{
// 有两种处理方法
// 方法一：
// 当前 map 位赋为 m , 处理 p( n-m , m )
map[len] = m;
int s1 = p( n - m , m , map , len + 1 );
// 方法二：
int s2 = p( n , m - 1 , map , len );
return s1 + s2;
}
}
void main()
{
int map[max] = { 0 };
int len = 0;
cout<<"total="<<p( 6 , 6 , map , len )<<endl;
}
// 程序2是程序1的扩充，基本思想与程序1相似，在理解程序1的基础上，
// 可以很好得理解程序2
////////////////////////////////////////
// 参考文献:
// 计算机算法设计与分析 电子工业出版社
