春风博客

春天里,百花香...

导航

<2008年7月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

统计

公告

MAIL: junglesong@gmail.com
MSN: junglesong_5@hotmail.com

Locations of visitors to this page

常用链接

留言簿(11)

随笔分类(224)

随笔档案(126)

个人软件下载

我的其它博客

我的邻居们

最新随笔

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

用递归和扫描解决称球问题

称球问题经常是面试中的常客,这里我用递归做了一个称球的程序,贴出来请大家指正。

代码下载:
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)

posted on 2008-07-27 00:11 sitinspring 阅读(1192) 评论(2)  编辑  收藏 所属分类: 算法数据结构

评论

# re: 用递归和扫描解决称球问题 2008-07-28 01:10 yegong

没这么简单
最简单的秤球问题有两种
1. 有一坏球,不知轻重,此外还有一标准球
2. 有3个球,知到坏球轻还是重

简单的这样划分个数是没有意义的
至少要给出每一步左右盘上的编号  回复  更多评论   

# re: 用递归和扫描解决称球问题 2008-07-28 09:31 Jacky-Q

已知异常球是过重还是过轻的情况下,称量次数是logN/log3,这个算是标准答案了。  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航:
 
sitinspring(http://www.blogjava.net)原创,转载请注明出处.