|
在前面已经提到了整数划分的问题，在那个问题中，只需要求出整数划分的个数，如果要求将整数划分的所有划分方法也输出，该如何求解？如对于整数6，输出的结果就应该是： 6 5+1 4+2 4+1+1 3+3 3+2+1 3+1+1 2+2+2 2+2+1+1 2+1+1+1+1 1+1+1+1+1+1 我们可以采用集合的思维去考虑，比如对于整数6，则初始集合相当于{1，1，1，1，1，1} 从1+1+1+1+1+1到2+1+1+1+1实际上就相当于我从左边那一堆{1,1,1,1,1,1}的集合中拿 两个1出来相加然后再把结果放回集合当中得到{2,1,1,1,1}.若这个时候我继续拿集合里面的两个 1相加再放回去就可以得到{2,2,1,1},同理再做同样的处理的话我们会得到{2,2,2}。
而对于第三层,我们可以先从{1,1,1,1,1,1}里面拿三个1,相加之后放回去得到{3,1,1,1},对于 {3,1,1,1}来说,剩下的三个1可以有两种不同的拿的策略 第一种是一次性拿三个1得到{3,3} 第二种是拿两个1得到{3,2,1} 这些正好是3+3, 3+2+1, 3+1+1+1 而从集合里面拿1这样的操作,利用堆栈就可以很容易的实现,我拿几个就弹出几个,然后把结果 压回栈中.但是这样的话并不是很直观,实际上使用两个栈来操作的话效果会更好.现在假设有两 个栈S1和S2.将S1栈全部压入1,S2栈为空.S1栈元素的个数就是我们输入要分解的整数,就像题 目输入的是6,那么S1栈里面就是6个1. 现在我们要做的事情就是从S1栈里面弹出N个1然后相加 把结果压入S2栈中,一直到S1栈空的时候,就将S2栈中的元素作为结果输出.
从前面的分析,我们可以把递归分成两个方面的,一个方面是深度的递归,就是不同层次之间的转变 的递归,另外一方面的递归是广度的递归,把同一层中的大数再分小,直至不能再分.举例子来说就是 6 -> 5+1 -> 4+2 -> 3+3这里是深度递归 3+3 -> 3+2+1 -> 3+1+1+1 这里是广度递归
运用到我们从S1栈弹出的元素来说,那么第一次弹几个元素就代表着深度,而第二次弹出的元素个 数只能是<=第一次弹出的元素的个数.第三次弹出的又要<=第二次弹出的 一直到S1栈空为止.
举例子来说 假设我们输入的是6,即我们要把6拿来分解.S1就应该有6个1 S2开始的时候是空. 1.第一次弹6个1,把6压入S2,这个时候S1空 ->输出6 2.第一次弹5个1,把5压入S2,这时候S1还剩下一个1,S2有一个5. 下一次弹出栈时候我只能弹出 一个1,压入S2,现在S1空 S2内为{1,5} 输出5+1 3.第一次弹4个1,S2{4},这里因为S1剩下的元素个数>1所以会出现不同的弹出的策略(广度递归 分解) ①第二次弹出两个1,S1空 S2{2,4} 输出 4 + 2 ②第二次弹出一个1,第三次弹出一个1, S1空 S2{1,1,4}输出4+1+1 4.第一次弹出三个1, S1{1,1,1} S2{3} 因为S1剩下的元素个数大于1产生不同的弹出策略 ①第二次弹出三个1,S1空 S2{3,3} 输出3+3 ②第二次弹出两个1,S1{1} S2{2,3} ,继续弹出一个1 S1空 S2{1,2,3} 输出 3+2+1 ③第二次弹出一个1,S1{1,1} S2{1,3},弹出一个1 S1{1} S2{1,1,3}, 弹出一个1 S1空 S2{1,1,1,3} ......如此一直到 第一次弹出一个1 S1{1,1,1,1,1,1} S2{1},弹出一个1 S1{1,1,1,1} S2{1,1} 弹出一个 S1{1,1,1} S2{1,1,1} ......最后S1空 S2{1,1,1,1,1,1} 输出1+1+1+1+1+1 #include<stdio.h>
#include<stdlib.h>
void output(int *a,int top2) //输出结果
{
int i;
for(i=0;i<top2-1;i++)
{
printf("%d+",a[i]);
}
printf("%d\n",a[i]);
}
void partion(int top1,int top2,int *a)
{
if(top1==0) //如果s1中已无元素，则划分完毕，输出
{
output(a,top2);
}
else
{
for(int i=top1;i>=1;i--)
{
if(top2==0||i<=a[top2-1])
{
a[top2]=i; //从s1中取出的1的个数压入s2
partion(top1-i,top2+1,a); //对s1中剩下的1再次进行取栈操作
}
}
}
}
int main(void)
{
int top1,top2;
int *a;
while(scanf("%d",&top1)==1&&top1>=0)
{
top2=0;
a=(int *)malloc(top1*sizeof(int));
partion(top1,top2,a);
}
return 0;
}
出处：http://www.cnblogs.com/dolphin0520/
本博客中未标明转载的**归作者Matrix海子和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在**页面明显位置给出原文连接，否则保留追究法律责任的权利。
|
楼主
标题置顶
标题高亮
