4117: 简单的整数划分问题
总时间限制: 100ms 内存限制: 65536kB
描述
将正整数 n 表示成一系列正整数之和, n=n1+n2+...+nk, 其中 n1>=n2>=...>=nk>=1 ,k>=1 .
正整数 n 的这种表示称为正整数 n 的划分. 正整数 n 的不同的划分个数称为正整数 n 的划分数.
输入
标准的输入包含若干组测试数据. 每组测试数据是一个整数 N(0 <N <= 50).
输出
对于每组测试数据, 输出 N 的划分数.
样例输入
5
样例输出
7
提示
5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
问题链接: Bailian4117 简单的整数划分问题 https://cn.vjudge.net/problem/OpenJ_Bailian-4117
问题描述:(略)
问题分析:
???? 这个问题的关键是递推式, 这里就不详细说明了. 另外用记忆化递归实现速度上是快.
程序说明:(略)
参考链接:(略)
题记:(略)
AC 的 C 语言程序 (优化枚举) 如下:
- /* Bailian4117 简单的整数划分问题 */
- #include <stdio.h>
- #include <string.h>
- #define N 50
- int c[N + 1][N + 1];
- int ways(int m, int n)
- {
- if(c[m][n])
- return c[m][n];
- else {
- if(m == 0)
- return c[m][n] = 1;
- else if(n == 0)
- return 0;
- else if(n <= m) {
- if(c[m - n][n] == 0)
- c[m - n][n] = ways(m - n, n);
- if(c[m][n - 1] == 0)
- c[m][n - 1] = ways(m, n - 1);
- return c[m][n] = c[m - n][n] + c[m][n - 1];
- } else
- if(c[m][n - 1])
- return c[m][n - 1];
- else
- return c[m][n - 1] = ways(m, n - 1);
- }
- }
- int main(void)
- {
- memset(c, 0, sizeof(c));
- int n;
- while(~scanf("%d", &n)) {
- printf("%d\n", ways(n, n));
- }
- return 0;
- }
Bailian4117 简单的整数划分问题[记忆化递归]
来源: http://www.bubuko.com/infodetail-2895465.html