/*
数字拆解
说明
题目是这样的：
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的拆解方法个数有多少个？
解法
我们以上例中最后一个数字5的拆解为例，假设f( n )为数字n的可拆解方式个数，而f(x, y)为使
用y以下的数字来拆解x的方法个数，则观察：
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1
使用函式来表示的话：
f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,4) + f(0,5)
其中f(1, 4) = f(1, 3) + f(1, 2) + f(1, 1)，但是使用大于1的数字来拆解1没有意义，所以f(1, 4) =
f(1, 1)，而同样的，f(0, 5)会等于f(0, 0)，所以：
f(5) = f(4, 1) + f(3,2) + f(2,3) + f(1,1) + f(0,0)
依照以上的说明，使用动态程式规画（Dynamic programming）来进行求解，其中f(4,1)其实就
是f(5-1, min(5-1,1))，f(x, y)就等于f(n-y, min(n-x, y))，其中n为要拆解的数字，而min()表示取两
者中较小的数。
使用一个二维阵列表格table[x][y]来表示f(x, y)，刚开始时，将每列的索引0与索引1元素值设定
为1，因为任何数以0以下的数拆解必只有1种，而任何数以1以下的数拆解也必只有1种：
for(i = 0; i < NUM +1; i++){
table[i][0] = 1; // 任何数以0以下的数拆解必只有1种
table[i][1] = 1; // 任何数以1以下的数拆解必只有1种
}
接下来就开始一个一个进行拆解了，如果数字为NUM，则我们的阵列维度大小必须为NUM x
(NUM/2+1)，以数字10为例，其维度为10 x 6我们的表格将会如下所示：
1 1 0 0 0 0
1 1 0 0 0 0
1 1 2 0 0 0
1 1 2 3 0 0
1 1 3 4 5 0
1 1 3 5 6 7
1 1 4 7 9 0
1 1 4 8 0 0
1 1 5 0 0 0
1 1 0 0 0 0
*/
#include <stdio.h>
#include <stdlib.h>
#define DEBUG 0
int main(void)
{
int NUM;
int N;
int **table = NULL;// 动态规画表格
int count = 0;
int result = 0;
int i, j, k;
printf("请输入M:");
scanf("%d", &NUM);
printf("请输入N:");
scanf("%d", &N);
table = (int **) malloc (sizeof(int *));
for (i=0; i<N+1; i++)
{
table[i] = (int *) malloc (sizeof(int));
}
printf("数字拆解\n");
printf("3 = 2+1 = 1+1+1 所以3有三种拆法\n");
printf("4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1");
printf("共五种\n");
printf("5 = 4 + 1 = 3 + 2 = 3 + 1 + 1");
printf(" = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1");
printf("共七种\n");
printf("依此类推，求 %d %d 有几种拆法？", NUM, N);
// 初始化
for(i = 0; i < N+1; i++)
{
table[i][0] = 1; // 任何数以0以下的数拆解必只有1种
table[i][1] = 1; // 任何数以1以下的数拆解必只有1种
}
// 动态规划
for(i = 2; i <= N+1; i++)
{
for(j = 2; j <= i; j++)
{
if(i + j > N+1) // 大于NUM
continue;
count = 0;
for(k = 1 ; k <= j; k++)
{
count += table[i-k][(i-k >= k) ? k : i-k];
}
table[i][j] = count;
}
}
// 计算并显示结果
for(k = 1 ; k <= N+1; k++)
result += table[N-k+1][(N-k+1 >= k) ? k : N-k+1];
printf("\n\nresult: %d\n", result);
if(DEBUG)
{
printf("\n除错资讯\n");
for(i = 0; i < N+1; i++)
{
for(j = 0; j < (N+1)/2+1; j++)
printf("%2d", table[i][j]);
printf("\n");
}
}
return 0;
}
追问输入6 3结果是5，不正确。
追答好了
#include
#include
#define DEBUG 0
int main(void)
{
int M;
int N;
int **table = NULL;// 动态规画表格
int count = 0;
int result = 0;
int i, j, k;
printf("请输入M:");
scanf("%d", &M);
printf("请输入N:");
scanf("%d", &N);
table = (int **) malloc (sizeof(int *));
for (i=0; i M) // 大于M
{
continue;
}
count = 0;
for (k=1; k= k) ? k : i-k];
}
table[i][j] = count;
}
}
// 计算并显示结果
for (k=1; k= k) ? k : M-k];
}
printf("\n\nf(%d, %d) = %d\n\n", M, N, result);
return 0;
}
追问输入30 2结果是16，正确
输入40 2结果是18908，不正确
追答f(40,2) = 21，再错我就不写了，我晕~~~
#include
#include
#define SIZE 100
int main(void)
{
int M;
int N;
int table[SIZE][SIZE/2+1] = { 0 };// 动态规画表格
int count = 0;
int result = 0;
int i, j, k;
printf("请输入M:");
scanf("%d", &M);
printf("请输入N:");
scanf("%d", &N);
if ((M = M || 100 = N || 10 M) // 大于M
{
continue;
}
count = 0;
for (k=1; k= k) ? k : i-k];
}
table[i][j] = count;
}
}
// 计算并显示结果
for (k=1; k= k) ? k : M-k];
}
printf("\n\nf(%d, %d) = %d\n\n", M, N, result);
return 0;
}