已知n,m，求满足 n 个正整数相加的和为 m的组合的个数？

wzzjnb2006

在学习编程（C++、python），碰到下面这个题目，没什么思路。
有没有大佬能指点下，这种题目的解题思路，或者是用什么算法？能有源码示例更好，谢谢。


题目：输入两个正整数 n 和 m（20≥m≥n>0），要求 n 个正整数相加的和为 m，输出满足这个条件的正整数组合有多少。
例：n=4,m=8,组合数是5；
　　n=4,m=7,组合数是3。

平淡最真

两个例子条件一样，结果不一样？

amoxuk

示例好像不对，两个重复了。
最简单的方法就是遍历了，每个数从1开始到m-n和为m就是了

ck1001CK

可以变成辗转相除或者取余数

wzzjnb2006

平淡最真 发表于 2022-11-13 19:39
两个例子条件一样，结果不一样？

写错了，例子是：
n=4,m=8,组合数是5
n=4,m=7,组合数是3

wzzjnb2006

amoxuk 发表于 2022-11-13 19:53
示例好像不对，两个重复了。
最简单的方法就是遍历了，每个数从1开始到m-n和为m就是了

写错了，例子是：
n=4,m=8,组合数是5
n=4,m=7,组合数是3

n不确定，没想到遍历的办法。

wzzjnb2006

ck1001CK 发表于 2022-11-13 19:55
可以变成辗转相除或者取余数

能不能说详细点？不太理解思路。

zzzzxcv

可以搜一下球盒问题，题目的意思相当于把m个球放在n个盒子里，并且不能有空盒的情况。
可以理解为先在每个盒子里放一个球，再把剩余的m-n个球放好；
解法总数等于：将剩余的m-n个球放在1个盒子里+将剩余的球放在2个盒子里+......+将剩余的球放在n个盒子里。

有几个前提：如果只有1个盒子，只有1种放法；如果盒子数等于球数，只有1种放法；如果球比盒子数多一个，只有1种放法；如果盒子数大于球数，必然有盒子是空的，违背题意，算为0种。

[Python] 纯文本查看 复制代码

n = 4
m = 8

def a(n, m):
    if n == 1:
        return 1
    elif n == m:
        return 1
    elif n == m - 1:
        return 1
    elif n > m:
        return 0

    s = 0
    for i in range(1, n + 1):
        s += a(i, m - n)
    return s

print(a(n, m))

wzzjnb2006

zzzzxcv 发表于 2022-11-14 11:40
可以搜一下球盒问题，题目的意思相当于把m个球放在n个盒子里，并且不能有空盒的情况。
可以理解为先在每个 ...

十分感谢大佬的回复。昨天查了一天，查到了球盒问题、递归算法、动态规划，正在学习，一直没能解决实际问题。
把您的代码转成C++了，经验证OK，明天再好好的理解一下，再次感谢。

[C++] 纯文本查看 复制代码

#include <iostream>
using namespace std;

int f(int n, int m)
{
    int i, sum = 0;

    if (n == 1)
    {
        return 1;
    }
    else if (n == m)
    {
        return 1;
    }
    else if (n > m)
    {
        return 0;
    }

    for (i = 1; i <= n; i++)
    {
        sum += f(i, m - n);
    }

    return sum;
}

int main()
{
    int n, m, sum;

    cin >> n;
    cin >> m;

    sum = f(n, m);

    cout << sum;
}

zzzzxcv

wzzjnb2006 发表于 2022-11-14 20:58
十分感谢大佬的回复。昨天查了一天，查到了球盒问题、递归算法、动态规划，正在学习，一直没能解决实际问 ...

大佬不敢当，共同学习共同进步