输出整数划分表达式

输出整数划分表达式

###基本思路 我们假设有两个栈，top1指向具有n(n就是要划分的整数)个元素，且元素全为1的栈顶。top2刚开始时指向空栈，然后top1中元素不断出栈，进入top2。 用划分整数7举例，开始时top1指向具有7个元素，且元素全为1的栈顶top1=7。top2刚开始时指向空栈，top2=0。

1 现在top1中元素出栈，第一次出栈7个元素，此时top2将top1中出栈元素个数记下，也就是top2中有一个元素7。当top1再次出栈时发现top1中已经没有元素，此时调用Output函数将top2中的元素从栈底一个一个输出(就是由大到小输出，后面讲)，出栈为7

2 这次top1第一次出栈6个元素，top2将top1中出栈元素个数记下，top2中有一个元素6。top1再次出栈时发现top1中只有一个元素，我们将最后一个元素出栈，top2中多了一个元素1，此时top1=0，top2=2。当top1=0时，调用Output函数将top2中的元素从栈底一个一个输出，出栈为6、1

3操作同上，出栈为5、2 4操作同上，出栈为5、1、1 5操作同上，出栈为4、3 6操作同上，出栈为4、2、1 7操作同上，出栈为4、1、1、1

8 这次不一样了，top1第一次出栈3个元素，top2将top1中出栈元素个数记下，top2中有一个元素3。top1再次出栈时发现还有4个元素，我们规定出栈的条件为top2为空（即top1中没有元素出栈）或top1出栈元素个数<=top2栈顶元素，即if(top2 == 0 || i <= a[top2-1]) ，满足这两个条件才可出栈。此时top2栈顶元素为3，top1中还剩4个元素，那么不能出栈4个元素，只可出栈3个，即本次出栈3个，然后出栈1个元素，最终输出3、3、1 . . . 依此类推，15次可完成所有划分

###代码

#includeusing namespace std;int time = 0;//记录分解的个数 void OutPut(int top2, int *a){ int i; for(i=0;i=1; i--) /* 先把所有S1内的元素取出，挨个减少，使得第一个划分的整数减小 一个for循环执行完就可以输出一个表达式 */ { /* S2为空（表示第一次从S1中取元素） 或 将要出栈的元素个数不大于S2栈顶元素 （即后一次拿出的元素个数只能 <= 前一次拿出的元素个数）时开始从S1中取元素 否则进行下一轮循环直到即将出栈的元素个数 i不大于S2栈顶元素（前一次拿出的元素个数） */ if(top2 == 0 || i <= a[top2-1]) { a[top2] = i;//S1出栈元素的个数压入S2，记下该次出栈元素的个数 Div(top1-i,top2+1,a);//S1少了i个元素，S2多了1个元素 } } } } int main(){ int top1;//栈S1其实不存在，假设有top1个1在栈S1 int top2=0; while(cin>>top1) { int *a = new int [top1]; Div(top1,top2,a); delete []a; cout<<"time:"<

###运行结果

第一个7是输入的，下面的是划分结果

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。