题目:
把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; }