称球问题经常是面试中的常客，这里我用递归做了一个称球的程序，贴出来请大家指正。
代码下载：
http://www.blogjava.net/Files/sitinspring/WeighBall20080727160827.zip
WeighingBall类：
package com.heyang;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/** *//**
* 多个球中有一个较重的，用一架天平将其称量出来，求如何分配称球方案使得称球次数最少。
* @author: sitinspring(junglesong@gmail.com)
* @date: 2008-7-26-下午07:51:40
*/
public class WeighingBall
{
/** *//**
* 构造函数
* @param n 球个数
*/
@SuppressWarnings("unchecked")
public WeighingBall(int n){
// 扫描求一个最小值
List<WeighingPlan> plans=new ArrayList<WeighingPlan>();
for(int i=1;i<=n/2;i++){
int times=weighBall(i,n-2*i);
plans.add(new WeighingPlan(i,n-2*i,times));
}
Collections.sort(plans);
// 打印最小称量次数方案
System.out.println(n+"个球的最小称量次数为"+plans.get(0).getWeighedtimes());
System.out.println("\t称量方案有:");
for(WeighingPlan plan:plans){
System.out.println("\t\t"+plan);
}
}
/** *//**
* 分配球
* @param ballCount
* @return
*/
private int assignBall(int ballCount){
if(ballCount<=1){
// 0，1个球直接得出结论
return 0;
}
else if(ballCount<=3){
// 2，3个球还需要再称量一次
return 1;
}
else{
// 重新分配求出最大的数，assignBall和weighBall这两个函数相互调用就是看能走多深的
int max=10000;
for(int i=1;i<=ballCount/2;i++){
int times=weighBall(i,ballCount-2*i);
if(times<max){
max=times;
}
}
return max;
}
}
/** *//**
* 称球
* @param ballCountOnBalance ：天平上的球个数
* @param ballCountOnTable ：剩下的球个数
* @return
*/
private int weighBall(int ballCountOnBalance,int ballCountOnTable){
// 最大称量次数由球个数大的决定
int bigger=ballCountOnBalance>ballCountOnTable?ballCountOnBalance:ballCountOnTable;
// 称一次加一次
return 1+assignBall(bigger);
}
/** *//**
* 程序入口
* @param args
*/
public static void main(String[] args){
//new WeighingBall(16);;
for(int i=3;i<27;i++){
new WeighingBall(i);
}
}
}
WeighingPlan类：
package com.heyang;
/** *//**
* 称量计划类
* @author: sitinspring(junglesong@gmail.com)
* @date: 2008-7-27-下午03:58:01
*/
public class WeighingPlan implements Comparable{
// 天平左右球个数
private int countOnBalance;
// 桌上球个数
private int countOnTable;
// 称量次数
private int weighedtimes;
public WeighingPlan(int countOnBalance,int countOnTable,int weighedtimes){
this.countOnBalance=countOnBalance;
this.countOnTable=countOnTable;
this.weighedtimes=weighedtimes;
}
public int compareTo(Object obj){
WeighingPlan another=(WeighingPlan)obj;
return this.weighedtimes-another.weighedtimes;
}
public String toString(){
return "称量次数为"+weighedtimes+" 称量方案为("+countOnBalance+","+countOnBalance+","+countOnTable+")";
}
public int getCountOnBalance() {
return countOnBalance;
}
public void setCountOnBalance(int countOnBalance) {
this.countOnBalance = countOnBalance;
}
public int getCountOnTable() {
return countOnTable;
}
public void setCountOnTable(int countOnTable) {
this.countOnTable = countOnTable;
}
public int getWeighedtimes() {
return weighedtimes;
}
public void setWeighedtimes(int weighedtimes) {
this.weighedtimes = weighedtimes;
}
}
输出：
3个球的最小称量次数为1
称量方案有:
称量次数为1 称量方案为(1,1,1)
4个球的最小称量次数为2
称量方案有:
称量次数为2 称量方案为(1,1,2)
称量次数为2 称量方案为(2,2,0)
5个球的最小称量次数为2
称量方案有:
称量次数为2 称量方案为(1,1,3)
称量次数为2 称量方案为(2,2,1)
6个球的最小称量次数为2
称量方案有:
称量次数为2 称量方案为(2,2,2)
称量次数为2 称量方案为(3,3,0)
称量次数为3 称量方案为(1,1,4)
7个球的最小称量次数为2
称量方案有:
称量次数为2 称量方案为(2,2,3)
称量次数为2 称量方案为(3,3,1)
称量次数为3 称量方案为(1,1,5)
8个球的最小称量次数为2
称量方案有:
称量次数为2 称量方案为(3,3,2)
称量次数为3 称量方案为(1,1,6)
称量次数为3 称量方案为(2,2,4)
称量次数为3 称量方案为(4,4,0)
9个球的最小称量次数为2
称量方案有:
称量次数为2 称量方案为(3,3,3)
称量次数为3 称量方案为(1,1,7)
称量次数为3 称量方案为(2,2,5)
称量次数为3 称量方案为(4,4,1)
10个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(1,1,8)
称量次数为3 称量方案为(2,2,6)
称量次数为3 称量方案为(3,3,4)
称量次数为3 称量方案为(4,4,2)
称量次数为3 称量方案为(5,5,0)
11个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(1,1,9)
称量次数为3 称量方案为(2,2,7)
称量次数为3 称量方案为(3,3,5)
称量次数为3 称量方案为(4,4,3)
称量次数为3 称量方案为(5,5,1)
12个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(2,2,8)
称量次数为3 称量方案为(3,3,6)
称量次数为3 称量方案为(4,4,4)
称量次数为3 称量方案为(5,5,2)
称量次数为3 称量方案为(6,6,0)
称量次数为4 称量方案为(1,1,10)
13个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(2,2,9)
称量次数为3 称量方案为(3,3,7)
称量次数为3 称量方案为(4,4,5)
称量次数为3 称量方案为(5,5,3)
称量次数为3 称量方案为(6,6,1)
称量次数为4 称量方案为(1,1,11)
14个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(3,3,8)
称量次数为3 称量方案为(4,4,6)
称量次数为3 称量方案为(5,5,4)
称量次数为3 称量方案为(6,6,2)
称量次数为3 称量方案为(7,7,0)
称量次数为4 称量方案为(1,1,12)
称量次数为4 称量方案为(2,2,10)
15个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(3,3,9)
称量次数为3 称量方案为(4,4,7)
称量次数为3 称量方案为(5,5,5)
称量次数为3 称量方案为(6,6,3)
称量次数为3 称量方案为(7,7,1)
称量次数为4 称量方案为(1,1,13)
称量次数为4 称量方案为(2,2,11)
16个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(4,4,8)
称量次数为3 称量方案为(5,5,6)
称量次数为3 称量方案为(6,6,4)
称量次数为3 称量方案为(7,7,2)
称量次数为3 称量方案为(8,8,0)
称量次数为4 称量方案为(1,1,14)
称量次数为4 称量方案为(2,2,12)
称量次数为4 称量方案为(3,3,10)
17个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(4,4,9)
称量次数为3 称量方案为(5,5,7)
称量次数为3 称量方案为(6,6,5)
称量次数为3 称量方案为(7,7,3)
称量次数为3 称量方案为(8,8,1)
称量次数为4 称量方案为(1,1,15)
称量次数为4 称量方案为(2,2,13)
称量次数为4 称量方案为(3,3,11)
18个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(5,5,8)
称量次数为3 称量方案为(6,6,6)
称量次数为3 称量方案为(7,7,4)
称量次数为3 称量方案为(8,8,2)
称量次数为3 称量方案为(9,9,0)
称量次数为4 称量方案为(1,1,16)
称量次数为4 称量方案为(2,2,14)
称量次数为4 称量方案为(3,3,12)
称量次数为4 称量方案为(4,4,10)
19个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(5,5,9)
称量次数为3 称量方案为(6,6,7)
称量次数为3 称量方案为(7,7,5)
称量次数为3 称量方案为(8,8,3)
称量次数为3 称量方案为(9,9,1)
称量次数为4 称量方案为(1,1,17)
称量次数为4 称量方案为(2,2,15)
称量次数为4 称量方案为(3,3,13)
称量次数为4 称量方案为(4,4,11)
20个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(6,6,8)
称量次数为3 称量方案为(7,7,6)
称量次数为3 称量方案为(8,8,4)
称量次数为3 称量方案为(9,9,2)
称量次数为4 称量方案为(1,1,18)
称量次数为4 称量方案为(2,2,16)
称量次数为4 称量方案为(3,3,14)
称量次数为4 称量方案为(4,4,12)
称量次数为4 称量方案为(5,5,10)
称量次数为4 称量方案为(10,10,0)
21个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(6,6,9)
称量次数为3 称量方案为(7,7,7)
称量次数为3 称量方案为(8,8,5)
称量次数为3 称量方案为(9,9,3)
称量次数为4 称量方案为(1,1,19)
称量次数为4 称量方案为(2,2,17)
称量次数为4 称量方案为(3,3,15)
称量次数为4 称量方案为(4,4,13)
称量次数为4 称量方案为(5,5,11)
称量次数为4 称量方案为(10,10,1)
22个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(7,7,8)
称量次数为3 称量方案为(8,8,6)
称量次数为3 称量方案为(9,9,4)
称量次数为4 称量方案为(1,1,20)
称量次数为4 称量方案为(2,2,18)
称量次数为4 称量方案为(3,3,16)
称量次数为4 称量方案为(4,4,14)
称量次数为4 称量方案为(5,5,12)
称量次数为4 称量方案为(6,6,10)
称量次数为4 称量方案为(10,10,2)
称量次数为4 称量方案为(11,11,0)
23个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(7,7,9)
称量次数为3 称量方案为(8,8,7)
称量次数为3 称量方案为(9,9,5)
称量次数为4 称量方案为(1,1,21)
称量次数为4 称量方案为(2,2,19)
称量次数为4 称量方案为(3,3,17)
称量次数为4 称量方案为(4,4,15)
称量次数为4 称量方案为(5,5,13)
称量次数为4 称量方案为(6,6,11)
称量次数为4 称量方案为(10,10,3)
称量次数为4 称量方案为(11,11,1)
24个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(8,8,8)
称量次数为3 称量方案为(9,9,6)
称量次数为4 称量方案为(1,1,22)
称量次数为4 称量方案为(2,2,20)
称量次数为4 称量方案为(3,3,18)
称量次数为4 称量方案为(4,4,16)
称量次数为4 称量方案为(5,5,14)
称量次数为4 称量方案为(6,6,12)
称量次数为4 称量方案为(7,7,10)
称量次数为4 称量方案为(10,10,4)
称量次数为4 称量方案为(11,11,2)
称量次数为4 称量方案为(12,12,0)
25个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(8,8,9)
称量次数为3 称量方案为(9,9,7)
称量次数为4 称量方案为(1,1,23)
称量次数为4 称量方案为(2,2,21)
称量次数为4 称量方案为(3,3,19)
称量次数为4 称量方案为(4,4,17)
称量次数为4 称量方案为(5,5,15)
称量次数为4 称量方案为(6,6,13)
称量次数为4 称量方案为(7,7,11)
称量次数为4 称量方案为(10,10,5)
称量次数为4 称量方案为(11,11,3)
称量次数为4 称量方案为(12,12,1)
26个球的最小称量次数为3
称量方案有:
称量次数为3 称量方案为(9,9,8)
称量次数为4 称量方案为(1,1,24)
称量次数为4 称量方案为(2,2,22)
称量次数为4 称量方案为(3,3,20)
称量次数为4 称量方案为(4,4,18)
称量次数为4 称量方案为(5,5,16)
称量次数为4 称量方案为(6,6,14)
称量次数为4 称量方案为(7,7,12)
称量次数为4 称量方案为(8,8,10)
称量次数为4 称量方案为(10,10,6)
称量次数为4 称量方案为(11,11,4)
称量次数为4 称量方案为(12,12,2)
称量次数为4 称量方案为(13,13,0)