Python求助：复杂的整数划分问题
复杂的整数划分问题总时间限制: 200ms 内存限制: 65536kB
描述
将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。
正整数n 的这种表示称为正整数n 的划分。
输入
标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。
(0 < N <= 50, 0 < K <= N)
输出
对于每组测试数据，输出以下三行数据:
第一行: N划分成K个正整数之和的划分数目
第二行: N划分成若干个不同正整数之和的划分数目
第三行: N划分成若干个奇正整数之和的划分数目
样例输入
5 2
样例输出
2
3
3
提示
第一行: 4+1, 3+2,
第二行: 5，4+1，3+2
第三行: 5，1+1+3， 1+1+1+1+1+1 # coding: utf-8
def split_n_k(n, k):
"""
将正整数 n 划分成 k 个正整数之和的划分数目
"""
if n < k:
return 0
if n == k:
return 1
# 动态规划
dp = [ * (n + 1) for _ in range(k + 1)]
for i in range(1, k + 1):
for j in range(i, n + 1):
if i == 1:
dp = 1
else:
dp = dp + dp
return dp
def split_diff(n):
"""
将正整数 n 划分成若干个不同正整数之和的划分数目
"""
dp = * (n + 1)
dp = 1
for i in range(1, n + 1):
for j in range(n, i - 1, -1):
dp += dp
return dp
def split_odd(n):
"""
将正整数 n 划分成若干个奇正整数之和的划分数目
"""
# 这里的代码和上面的 split_diff 函数也很相似
dp = * (n + 1)
dp = 1
for i in range(1, n + 1, 2):
for j in range(i, n + 1):
dp += dp
return dp
while True:
try:
n, k = map(int, input().split())
print(split_n_k(n, k))
print(split_diff(n))
print(split_odd(n))
except:
break
#include <iostream>
using namespace std;
const int MAXN = 55;
int dp; // dp表示i划分成j个数的方案数
int dp2; // dp2表示i划分成j个不同正整数之和的方案数
int dp3; // dp3表示i划分成j个奇正整数之和的方案数
int main() {
// 预处理dp
for (int i = 1; i < MAXN; i++) {
dp = 1; // i只能划分成一个数，方案数为1
for (int j = 2; j <= i; j++) {
dp = dp + dp; // 递推
}
}
// 预处理dp2
for (int i = 1; i < MAXN; i++) {
dp2 = 1; // i只能划分成一个数，方案数为1
for (int j = 2; j <= i; j++) {
dp2 = dp2 + dp2; // 递推
}
}
// 预处理dp3
for (int i = 1; i < MAXN; i++) {
dp3 = 1; // 只有一个奇数i，方案数为1
for (int j = 2; j <= i; j++) {
dp3 = dp3 + dp3; // 递推
}
}
// 处理输入
int n, k;
while (cin >> n >> k) {
cout << dp << endl; // 输出第一问答案
// 计算第二问答案（只需要在dp2的结果中减去dp的结果即可）
int ans2 = 0;
for (int i = 1; i <= k; i++) {
ans2 += dp2 - dp;
}
cout << ans2 << endl;
// 计算第三问答案（只需要在dp3的结果中减去dp2的结果即可）
int ans3 = 0;
for (int i = 1; i <= k; i++) {
ans3 += dp3 - dp2;
}
cout << ans3 << endl;
}
return 0;
}
页:
[1]