1、引言
筆者在大學(xué)的算法競賽中，遇到過這樣的一個題目，現(xiàn)在拿出來與大家分享一下：現(xiàn)在有現(xiàn)有八枚銀幣abcdefgh，已知其中一枚是假幣，其重量不同于真幣，但不知是較輕或較重，如何使用天平以最少的比較次數(shù)，決定出哪枚是假幣，并得知假幣比真幣較輕或較重。
2、分析
如果本題目只是很單純的求解假幣是哪一個，問題倒并不是很復(fù)雜，只需要回溯遞歸便可求得結(jié)果。問題的難點在意，我們需要用最少的步驟！！！
比之以前的數(shù)據(jù)結(jié)構(gòu)問題，有遞歸，回溯，我們今天可能要接觸一個新的概念，叫做樹。顧名思義，數(shù)結(jié)構(gòu)就是說我們的分析圖示像樹一樣，有分支節(jié)點等各種信息。樹結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)中的一個較大的章節(jié)，不在我們的討論之中，在本題目當(dāng)中，我們會介紹樹的一個小小的分子，決策樹。
我們先建立一下，八個銀幣求解的數(shù)學(xué)模型。一個簡單的狀況是這樣的，我們將銀幣依次命名為abcdefg等，我們比較a+b+c與d+e+f，如果相等，則假幣必是g或h，我們先比較g或h哪個較重，如果g較重，再與a比較（a是真幣），如果g等于a，則g為真幣，則h為假幣，由于h比g輕而g是真幣，則h假幣的重量比真幣輕。
如果不相等呢？又是何種情況，我們將依次分支回溯比較，直到得到最終的答案！
3、示例圖
根據(jù)上面的分析，我們可以有一個完整的決策樹圖示：
4、代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
public class coins { private int[] coins; public coins() { coins = new int[8]; for(int i = 0; i < 8; i++) coins[i] = 10; } public void setfake(int weight) { coins[(int) (math.random() * 7)] = weight; } public void fake() { if(coins[0]+coins[1]+coins[2] == coins[3]+coins[4]+coins[5]) { if(coins[6] > coins[7]) compare(6, 7, 0); else compare(7, 6, 0); } else if(coins[0]+coins[1]+coins[2] > coins[3]+coins[4]+coins[5]) { if(coins[0]+coins[3] == coins[1]+coins[4]) compare(2, 5, 0); else if(coins[0]+coins[3] > coins[1]+coins[4]) compare(0, 4, 1); if(coins[0]+coins[3] < coins[1]+coins[4]) compare(1, 3, 0); } else if(coins[0]+coins[1]+coins[2] < coins[3]+coins[4]+coins[5]) { if(coins[0]+coins[3] == coins[1]+coins[4]) compare(5, 2, 0); else if(coins[0]+coins[3] > coins[1]+coins[4]) compare(3, 1, 0); if(coins[0]+coins[3] < coins[1]+coins[4]) compare(4, 0, 1); } } protected void compare(int i, int j, int k) { if(coins[i] > coins[k]) system.out.print("\n假幣 " + (i+1) + " 較重"); else system.out.print("\n假幣 " + (j+1) + " 較輕"); } public static void main(string[] args) { if(args.length == 0) { system.out.println("輸入假幣重量（比10大或小）"); system.out.println("ex. java coins 5"); return; } coins eightcoins = new coins(); eightcoins.setfake(integer.parseint(args[0])); eightcoins.fake(); } } |
結(jié)果：
輸入假幣重量（比10大或小）
ex. java coins 5
這里是一段通用的解題方法，大家可以仔細(xì)琢磨代碼，對于本段代碼，上面的分析已經(jīng)足夠，剩下的就要大家自己琢磨學(xué)習(xí)了，這樣才能深刻理解。
總結(jié)
以上就是本文關(guān)于java編程實現(xiàn)求解八枚銀幣代碼分享的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://blog.csdn.net/ljtyzhr/article/details/39274059
