intpart.cpp

采用非递归方法实现的整数分拆程序

// intpart.cpp : Defines the entry point for the console application.
//
// ***************************************************************
//  intpart   version:  1.0   ? date: 02/11/2009
//  -------------------------------------------------------------
//  整数分解的非递归版本。使用了两个栈，一个保存分解成的数字（从大到小），
//  另一个（依次）保存各数字出现的次数。  
//  -------------------------------------------------------------
//  Copyright (C) 2009 - All Rights Reserved
// ***************************************************************
// 
// ***************************************************************
#include "stdafx.h"

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>

#define MAXSIZE		50 //控制堆栈的最大高度
typedef unsigned int UINT;
char print=0;	  //控制是否打印结果的标记变量。由键盘输入值控制

UINT IntPart(UINT n);
int main()
{
	UINT n;
	int ch;
	printf("=========正整数分解程序(非递归版)===\n");
	printf("输入正整数n，本程序将把它分解成不\n大于它的数字的和的形式\n");
	printf("================================\n\n");
	//输入n
	printf("input n(>0): ");
	scanf("%ud",&n);
	if(n<=0)
		exit(-1);
	
	printf("要打印分拆结果吗？[y|n]");
	ch=getche();//此标志用来控制是否显示分割结果。主要是当n比较大时用。
	if(ch=='y') print=1;
	else print = 0;
	printf("\nPlease wait.....\n");
	clock_t begin_time, end_time;
	begin_time= clock();

	if(print)
		printf("\n%-2d=\n",n);

	IntPart(n);

	end_time  = clock();
	printf("\nTime elapsed:%.3lf (ms)\n",(double)(end_time-begin_time));
	return 0;
}
/*******************************************************************
 函数IntPart把输入整数n进行分拆，并根据全局变量print的值确定是否打印
 分解结果，返回值为分拆的种数。
 使用两个数组型堆栈的目的是减小存储量。可以跟只用一个堆栈的方法对比
********************************************************************/
//************************************
// Method:    IntPart
// FullName:  IntPart
// Access:    public 
// Returns:   int
// Qualifier: 
// Parameter: UINT n
//************************************
UINT IntPart(UINT n)
{
	UINT partition[MAXSIZE+1]={0}, repeat[MAXSIZE+1]={0}; //第一个存分割的数字，第二个存该数字出现的次数

	//top表示栈顶位置，next表示比栈顶数小的下一个数,sum是n减去栈中元素和之后的差
	UINT top=1,next=n,sum=0,cnt=1; //栈从1开始增长
	int i,j,k;

	//初始化，将n压栈
    partition[top]=n,repeat[top]++;
	if(print)     printf("%3d \n", n); //打印控制。后面打印的地方同此。

	//程序主体
	do
	{
		next = partition[top]-1;


		//把栈顶元素弹出一个出去,并调整之后栈顶的位置。注意：1是不会压入栈中去的
		sum	+= partition[top];
		if(--repeat[top]==0) //要判断栈顶元素是不是只出现一次，弹出去就没有了？
			if(next==1)
				top--;

		//进而把sum分成next的和，并压栈
		if(next==1)				//因为1不会压栈，所以此时便可打印一个结果
		{
			if(print)
			{
				for(i=1;i<=top;i++)
					for(j=1;j<=repeat[i];j++)
						printf("%3d ",partition[i]);

				for(i=1;i<=sum;i++)
					printf("%3d ", next);
				printf("\n");
			}
			cnt++;
		}else//next>1,把sum中的next压栈，压栈次数放到repeat[top]中，直至sum剩下的值小于next
		{
			if(repeat[top]) top++;

			partition[top] = next;
			while(sum>=next)
			{
				repeat[top]++;
				sum-=partition[top];
			}
			if(print)
			{
				for(i=1;i<=top;i++)
					for(j=1;j<=repeat[i];j++)
						printf("%3d ",partition[i]);
				if(sum) printf("%3d", sum);
				printf("\n");
			}
			cnt++;
			if(sum>1)//压完栈之后，如果sum中的值大于1，再把该值也压栈，并减小sum
			{
				top++;
				partition[top]=sum;
				repeat[top]++;
				sum-=partition[top];
			}
		}
	}while(top>0);
	printf("\n\n正整数%d有总共%d种分割方法\n",n,cnt);
	return cnt;
}

/*如n＝7，则结果为：
7 =
  7
  6   1
  5   2
  5   1   1
  4   3
  4   2   1
  4   1   1   1
  3   3   1
  3   2   2
  3   2   1   1
  3   1   1   1   1
  2   2   2   1
  2   2   1   1   1
  2   1   1   1   1   1
  1   1   1   1   1   1   1
先置栈顶top=1,把n放入栈中。sum=0,repeat[1]=1（表示n出现一次，后面不再解释）。

 (1)next=栈顶当前值-1;
 (2)弹出一个栈顶值来，加到sum上去。如果栈顶值只重复一次，且next==1，则栈顶位置下降一。
 (3)把sum分解成最大值为next 的若干数字之和。
    (i) 若next为1，则打印出栈内的数字，并打印sum个1，完成一种分割方法。
	(ii)若next>1，把sum中的next压栈。从sum中减去next作为新的sum。如此循环直至sum<next。
	于是得到一种分割。打印出结果。sum若大于1，也要压入栈中。
 (4)如果栈顶大于0，则到(1)

其实质是：栈顶以下的元素是保持不动的，而栈顶+sum构成的和被分解成最大值为栈顶元素值的
          分拆。

给出一个n，画出堆栈的变化情况，观察sum，top,next的变化情况可以加深对算法的理解。
*/