您好,登錄后才能下訂單哦!
小編給大家分享一下java中如何實(shí)現(xiàn)求解八枚銀幣,相信大部分人都還不怎么了解,因此分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后大有收獲,下面讓我們一起去了解一下吧!
1、引言
在大學(xué)的算法競(jìng)賽中,遇到過這樣的一個(gè)題目,現(xiàn)在拿出來與大家分享一下:現(xiàn)在有現(xiàn)有八枚銀幣abcdefgh,已知其中一枚是假幣,其重量不同于真幣,但不知是較輕或較重,如何使用天平以最少的比較次數(shù),決定出哪枚是假幣,并得知假幣比真幣較輕或較重。
2、分析
如果本題目只是很單純的求解假幣是哪一個(gè),問題倒并不是很復(fù)雜,只需要回溯遞歸便可求得結(jié)果。問題的難點(diǎn)在意,我們需要用最少的步驟!??!
比之以前的數(shù)據(jù)結(jié)構(gòu)問題,有遞歸,回溯,我們今天可能要接觸一個(gè)新的概念,叫做樹。顧名思義,數(shù)結(jié)構(gòu)就是說我們的分析圖示像樹一樣,有分支節(jié)點(diǎn)等各種信息。樹結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)中的一個(gè)較大的章節(jié),不在我們的討論之中,在本題目當(dāng)中,我們會(huì)介紹樹的一個(gè)小小的分子,決策樹。
我們先建立一下,八個(gè)銀幣求解的數(shù)學(xué)模型。一個(gè)簡單的狀況是這樣的,我們將銀幣依次命名為abcdefg等,我們比較a+b+c與d+e+f,如果相等,則假幣必是g或h,我們先比較g或h哪個(gè)較重,如果g較重,再與a比較(a是真幣),如果g等于a,則g為真幣,則h為假幣,由于h比g輕而g是真幣,則h假幣的重量比真幣輕。
如果不相等呢?又是何種情況,我們將依次分支回溯比較,直到得到最終的答案!
3、示例圖
根據(jù)上面的分析,我們可以有一個(gè)完整的決策樹圖示:
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大或?。?quot;); System.out.println("ex. java Coins 5"); return; } Coins eightCoins = new Coins(); eightCoins.setFake(Integer.parseInt(args[0])); eightCoins.fake(); } }
結(jié)果:
輸入假幣重量(比10大或?。?br/>ex. java Coins 5
這里是一段通用的解題方法,大家可以仔細(xì)琢磨代碼,對(duì)于本段代碼,上面的分析已經(jīng)足夠,剩下的就要大家自己琢磨學(xué)習(xí)了,這樣才能深刻理解。
以上是“java中如何實(shí)現(xiàn)求解八枚銀幣”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對(duì)大家有所幫助,如果還想學(xué)習(xí)更多知識(shí),歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。