欢迎访问 如意编程网!

如意编程网

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

编程问答

算法题放苹果:把M个相同的苹果放到N个完全相同的盘子里,有多少种放法?

发布时间:2024/5/15 编程问答 1 豆豆
如意编程网 收集整理的这篇文章主要介绍了 算法题放苹果:把M个相同的苹果放到N个完全相同的盘子里,有多少种放法? 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

文章目录

  • 题目描述
  • 题解
  • 思路1 暴力递归
  • 思路2:缓存思想——动态规划来优化暴力递归

题目描述


链接:点我做题

题解

思路1 暴力递归

  我们利用递归来解决这个问题,不妨这样思考,假设apples表示当前剩余的苹果数,plates表示当前剩余的盘子数,ways(apples, plates)表示以apples个苹果放进plates个盘子里的方法数。
  如果apples==0,说明当前苹果都已经放完了,既然放完了,不管剩不剩盘子,这都是一种放的方法,向上一层返回1;
  否则apples不为0的时候,如果plates==0了,盘子已经被用完了但是苹果没放完,这种情况显然是摆放失败了,不是一种摆放的方法,向上一层返回0;
  再考虑一种特殊情况,当盘子数大于苹果数时,那么苹果怎样也不可能放到多出来的盘子上,这种情况下的摆放方法数显然和盘子减少为 p l a t e s − a p p l e s plates-apples platesapples个,apples个苹果的摆放方法数是一样多的,因此
i f ( a p p l e s < p l a t e s ) , w a y s ( a p p l e s , p l a t e s ) = w a y s ( a p p l e s , p l a t e s − a p p l e s ) if (apples <plates),\\ways(apples, plates)=ways(apples,plates-apples) if(apples<plates),ways(apples,plates)=ways(apples,platesapples)
  当剩余的苹果数量大于盘子数量时,我们有两种互斥的摆法
  一种,我们用上所有的盘子,也就是先让所有的盘子都摆上一个苹果,那么这种方式的摆法数量a显然等于 w a y s ( a p p l e s − p l a t e s , p l a t e s ) ways(apples - plates, plates) ways(applesplates,plates);
  另一种方法,我们不用上所有的盘子,那么怎么才能不用上所有的盘子呢?先放弃一个盘子,剩下的盘子是放弃还是保留交给递归来讨论。也就是说,不完全使用所有盘子的摆放方法数量b等于 w a y s ( a p p l e s , p l a t e s − 1 ) ways(apples, plates - 1) ways(apples,plates1).
  这两种情况显然是互斥的,所以他们的方法数可以直接相加,也就是说
i f ( a p p l e s > p l a t e s ) w a y s ( a p p l e s , p l a t e s ) = w a y s ( a p p l e s − p l a t e s , p l a t e s ) + w a y s ( a p p l e s , p l a t e s − 1 ) if (apples>plates)\\ ways(apples,plates)=ways(apples-plates,plates)\\+ways(apples, plates-1) if(apples>plates)ways(apples,plates)=ways(applesplates,plates)+ways(apples,plates1)
代码:

int ways(int apples, int plates) {//apples个完全相同的苹果放到plates个完全相同的盘子里//有多少种方法//如果苹果用完了 说明摆放结束了 返回一种摆法if (apples == 0) {return 1;}//如果plates等于0了 apples不等于0还 那么说明没有盘子用了//0种摆法if (plates == 0) {return 0;}//如果盘子数大于苹果数 那么多出来的盘子不论什么摆法一定空着//这种情况下的摆法数等于把多出来的盘子都不考虑的摆法数if (plates > apples) {return ways(apples, apples);}//当苹果数大于盘子数的时候 有两种方法//1) 我们把所有的盘子都使用 那么相当于先往所有盘子上都放一个苹果// 这种方法的方法数等于ways(apples - plates, plates)int a = ways(apples - plates, plates);//2) 我们让盘子不全都使用 那么就敲碎一个盘子 //剩下的盘子全用还是敲碎一个 总可能方法数用递归去讨论int b = ways(apples, plates - 1);//这两种情况显然是互斥的 所以数量可以直接加return a + b; }

思路2:缓存思想——动态规划来优化暴力递归

  所有的暴力递归的展开过程都可以用动态规划来优化.我们想想递归是怎么解决问题的,比如遇到ways(7, 5),它是展开为ways(7,4)和ways(2,5)来解决的,然后ways(2,5)和ways(7,4)再接着展开,那如果我们之前早就计算过ways(2,5)了呢,如果已经计算过一次了,还有必要再接着展开吗?直接用上次计算的结果不就好了,这样不就可以把递归层数变浅了吗。
  那么怎么记录上次计算的结果呢?这里可以用一个二维数组dp缓存存起来,并且考虑到多组输入问题,我们可以把创建二维数组dp的过程放到执行ways方法外头,这样下一组输入也可以使用我们上一轮计算过的值。
  为了和0种方法区分,我们不妨先让dp的所有值都赋-1,表示尚未计算过,在递归的每一层都检查当前层中dp的是否不等于-1,如果是,说明这层没必要继续展开下去了,已经计算过了,返回 d p [ a p p l e s ] [ p l a t e s ] dp[apples][plates] dp[apples][plates],否则再执行展开过程,并且最后把这一层的计算结果记录到dp中作为缓存。

代码:

#include <vector> #include <iostream> using namespace std; int ways(int apples, int plates, vector<vector<int>>& dp) {if (dp[apples][plates] != -1){return dp[apples][plates];}int ans = 0;if (apples == 0){ans = 1;}else if (plates == 0){ans = 0;}else if (apples < plates){ans = ways(apples, apples, dp);}else{int a = ways(apples - plates, plates, dp);int b = ways(apples, plates - 1, dp);ans = a + b;}dp[apples][plates] = ans;return ans; }int main() {int apples, plates;vector<vector<int>> dp(11, vector<int>(11, -1));while (cin >> apples >> plates){cout << ways(apples, plates, dp) << endl;}return 0; }

总结

以上是如意编程网为你收集整理的算法题放苹果:把M个相同的苹果放到N个完全相同的盘子里,有多少种放法?的全部内容,希望文章能够帮你解决所遇到的问题。

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