C语言学习--数字拆解

浏览数：23 / 时间：2015年06月08日

原题再现：

3 = 2 + 1 = 1 + 1 + 1 所以3有三种拆法

4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五种

5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1 共七种

依此类推，请问一个指定数字NUM的拆解方法个数有多少个？
程序设计：

1、整型变量n用来记录待判定的数，整型指针t用来指向存放一组成功的结果。整型变量i用以控制初始化数组的循环；

2、关键算法递归寻找结果序列 Dismantling；

3、输出函数，printResult。

算法描述：

1、首次传入带判定的数n，待产生的结果序列中的数在结果数组中的序号i，结果数组t;

2、如果n为0,输出结果；否则循环测试结果序列中第i+1个数；

3、如果i>0并且循环测试的k不于结果序列中在他位置之前的数t[i-1]则执行2，否则执行4；

4、 t[i] = k; n -= k; i++;

5、递归判断n的剩余部分；

6、逆置4，同时返回2.

/*
	功能：数字拆解
	时间：2014-09-08 21:03:40
*/

#include <stdio.h>
#include <malloc.h>

void Dismantling(int n, int i, int *t);	//递归寻找结果序列
void printResult(int i, int *t);	//打印结果

int Count = 0;

int main()
{
	int n;	//待判定的数
	int *t;	//结果序列缓存数组
	int i;	//初始化结果数组变量
	
	printf("Please Enter a number(n>0):");
	scanf("%d/n",&n);

	t = (int *)malloc(n);
	for(i=0; i<n; i++)
	{
		t[0] = 0;
	}

	Dismantling(n, 0, t);

	//free(t);

	return 0;
}

void Dismantling(int n, int i, int *t)
{
	int k;

	if(n == 0)
	{
		//OutPut Result
		printResult(i, t);
	}
	else
	{
		//Recursive Find Result Sequence
		for(k=1; k<=n; k++)
		{
			if(i>0 && k<t[i-1]) //让大数在，后小数在前，用来防止结果重复
				continue;
			t[i] = k;
			n -= k;
			i++;
			Dismantling(n, i, t);
			i--;
			n +=k;
			t[i] = 1;
		}
	}
}

void printResult(int i, int *t)
{
	int j;
	printf("The %3d Result is :", ++Count);
	for(j=i-1; j>0; j--)
	{
		printf("%d+", t[j]);
	}
	printf("%d\n", t[0]);
}

　　结果：