球大神们的解决思路

Question

魔术师有m个碗每个碗可以放n个小球 现在共有X个小球 小球的大小一样 请问有多少种放法  求解决思路

Answer 1

public class Andy {

public static void main(String[] args) {
int boxCount = 5; //有5个盒子
int[] boxs = new int[boxCount];
int cap = 3; //每个盒子容量是3
int ball = 10; //共有10个球

int count = putBallInBox(0, boxs, cap, ball);
System.out.println("共有 "+count+" 种放置方法");
}

//本函数规定，每个盒子至少放1个球
private static int putBallInBox(int index, int[] a, int cap, int ball) {
int start;
int count = 0;
int leftBall = ball;
//计算当前还剩多少球
for(int i=0; i<index; i++) {
leftBall -= a[i];
}

//如果一个球都不剩了，则此套方案失败，返回0
if(leftBall<=0) {
return 0;
} //如果正在考察最后一个盒子
if(index == a.length-1) {
//如果剩余的球少于盒子容量上限
if(leftBall<=cap) {
//则打印显示此放置方案，并返回1
a[index] = leftBall;
for(int i=0; i<a.length; i++) {
System.out.print(a[i]+" ");
}
System.out.println();
return 1;
}else { //反之，此方案不可行，返回0
return 0;
}
}

//假设后面的盒子全放满，则当前盒子最少放多少个球
start = leftBall - (a.length - index - 1) * cap;
if(start>cap) { //若最少也要超过盒子容量上限，则此方案失败，回溯
return 0;
}else if(start <1) {//若其值小于等于0，则将其修真恶搞为1，因为至少要放1个球
start = 1;
}
//开始递归调用
for(int i=start; i<=cap; i++) {
a[index] = i;
count += putBallInBox(index+1, a, cap, ball);
}
return count;
}
}