整数划分问题c语言编程
dnf徽章获得-家长对孩子的评语
整数划分问题
问题：将以正整数n表示成一系列正整数之和.n=n1+n2+n3+...+nk
(其中
n1>=n2>=n3>=nk>=1,
k>=1)这就是正整数n的一个划分，正整数n不同的划分
个数称为正整数n的划分数,
记作p(n)
分析：在正整数n的所有不同的划分中,将最大加数n1不大于m的的划分个数
记为q(n,m),可以建立如下递归关系
1、 q(n,1)=1,n>=1;
当最大加
数n1不大于1的时候，任何正整数只有一种划分，即n=1+1+1+…+1，
其中有n个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的一种还有最大划分小于等于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的划分组成
递归式为:
1;
(n=1 or m=1)
q(n,
n); (n
q(n, m)=
1+ q(n, n-1);
q(n,m-1)+q(n-m,m);
伪代码:
q(n,m)*求解整数n的划分数*
{
if(n<1||m<1)
return 0;
if(n==1||m==1)
return 1;
else
if(n
else
if(n==m)
(n=m)
(n>m)
return 1+q(n,n-1);
else
return
q(n,m-1)+q(n-m,m);
}
整数n的具体划分伪代码
start:
input：n
part:
{
int i,j;
for(i=x;i>=1;i--)
if(i+total<=n)
{
a[t++]=i;
total+=i;
goto part;
}
if(total==n) print:
{
count++;
print(n=a[0]+a[1]+...+a[t-1])
if (a[k]中，k != t-1)
print(
else
print(
if(a[1]==a[2]==a[3]==...a[t-1]==1)
print(
}
}
t=t-1
total=total-a[t];
}
程序代码如下：
#include
#define N 100
int
a[N];
int t=0;t作为数组a[]的下标
int total=0;
int count=0;划分数的计数器
void
part(int x,int n)
{
int i,j;
for(i=x;i>=1;i--)
if(i+total<=n)
{
a[t++]=i; 将n的划分由大到小给数组a[]
total+=i;total的值逐渐向n靠拢，当n==total时就是打印的时候
part(i,n); 递归调用，直到满足n==total
}
if(total==n)等式两边n=total时打印
{
count++; 计数，每打印一次增1，最终结果即为划分数
printf(打印等式左边的n及=
for(j=0;j
printf(依次输出a[0],a[1],a[2].....
if(j
{
if(a[1]==1||a[0]==n)
printf(唯有n=n或者a[1]为1，即除a[0]以外都
为1的情况，进行下一行输出
else printf(同行等式间分割号
}
}
}
t--;回到上一步t值
total-=a[t];回到上一步total值
}
void main()
{
int n;
printf(输入是n:
scanf(
part(n,n);
将n划分成若干正整数之和的划分数。
printf(将%d划分成若干正整数之和的划分数:%dnn
}
程序运行如下: