程序竞赛里的一个递归问题．．高手帮忙．．
以下问题，如何用C实现才是最优的程序呢？各位高人解一下
随机输入一个2至100的数,产生相应的输出,如输入数为5,则输出以下结果
5=1+1+1+1+1
=1+1+1+2
=1+2+2
=1+1+3
=2+3
=1+4
[解决办法]
这个是经典的自然数分拆问题也叫做是欧拉分拆。
一般用递归就可以实现。
例如5的拆分，可以化成1+(4的拆分)，2+(3的拆分)。
下面写的大概的程序
program input n;
program output split;
#include <stdio.h>
#include <string.h>
long res[1024],Total;
void fen(long n, long m)
{
long rest,i,j;
for(i=1;i <=n;i++)
{
if(i> =res[m-1])
{
res[m]=i;
rest=n-i;
if(rest==0&&m> 1)
{
Total++;
printf( "%ld\t ",Total);
for(j=1;j <=m;j++)
{
printf( "%ld ",res[j]);
}
printf( "\n ");
}
else
{
fen(rest,m+1);
}
res[m]=0;
}
}
}
int main()
{
long n;
printf( "Input n: ");
scanf( "%ld ",&n);
memset(res,0,sizeof(res));
Total=0;
fen(n,1);
return 0;
}
[解决办法]
int path[128];
int index = 0;
int g_number = 5;
void TestTheNumber(int number){
int sum = getTheSum();
if(number + sum == g_number){
for(int i = 0;i < index;i ++)
printf( "%d\t ",path[i]);
}
else{
path[index ++] = number;
}
for(int i = number - 1;i > = (number - 1) / 2;i --){
TestTheNumber(i);
}
}
int getTheSum(){
int sum = 0;
for(int i = 0;i <= index;i ++)
sum += path[index];
return sum;
}
[解决办法]
memset
表示吧数组res的内存每个值都初始化0
