分苹果的算法
2021/10/30 11:11:03
本文主要是介绍分苹果的算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目:
把M个一样的苹果放在N个同样的盘子里,允许盘子空着不放,问共有多少种不同的分法?
N<=10。
测试样例:
7个苹果、3个盘子,有8种放发。
说明:
5,1,1和1,5,1算同样的分法。即盘子是无差别的盘子,苹果也是一样的苹果。
参考答案是使用递归算法,有点难度。
下面是一种简单粗暴的近似算法:蒙特卡罗算法。在苹果、盘子不多的情况下效果良好。
public static int force(int apples, int plates) { //蒙特卡罗算法 HashSet<String> set = new HashSet<>(); //set用于统计分配方案 int[] array = new int[plates]; //数组模拟盘子 Random rnd = new Random(); //随机数 for (int i=0; i<2000_0000; i++) { Arrays.fill(array,0); int balance = apples; //剩余苹果数 for (int j=0; j<plates-1; j++) { //随机给盘子分苹果 int x = rnd.nextInt(balance+1); array[j] = x; balance =balance - x; if (balance == 0) { //苹果已经分完,提前结束 break; } } array[plates-1]=balance; //剩余苹果放到最后一个盘子里 Arrays.sort(array); set.add(Arrays.toString(array)); } return set.size(); }
参考答案:递归算法。
public static int f(int apples, int plates) { //递归算法 if (apples <= 0) { return 1; //没有苹果(盘子有剩)也算一种方案 } if (plates <=0) { return 0; //没有盘子(苹果有剩)不算方案 } if (plates > apples) { return f(apples, apples); //盘子过多,直接去掉多余盘子 } int sum0 = f(apples, plates-1); //要么有一个盘子退出分配 int sum1 = f(apples-plates, plates); //要么每盘先预留一个苹果 return sum0 + sum1; }
这篇关于分苹果的算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南
- 2024-09-26Springboot微服务资料入门教程