神马品牌网占地面积100000平方米:关于一道题的算法
来源：百度文库 编辑：神马品牌网 时间：2024/05/07 01:49:52
输入一个整数N，输出它有多少种拆法。
告诉我一下大致想法，谢谢。
如：输入4
输出5
因为
4
=4 第1种
=3+1 第2种
=2+2 第3种
=2+1+1 第4种
=1+1+1+1 第5种
告诉我一下大致想法，谢谢。
如：输入4
输出5
因为
4
=4 第1种
=3+1 第2种
=2+2 第3种
=2+1+1 第4种
=1+1+1+1 第5种
#include "stdio.h"
void main()
{
int n;
scanf("%d", &n);
if (n == 1)
{
printf("1=1\n");
return;
}
if (n == 2)
{
printf("2=1+1\n");
return;
}
int *a = new int(n);
int top = 0;
a[0] = n - 1;
a[1] = 1;
top = 2;
int i;
do{
printf("%d=%d", n, a[0]);
for (i = 1; i < top; i++)
{
printf("+%d", a[i]);
}
printf("\n");
int s = 0;
do{
s += a[--top];
}while (top >= 0 && a[top] == 1);
if (top == -1)
{
break;
}
int d = a[top] - 1;
if (d == 1)
{
while (s > 0)
{
a[top++] = 1;
s--;
}
}
else
{
do{
a[top++] = d;
s -= d;
}while (s >= d);
if (s != 0)
{
a[top++] = s;
}
}
}while (1);
}
我这个程序是输出所有拆分方法的，你可以在输出一个拆分方法时，用一个整型变量去统计一下。