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

# coding: utf-8

def split_n_k(n, k):
    """
    将正整数 n 划分成 k 个正整数之和的划分数目
    """
    if n < k:
        return 0
    if n == k:
        return 1
    # 动态规划
    dp = [[0] * (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[i][j] = 1
            else:
                dp[i][j] = dp[i - 1][j - i] + dp[i][j - i]
    return dp[k][n]


def split_diff(n):
    """
    将正整数 n 划分成若干个不同正整数之和的划分数目
    """
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        for j in range(n, i - 1, -1):
            dp[j] += dp[j - i]
    return dp[n]


def split_odd(n):
    """
    将正整数 n 划分成若干个奇正整数之和的划分数目
    """
    # 这里的代码和上面的 split_diff 函数也很相似
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1, 2):
        for j in range(i, n + 1):
            dp[j] += dp[j - i]
    return dp[n]


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

跳转到最佳答案楼层

isdkz

# coding: utf-8

def split_n_k(n, k):
    """
    将正整数 n 划分成 k 个正整数之和的划分数目
    """
    if n < k:
        return 0
    if n == k:
        return 1
    # 动态规划
    dp = [[0] * (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[i][j] = 1
            else:
                dp[i][j] = dp[i - 1][j - i] + dp[i][j - i]
    return dp[k][n]


def split_diff(n):
    """
    将正整数 n 划分成若干个不同正整数之和的划分数目
    """
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1):
        for j in range(n, i - 1, -1):
            dp[j] += dp[j - i]
    return dp[n]


def split_odd(n):
    """
    将正整数 n 划分成若干个奇正整数之和的划分数目
    """
    # 这里的代码和上面的 split_diff 函数也很相似
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(1, n + 1, 2):
        for j in range(i, n + 1):
            dp[j] += dp[j - i]
    return dp[n]


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

sfqxx

#include <iostream>
using namespace std;
const int MAXN = 55;
int dp[MAXN][MAXN]; // dp[i][j]表示i划分成j个数的方案数
int dp2[MAXN][MAXN]; // dp2[i][j]表示i划分成j个不同正整数之和的方案数
int dp3[MAXN][MAXN]; // dp3[i][j]表示i划分成j个奇正整数之和的方案数
int main() {
    // 预处理dp
    for (int i = 1; i < MAXN; i++) {
        dp[i][1] = 1; // i只能划分成一个数，方案数为1
        for (int j = 2; j <= i; j++) {
            dp[i][j] = dp[i-j][j] + dp[i-1][j-1]; // 递推
        }
    }
    // 预处理dp2
    for (int i = 1; i < MAXN; i++) {
        dp2[i][1] = 1; // i只能划分成一个数，方案数为1
        for (int j = 2; j <= i; j++) {
            dp2[i][j] = dp2[i-j][j-1] + dp2[i-1][j-1]; // 递推
        }
    }
    // 预处理dp3
    for (int i = 1; i < MAXN; i++) {
        dp3[i][1] = 1; // 只有一个奇数i，方案数为1
        for (int j = 2; j <= i; j++) {
            dp3[i][j] = dp3[i-j][j-1] + dp3[i-1][j-1]; // 递推
        }
    }
    // 处理输入
    int n, k;
    while (cin >> n >> k) {
        cout << dp[n][k] << endl; // 输出第一问答案
        // 计算第二问答案（只需要在dp2的结果中减去dp的结果即可）
        int ans2 = 0;
        for (int i = 1; i <= k; i++) {
            ans2 += dp2[n][i] - dp[n][i];
        }
        cout << ans2 << endl;
        // 计算第三问答案（只需要在dp3的结果中减去dp2的结果即可）
        int ans3 = 0;
        for (int i = 1; i <= k; i++) {
            ans3 += dp3[n][i] - dp2[n][i];
        }
        cout << ans3 << endl;
    }
    return 0;
}