整数划分问题C语言编程

整数划分问题问题：将以正整数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个12、q(n,m)=q(n,n),m=n;最大加数n1实际上不能大于n。特殊的，q(1,m)=13、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),nm1；正整数n的最大加数n1不大于m的划分由n1=m的划分和n1=m-1的划分组成递归式为:1;(n=1orm=1)q(n,n);(nm)q(n,m)=1+q(n,n-1);(n=m)q(n,m-1)+q(n-m,m);(nm)伪代码:q(n,m)/*求解整数n的划分数*/{if(n1||m1)return0;if(n==1||m==1)return1;elseif(nm)returnq(n,n);elseif(n==m)return1+q(n,n-1);elsereturnq(n,m-1)+q(n-m,m);}整数n的具体划分伪代码start:input：npart:{inti,j;for(i=x;i=1;i--)if(i+total=n){a[t++]=i;total+=i;gotopart;}if(total==n)print:{count++;print(n=a[0]+a[1]+...+a[t-1])if(a[k]中，k!=t-1)print(+);elseprint();if(a[1]==a[2]==a[3]==...a[t-1]==1)print(\n);}}t=t-1total=total-a[t];}程序代码如下：#includestdio.h#defineN100inta[N];intt=0;//t作为数组a[]的下标inttotal=0;intcount=0;//划分数的计数器voidpart(intx,intn){inti,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(%d=,n);//打印等式左边的n及=for(j=0;jt;j++){printf(%d,a[j]);//依次输出a[0],a[1],a[2].....if(jt-1)printf(+);//如果a[j]不是最后一个加数，那么打印+号else{if(a[1]==1||a[0]==n)printf(\n);//唯有n=n或者a[1]为1，即除a[0]以外都为1的情况，进行下一行输出elseprintf();//同行等式间分割号}}}t--;//回到上一步t值total-=a[t];//回到上一步total值}voidmain(){intn;printf(输入是n:);scanf(%d,&n);part(n,n);//将n划分成若干正整数之和的划分数。printf(将%d划分成若干正整数之和的划分数:%d\n\n,n,count);}程序运行如下: