[已解决]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

最佳答案

月排行榜 / 总排行榜

isdkz

2023-4-3 21:03:51

1. # coding: utf-8
   
2. 
   
3. def split_n_k(n, k):
   
4.     """
   
5.     将正整数 n 划分成 k 个正整数之和的划分数目
   
6.     """
   
7.     if n < k:
   
8.         return 0
   
9.     if n == k:
   
10.         return 1
    
11.     # 动态规划
    
12.     dp = [[0] * (n + 1) for _ in range(k + 1)]
    
13.     for i in range(1, k + 1):
    
14.         for j in range(i, n + 1):
    
15.             if i == 1:
    
16.                 dp[i][j] = 1
    
17.             else:
    
18.                 dp[i][j] = dp[i - 1][j - i] + dp[i][j - i]
    
19.     return dp[k][n]
    
20. 
    
21. 
    
22. def split_diff(n):
    
23.     """
    
24.     将正整数 n 划分成若干个不同正整数之和的划分数目
    
25.     """
    
26.     dp = [0] * (n + 1)
    
27.     dp[0] = 1
    
28.     for i in range(1, n + 1):
    
29.         for j in range(n, i - 1, -1):
    
30.             dp[j] += dp[j - i]
    
31.     return dp[n]
    
32. 
    
33. 
    
34. def split_odd(n):
    
35.     """
    
36.     将正整数 n 划分成若干个奇正整数之和的划分数目
    
37.     """
    
38.     # 这里的代码和上面的 split_diff 函数也很相似
    
39.     dp = [0] * (n + 1)
    
40.     dp[0] = 1
    
41.     for i in range(1, n + 1, 2):
    
42.         for j in range(i, n + 1):
    
43.             dp[j] += dp[j - i]
    
44.     return dp[n]
    
45. 
    
46. 
    
47. while True:
    
48.     try:
    
49.         n, k = map(int, input().split())
    
50.         print(split_n_k(n, k))
    
51.         print(split_diff(n))
    
52.         print(split_odd(n))
    
53.     except:
    
54.         break
    

复制代码

跳转到最佳答案楼层

isdkz

1. # coding: utf-8
   
2. 
   
3. def split_n_k(n, k):
   
4.     """
   
5.     将正整数 n 划分成 k 个正整数之和的划分数目
   
6.     """
   
7.     if n < k:
   
8.         return 0
   
9.     if n == k:
   
10.         return 1
    
11.     # 动态规划
    
12.     dp = [[0] * (n + 1) for _ in range(k + 1)]
    
13.     for i in range(1, k + 1):
    
14.         for j in range(i, n + 1):
    
15.             if i == 1:
    
16.                 dp[i][j] = 1
    
17.             else:
    
18.                 dp[i][j] = dp[i - 1][j - i] + dp[i][j - i]
    
19.     return dp[k][n]
    
20. 
    
21. 
    
22. def split_diff(n):
    
23.     """
    
24.     将正整数 n 划分成若干个不同正整数之和的划分数目
    
25.     """
    
26.     dp = [0] * (n + 1)
    
27.     dp[0] = 1
    
28.     for i in range(1, n + 1):
    
29.         for j in range(n, i - 1, -1):
    
30.             dp[j] += dp[j - i]
    
31.     return dp[n]
    
32. 
    
33. 
    
34. def split_odd(n):
    
35.     """
    
36.     将正整数 n 划分成若干个奇正整数之和的划分数目
    
37.     """
    
38.     # 这里的代码和上面的 split_diff 函数也很相似
    
39.     dp = [0] * (n + 1)
    
40.     dp[0] = 1
    
41.     for i in range(1, n + 1, 2):
    
42.         for j in range(i, n + 1):
    
43.             dp[j] += dp[j - i]
    
44.     return dp[n]
    
45. 
    
46. 
    
47. while True:
    
48.     try:
    
49.         n, k = map(int, input().split())
    
50.         print(split_n_k(n, k))
    
51.         print(split_diff(n))
    
52.         print(split_odd(n))
    
53.     except:
    
54.         break
    

复制代码

sfqxx

1. #include <iostream>
   
2. using namespace std;
   
3. const int MAXN = 55;
   
4. int dp[MAXN][MAXN]; // dp[i][j]表示i划分成j个数的方案数
   
5. int dp2[MAXN][MAXN]; // dp2[i][j]表示i划分成j个不同正整数之和的方案数
   
6. int dp3[MAXN][MAXN]; // dp3[i][j]表示i划分成j个奇正整数之和的方案数
   
7. int main() {
   
8.     // 预处理dp
   
9.     for (int i = 1; i < MAXN; i++) {
   
10.         dp[i][1] = 1; // i只能划分成一个数，方案数为1
    
11.         for (int j = 2; j <= i; j++) {
    
12.             dp[i][j] = dp[i-j][j] + dp[i-1][j-1]; // 递推
    
13.         }
    
14.     }
    
15.     // 预处理dp2
    
16.     for (int i = 1; i < MAXN; i++) {
    
17.         dp2[i][1] = 1; // i只能划分成一个数，方案数为1
    
18.         for (int j = 2; j <= i; j++) {
    
19.             dp2[i][j] = dp2[i-j][j-1] + dp2[i-1][j-1]; // 递推
    
20.         }
    
21.     }
    
22.     // 预处理dp3
    
23.     for (int i = 1; i < MAXN; i++) {
    
24.         dp3[i][1] = 1; // 只有一个奇数i，方案数为1
    
25.         for (int j = 2; j <= i; j++) {
    
26.             dp3[i][j] = dp3[i-j][j-1] + dp3[i-1][j-1]; // 递推
    
27.         }
    
28.     }
    
29.     // 处理输入
    
30.     int n, k;
    
31.     while (cin >> n >> k) {
    
32.         cout << dp[n][k] << endl; // 输出第一问答案
    
33.         // 计算第二问答案（只需要在dp2的结果中减去dp的结果即可）
    
34.         int ans2 = 0;
    
35.         for (int i = 1; i <= k; i++) {
    
36.             ans2 += dp2[n][i] - dp[n][i];
    
37.         }
    
38.         cout << ans2 << endl;
    
39.         // 计算第三问答案（只需要在dp3的结果中减去dp2的结果即可）
    
40.         int ans3 = 0;
    
41.         for (int i = 1; i <= k; i++) {
    
42.             ans3 += dp3[n][i] - dp2[n][i];
    
43.         }
    
44.         cout << ans3 << endl;
    
45.     }
    
46.     return 0;
    
47. }

复制代码