java編程實現(xiàn)求解八枚銀幣代碼分享
1、引言
筆者在大學的算法競賽中，遇到過這樣的一個題目，現(xiàn)在拿出來與大家分享一下：現(xiàn)在有現(xiàn)有八枚銀幣abcdefgh，已知其中一枚是假幣，其重量不同于真幣，但不知是較輕或較重，如何使用天平以最少的比較次數(shù)，決定出哪枚是假幣，并得知假幣比真幣較輕或較重。
2、分析
如果本題目只是很單純的求解假幣是哪一個，問題倒并不是很復雜，只需要回溯遞歸便可求得結果。問題的難點在意，我們需要用最少的步驟！?。?/p>
比之以前的數(shù)據(jù)結構問題，有遞歸，回溯，我們今天可能要接觸一個新的概念，叫做樹。顧名思義，數(shù)結構就是說我們的分析圖示像樹一樣，有分支節(jié)點等各種信息。樹結構是數(shù)據(jù)結構中的一個較大的章節(jié)，不在我們的討論之中，在本題目當中，我們會介紹樹的一個小小的分子，決策樹。
我們先建立一下，八個銀幣求解的數(shù)學模型。一個簡單的狀況是這樣的，我們將銀幣依次命名為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、代碼
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();
}
}
結果：
輸入假幣重量（比10大或?。?br />
ex. java Coins 5
這里是一段通用的解題方法，大家可以仔細琢磨代碼，對于本段代碼，上面的分析已經足夠，剩下的就要大家自己琢磨學習了，這樣才能深刻理解。
總結
以上就是本文關于java編程實現(xiàn)求解八枚銀幣代碼分享的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
相關文章
前端有一個神器——canvas，這個畫布標簽可以處理各種圖片的合成，可以精確到圖片的具體坐標。java后端也有這樣的神器，那就是image-combiner，可以很簡單的合成圖片，感興趣的可以試一試2022-01-01
下面小編就為大家?guī)硪黄獪\談foreach寫失效的問題。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-07-07
SpringBoot集成SpringSecurity和JWT做登陸鑒權的實現(xiàn)
這篇文章主要介紹了SpringBoot集成SpringSecurity和JWT做登陸鑒權的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-04-04
Spring mvc JSON數(shù)據(jù)交換格式原理解析
這篇文章主要介紹了Spring mvc JSON數(shù)據(jù)交換格式原理解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-03-03
springBoot配置國產達夢數(shù)據(jù)庫的示例詳解
本文向大家介紹springBoot?配置國產達夢數(shù)據(jù)庫的相關知識，文章結合示例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-04-04
這篇文章主要為大家詳細介紹了Maven安裝步驟，及MyEclipse中如何使用Maven，感興趣的小伙伴們可以參考一下2016-07-07
SpringBoot?@Scheduled?Cron表達式使用方式
這篇文章主要介紹了SpringBoot?@Scheduled?Cron表達式使用方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2025-03-03
大家好，本篇文章主要講的是java中JDBC增刪改查操作詳解，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
本篇文章主要介紹了java多線程之定時器Timer的使用詳解，Time類主要負責完成定時計劃任務的功能,有興趣的可以了解一下。2017-04-04
這篇文章主要介紹了Java之理解Redis回收算法LRU案例講解,本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-08-08