稱球問題經(jīng)常是面試中的常客，這里我用遞歸做了一個(gè)稱球的程序，貼出來請(qǐng)大家指正。
代碼下載：
http://m.tkk7.com/Files/sitinspring/WeighBall20080727160827.zip
WeighingBall類：
package com.heyang;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/** *//**
* 多個(gè)球中有一個(gè)較重的，用一架天平將其稱量出來，求如何分配稱球方案使得稱球次數(shù)最少。
* @author: sitinspring(junglesong@gmail.com)
* @date: 2008-7-26-下午07:51:40
*/
public class WeighingBall
{
/** *//**
* 構(gòu)造函數(shù)
* @param n 球個(gè)數(shù)
*/
@SuppressWarnings("unchecked")
public WeighingBall(int n){
// 掃描求一個(gè)最小值
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);
// 打印最小稱量次數(shù)方案
System.out.println(n+"個(gè)球的最小稱量次數(shù)為"+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個(gè)球直接得出結(jié)論
return 0;
}
else if(ballCount<=3){
// 2，3個(gè)球還需要再稱量一次
return 1;
}
else{
// 重新分配求出最大的數(shù)，assignBall和weighBall這兩個(gè)函數(shù)相互調(diào)用就是看能走多深的
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 ：天平上的球個(gè)數(shù)
* @param ballCountOnTable ：剩下的球個(gè)數(shù)
* @return
*/
private int weighBall(int ballCountOnBalance,int ballCountOnTable){
// 最大稱量次數(shù)由球個(gè)數(shù)大的決定
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;
/** *//**
* 稱量計(jì)劃類
* @author: sitinspring(junglesong@gmail.com)
* @date: 2008-7-27-下午03:58:01
*/
public class WeighingPlan implements Comparable{
// 天平左右球個(gè)數(shù)
private int countOnBalance;
// 桌上球個(gè)數(shù)
private int countOnTable;
// 稱量次數(shù)
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 "稱量次數(shù)為"+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個(gè)球的最小稱量次數(shù)為1
稱量方案有:
稱量次數(shù)為1 稱量方案為(1,1,1)
4個(gè)球的最小稱量次數(shù)為2
稱量方案有:
稱量次數(shù)為2 稱量方案為(1,1,2)
稱量次數(shù)為2 稱量方案為(2,2,0)
5個(gè)球的最小稱量次數(shù)為2
稱量方案有:
稱量次數(shù)為2 稱量方案為(1,1,3)
稱量次數(shù)為2 稱量方案為(2,2,1)
6個(gè)球的最小稱量次數(shù)為2
稱量方案有:
稱量次數(shù)為2 稱量方案為(2,2,2)
稱量次數(shù)為2 稱量方案為(3,3,0)
稱量次數(shù)為3 稱量方案為(1,1,4)
7個(gè)球的最小稱量次數(shù)為2
稱量方案有:
稱量次數(shù)為2 稱量方案為(2,2,3)
稱量次數(shù)為2 稱量方案為(3,3,1)
稱量次數(shù)為3 稱量方案為(1,1,5)
8個(gè)球的最小稱量次數(shù)為2
稱量方案有:
稱量次數(shù)為2 稱量方案為(3,3,2)
稱量次數(shù)為3 稱量方案為(1,1,6)
稱量次數(shù)為3 稱量方案為(2,2,4)
稱量次數(shù)為3 稱量方案為(4,4,0)
9個(gè)球的最小稱量次數(shù)為2
稱量方案有:
稱量次數(shù)為2 稱量方案為(3,3,3)
稱量次數(shù)為3 稱量方案為(1,1,7)
稱量次數(shù)為3 稱量方案為(2,2,5)
稱量次數(shù)為3 稱量方案為(4,4,1)
10個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(1,1,8)
稱量次數(shù)為3 稱量方案為(2,2,6)
稱量次數(shù)為3 稱量方案為(3,3,4)
稱量次數(shù)為3 稱量方案為(4,4,2)
稱量次數(shù)為3 稱量方案為(5,5,0)
11個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(1,1,9)
稱量次數(shù)為3 稱量方案為(2,2,7)
稱量次數(shù)為3 稱量方案為(3,3,5)
稱量次數(shù)為3 稱量方案為(4,4,3)
稱量次數(shù)為3 稱量方案為(5,5,1)
12個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(2,2,8)
稱量次數(shù)為3 稱量方案為(3,3,6)
稱量次數(shù)為3 稱量方案為(4,4,4)
稱量次數(shù)為3 稱量方案為(5,5,2)
稱量次數(shù)為3 稱量方案為(6,6,0)
稱量次數(shù)為4 稱量方案為(1,1,10)
13個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(2,2,9)
稱量次數(shù)為3 稱量方案為(3,3,7)
稱量次數(shù)為3 稱量方案為(4,4,5)
稱量次數(shù)為3 稱量方案為(5,5,3)
稱量次數(shù)為3 稱量方案為(6,6,1)
稱量次數(shù)為4 稱量方案為(1,1,11)
14個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(3,3,8)
稱量次數(shù)為3 稱量方案為(4,4,6)
稱量次數(shù)為3 稱量方案為(5,5,4)
稱量次數(shù)為3 稱量方案為(6,6,2)
稱量次數(shù)為3 稱量方案為(7,7,0)
稱量次數(shù)為4 稱量方案為(1,1,12)
稱量次數(shù)為4 稱量方案為(2,2,10)
15個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(3,3,9)
稱量次數(shù)為3 稱量方案為(4,4,7)
稱量次數(shù)為3 稱量方案為(5,5,5)
稱量次數(shù)為3 稱量方案為(6,6,3)
稱量次數(shù)為3 稱量方案為(7,7,1)
稱量次數(shù)為4 稱量方案為(1,1,13)
稱量次數(shù)為4 稱量方案為(2,2,11)
16個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(4,4,8)
稱量次數(shù)為3 稱量方案為(5,5,6)
稱量次數(shù)為3 稱量方案為(6,6,4)
稱量次數(shù)為3 稱量方案為(7,7,2)
稱量次數(shù)為3 稱量方案為(8,8,0)
稱量次數(shù)為4 稱量方案為(1,1,14)
稱量次數(shù)為4 稱量方案為(2,2,12)
稱量次數(shù)為4 稱量方案為(3,3,10)
17個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(4,4,9)
稱量次數(shù)為3 稱量方案為(5,5,7)
稱量次數(shù)為3 稱量方案為(6,6,5)
稱量次數(shù)為3 稱量方案為(7,7,3)
稱量次數(shù)為3 稱量方案為(8,8,1)
稱量次數(shù)為4 稱量方案為(1,1,15)
稱量次數(shù)為4 稱量方案為(2,2,13)
稱量次數(shù)為4 稱量方案為(3,3,11)
18個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(5,5,8)
稱量次數(shù)為3 稱量方案為(6,6,6)
稱量次數(shù)為3 稱量方案為(7,7,4)
稱量次數(shù)為3 稱量方案為(8,8,2)
稱量次數(shù)為3 稱量方案為(9,9,0)
稱量次數(shù)為4 稱量方案為(1,1,16)
稱量次數(shù)為4 稱量方案為(2,2,14)
稱量次數(shù)為4 稱量方案為(3,3,12)
稱量次數(shù)為4 稱量方案為(4,4,10)
19個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(5,5,9)
稱量次數(shù)為3 稱量方案為(6,6,7)
稱量次數(shù)為3 稱量方案為(7,7,5)
稱量次數(shù)為3 稱量方案為(8,8,3)
稱量次數(shù)為3 稱量方案為(9,9,1)
稱量次數(shù)為4 稱量方案為(1,1,17)
稱量次數(shù)為4 稱量方案為(2,2,15)
稱量次數(shù)為4 稱量方案為(3,3,13)
稱量次數(shù)為4 稱量方案為(4,4,11)
20個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(6,6,8)
稱量次數(shù)為3 稱量方案為(7,7,6)
稱量次數(shù)為3 稱量方案為(8,8,4)
稱量次數(shù)為3 稱量方案為(9,9,2)
稱量次數(shù)為4 稱量方案為(1,1,18)
稱量次數(shù)為4 稱量方案為(2,2,16)
稱量次數(shù)為4 稱量方案為(3,3,14)
稱量次數(shù)為4 稱量方案為(4,4,12)
稱量次數(shù)為4 稱量方案為(5,5,10)
稱量次數(shù)為4 稱量方案為(10,10,0)
21個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(6,6,9)
稱量次數(shù)為3 稱量方案為(7,7,7)
稱量次數(shù)為3 稱量方案為(8,8,5)
稱量次數(shù)為3 稱量方案為(9,9,3)
稱量次數(shù)為4 稱量方案為(1,1,19)
稱量次數(shù)為4 稱量方案為(2,2,17)
稱量次數(shù)為4 稱量方案為(3,3,15)
稱量次數(shù)為4 稱量方案為(4,4,13)
稱量次數(shù)為4 稱量方案為(5,5,11)
稱量次數(shù)為4 稱量方案為(10,10,1)
22個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(7,7,8)
稱量次數(shù)為3 稱量方案為(8,8,6)
稱量次數(shù)為3 稱量方案為(9,9,4)
稱量次數(shù)為4 稱量方案為(1,1,20)
稱量次數(shù)為4 稱量方案為(2,2,18)
稱量次數(shù)為4 稱量方案為(3,3,16)
稱量次數(shù)為4 稱量方案為(4,4,14)
稱量次數(shù)為4 稱量方案為(5,5,12)
稱量次數(shù)為4 稱量方案為(6,6,10)
稱量次數(shù)為4 稱量方案為(10,10,2)
稱量次數(shù)為4 稱量方案為(11,11,0)
23個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(7,7,9)
稱量次數(shù)為3 稱量方案為(8,8,7)
稱量次數(shù)為3 稱量方案為(9,9,5)
稱量次數(shù)為4 稱量方案為(1,1,21)
稱量次數(shù)為4 稱量方案為(2,2,19)
稱量次數(shù)為4 稱量方案為(3,3,17)
稱量次數(shù)為4 稱量方案為(4,4,15)
稱量次數(shù)為4 稱量方案為(5,5,13)
稱量次數(shù)為4 稱量方案為(6,6,11)
稱量次數(shù)為4 稱量方案為(10,10,3)
稱量次數(shù)為4 稱量方案為(11,11,1)
24個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(8,8,8)
稱量次數(shù)為3 稱量方案為(9,9,6)
稱量次數(shù)為4 稱量方案為(1,1,22)
稱量次數(shù)為4 稱量方案為(2,2,20)
稱量次數(shù)為4 稱量方案為(3,3,18)
稱量次數(shù)為4 稱量方案為(4,4,16)
稱量次數(shù)為4 稱量方案為(5,5,14)
稱量次數(shù)為4 稱量方案為(6,6,12)
稱量次數(shù)為4 稱量方案為(7,7,10)
稱量次數(shù)為4 稱量方案為(10,10,4)
稱量次數(shù)為4 稱量方案為(11,11,2)
稱量次數(shù)為4 稱量方案為(12,12,0)
25個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(8,8,9)
稱量次數(shù)為3 稱量方案為(9,9,7)
稱量次數(shù)為4 稱量方案為(1,1,23)
稱量次數(shù)為4 稱量方案為(2,2,21)
稱量次數(shù)為4 稱量方案為(3,3,19)
稱量次數(shù)為4 稱量方案為(4,4,17)
稱量次數(shù)為4 稱量方案為(5,5,15)
稱量次數(shù)為4 稱量方案為(6,6,13)
稱量次數(shù)為4 稱量方案為(7,7,11)
稱量次數(shù)為4 稱量方案為(10,10,5)
稱量次數(shù)為4 稱量方案為(11,11,3)
稱量次數(shù)為4 稱量方案為(12,12,1)
26個(gè)球的最小稱量次數(shù)為3
稱量方案有:
稱量次數(shù)為3 稱量方案為(9,9,8)
稱量次數(shù)為4 稱量方案為(1,1,24)
稱量次數(shù)為4 稱量方案為(2,2,22)
稱量次數(shù)為4 稱量方案為(3,3,20)
稱量次數(shù)為4 稱量方案為(4,4,18)
稱量次數(shù)為4 稱量方案為(5,5,16)
稱量次數(shù)為4 稱量方案為(6,6,14)
稱量次數(shù)為4 稱量方案為(7,7,12)
稱量次數(shù)為4 稱量方案為(8,8,10)
稱量次數(shù)為4 稱量方案為(10,10,6)
稱量次數(shù)為4 稱量方案為(11,11,4)
稱量次數(shù)為4 稱量方案為(12,12,2)
稱量次數(shù)為4 稱量方案為(13,13,0)