// intpart.cpp : Defines the entry point for the console application.
//
// ***************************************************************
//  intpart   version:  1.0   ? date: 02/11/2009
//  -------------------------------------------------------------
//  整數(shù)分解的非遞歸版本。使用了兩個(gè)棧，一個(gè)保存分解成的數(shù)字（從大到小），
//  另一個(gè)（依次）保存各數(shù)字出現(xiàn)的次數(shù)。  
//  -------------------------------------------------------------
//  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;	  //控制是否打印結(jié)果的標(biāo)記變量。由鍵盤輸入值控制

UINT IntPart(UINT n);
int main()
{
	UINT n;
	int ch;
	printf("=========正整數(shù)分解程序(非遞歸版)===\n");
	printf("輸入正整數(shù)n，本程序?qū)阉纸獬刹籠n大于它的數(shù)字的和的形式\n");
	printf("================================\n\n");
	//輸入n
	printf("input n(>0): ");
	scanf("%ud",&n);
	if(n<=0)
		exit(-1);
	
	printf("要打印分拆結(jié)果嗎？[y|n]");
	ch=getche();//此標(biāo)志用來控制是否顯示分割結(jié)果。主要是當(dāng)n比較大時(shí)用。
	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;
}
/*******************************************************************
 函數(shù)IntPart把輸入整數(shù)n進(jìn)行分拆，并根據(jù)全局變量print的值確定是否打印
 分解結(jié)果，返回值為分拆的種數(shù)。
 使用兩個(gè)數(shù)組型堆棧的目的是減小存儲(chǔ)量。可以跟只用一個(gè)堆棧的方法對(duì)比
********************************************************************/
//************************************
// 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}; //第一個(gè)存分割的數(shù)字，第二個(gè)存該數(shù)字出現(xiàn)的次數(shù)

	//top表示棧頂位置，next表示比棧頂數(shù)小的下一個(gè)數(shù),sum是n減去棧中元素和之后的差
	UINT top=1,next=n,sum=0,cnt=1; //棧從1開始增長(zhǎng)
	int i,j,k;

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

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


		//把棧頂元素彈出一個(gè)出去,并調(diào)整之后棧頂?shù)奈恢谩Ｗ⒁猓?是不會(huì)壓入棧中去的
		sum	+= partition[top];
		if(--repeat[top]==0) //要判斷棧頂元素是不是只出現(xiàn)一次，彈出去就沒有了？
			if(next==1)
				top--;

		//進(jìn)而把sum分成next的和，并壓棧
		if(next==1)				//因?yàn)?不會(huì)壓棧，所以此時(shí)便可打印一個(gè)結(jié)果
		{
			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壓棧，壓棧次數(shù)放到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正整數(shù)%d有總共%d種分割方法\n",n,cnt);
	return cnt;
}

/*如n＝7，則結(jié)果為：
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出現(xiàn)一次，后面不再解釋）。

 (1)next=棧頂當(dāng)前值-1;
 (2)彈出一個(gè)棧頂值來，加到sum上去。如果棧頂值只重復(fù)一次，且next==1，則棧頂位置下降一。
 (3)把sum分解成最大值為next 的若干數(shù)字之和。
    (i) 若next為1，則打印出棧內(nèi)的數(shù)字，并打印sum個(gè)1，完成一種分割方法。
	(ii)若next>1，把sum中的next壓棧。從sum中減去next作為新的sum。如此循環(huán)直至sum<next。
	于是得到一種分割。打印出結(jié)果。sum若大于1，也要壓入棧中。
 (4)如果棧頂大于0，則到(1)

其實(shí)質(zhì)是：棧頂以下的元素是保持不動(dòng)的，而棧頂+sum構(gòu)成的和被分解成最大值為棧頂元素值的
          分拆。

給出一個(gè)n，畫出堆棧的變化情況，觀察sum，top,next的變化情況可以加深對(duì)算法的理解。
*/