2877 - 【创新型】第7章：函数 数字拆解
3 = 2+1 = 1+1+1 共三种拆法
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 共七种拆法
依此类推，请问一个从键盘输入的n值（2<n<100）拆解方法有多少种？
Input
1个数n。表示要拆解的数字。
Output
1个数。表示拆解方法的个数。
Examples
Input
10
Output
42
Solution C
#include <stdio.h> #include <stdlib.h> #define NUM 100 // 要拆解的数字 #define DEBUG 0 int main(void) { int table[NUM][NUM/2+1] = {0}; // 动态规画表格 int count = 0; int result = 0; int i, j, k,n; scanf("%d",&n); // 初始化 for(i = 0; i < n; i++) { table[i][0] = 1; // 任何数以0以下的数拆解必只有1种 table[i][1] = 1; // 任何数以1以下的数拆解必只有1种 table[i][2] = 1; } // 动态规划 for(i = 2; i <= n; i++) { for(j = 2; j <= i; j++) { if(i + j > n) // 大于 n 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; k++) result += table[n-k][(n-k >= k) ? k : n-k]; printf("%d\n", result); if(DEBUG) { printf("\n除错资讯\n"); for(i = 0; i < n; i++) { for(j = 0; j < n/2+1; j++) printf("%2d", table[i][j]); printf("\n"); } } return 0; }
Solution C++
#include <cstdio> int split(int n, int m) { if(n==1||m==1) return 1; if(n<=m) return 1+split(n, n-1); return split(n-m, m)+split(n, m-1); } int main(void) { int n, m; scanf("%d", &n); printf("%d\n", split(n, n)); return 0; }