欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

递归算法《M个苹果放入N个盘子》

发布时间:2024/5/15 编程问答 2 豆豆
如意编程网 收集整理的这篇文章主要介绍了 递归算法《M个苹果放入N个盘子》 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题目:

把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。

输入

每个用例包含二个整数M和N。0<=m<=10,1<=n<=10。

样例输入

7 3

样例输出

8

【代码】
放苹果分为两种情况,一种是有盘子为空,一种是每个盘子上都有苹果。
令(m,n)表示将m个苹果放入n个盘子中的摆放方法总数。
1.假设有一个盘子为空,则(m,n)问题转化为将m个苹果放在n-1个盘子上,即求得(m,n-1)即可
2.假设所有盘子都装有苹果,则每个盘子上至少有一个苹果,即最多剩下m-n个苹果,问题转化为将m-n个苹果放到n个盘子上
即求(m-n,n)

综上所述:
(m,n)=(m,n-1)+(m-n,n);

#include <bits/stdc++.h>using namespace std;// m = apple; n = plate; int apple(int m, int n) {if (m < 0 ) {return 0;}if (m == 1 || n == 1) {return 1;}cout <<" f = " << m << " " << n << endl;return apple(m, n-1) + apple(m-n, n); }int main() {int m = 0, n = 0;scanf("%d", &m);scanf("%d", &n);printf("%d", apple(m, n));return 0; }```

总结

以上是如意编程网为你收集整理的递归算法《M个苹果放入N个盘子》的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。