已知n,m，求满足 n 个正整数相加的和为 m的组合的个数？
本帖最后由 wzzjnb2006 于 2022-11-13 19:59 编辑在学习编程（C++、python），碰到下面这个题目，没什么思路。
有没有大佬能指点下，这种题目的解题思路，或者是用什么算法？能有源码示例更好，谢谢。
题目：输入两个正整数 n 和 m（20≥m≥n>0），要求 n 个正整数相加的和为 m，输出满足这个条件的正整数组合有多少。
例：n=4,m=8,组合数是5；
n=4,m=7,组合数是3。 两个例子条件一样，结果不一样？ 示例好像不对，两个重复了。
最简单的方法就是遍历了，每个数从1开始到m-n和为m就是了 可以变成辗转相除或者取余数 平淡最真 发表于 2022-11-13 19:39
两个例子条件一样，结果不一样？
写错了，例子是：
n=4,m=8,组合数是5
n=4,m=7,组合数是3 amoxuk 发表于 2022-11-13 19:53
示例好像不对，两个重复了。
最简单的方法就是遍历了，每个数从1开始到m-n和为m就是了
写错了，例子是：
n=4,m=8,组合数是5
n=4,m=7,组合数是3
n不确定，没想到遍历的办法。 ck1001CK 发表于 2022-11-13 19:55
可以变成辗转相除或者取余数
能不能说详细点？不太理解思路。 本帖最后由 zzzzxcv 于 2022-11-14 13:15 编辑
可以搜一下球盒问题，题目的意思相当于把m个球放在n个盒子里，并且不能有空盒的情况。
可以理解为先在每个盒子里放一个球，再把剩余的m-n个球放好；
解法总数等于：将剩余的m-n个球放在1个盒子里+将剩余的球放在2个盒子里+......+将剩余的球放在n个盒子里。
有几个前提：如果只有1个盒子，只有1种放法；如果盒子数等于球数，只有1种放法；如果球比盒子数多一个，只有1种放法；如果盒子数大于球数，必然有盒子是空的，违背题意，算为0种。
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)) zzzzxcv 发表于 2022-11-14 11:40
可以搜一下球盒问题，题目的意思相当于把m个球放在n个盒子里，并且不能有空盒的情况。
可以理解为先在每个 ...
十分感谢大佬的回复。昨天查了一天，查到了球盒问题、递归算法、动态规划，正在学习，一直没能解决实际问题。
把您的代码转成C++了，经验证OK，明天再好好的理解一下，再次感谢。{:1_893:}
#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;
} wzzjnb2006 发表于 2022-11-14 20:58
十分感谢大佬的回复。昨天查了一天，查到了球盒问题、递归算法、动态规划，正在学习，一直没能解决实际问 ...
大佬不敢当，共同学习共同进步{:1_893:}
页:
[1]
2