快捷導(dǎo)航

java編程實(shí)現(xiàn)求解八枚銀幣代碼分享

更新時(shí)間：2017年11月30日 17:10:53 作者：ljtyzhr

這篇文章主要介紹了java編程實(shí)現(xiàn)求解八枚銀幣代碼分享，具有一定參考價(jià)值，需要的朋友可以了解下。

1、引言

筆者在大學(xué)的算法競(jìng)賽中，遇到過(guò)這樣的一個(gè)題目，現(xiàn)在拿出來(lái)與大家分享一下：現(xiàn)在有現(xiàn)有八枚銀幣abcdefgh，已知其中一枚是假幣，其重量不同于真幣，但不知是較輕或較重，如何使用天平以最少的比較次數(shù)，決定出哪枚是假幣，并得知假幣比真幣較輕或較重。

2、分析

如果本題目只是很單純的求解假幣是哪一個(gè)，問(wèn)題倒并不是很復(fù)雜，只需要回溯遞歸便可求得結(jié)果。問(wèn)題的難點(diǎn)在意，我們需要用最少的步驟！??！

比之以前的數(shù)據(jù)結(jié)構(gòu)問(wèn)題，有遞歸，回溯，我們今天可能要接觸一個(gè)新的概念，叫做樹(shù)。顧名思義，數(shù)結(jié)構(gòu)就是說(shuō)我們的分析圖示像樹(shù)一樣，有分支節(jié)點(diǎn)等各種信息。樹(shù)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)中的一個(gè)較大的章節(jié)，不在我們的討論之中，在本題目當(dāng)中，我們會(huì)介紹樹(shù)的一個(gè)小小的分子，決策樹(shù)。

我們先建立一下，八個(gè)銀幣求解的數(shù)學(xué)模型。一個(gè)簡(jiǎn)單的狀況是這樣的，我們將銀幣依次命名為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è)完整的決策樹(shù)圖示：

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(); 
  } 
}

結(jié)果：

輸入假幣重量（比10大或?。?br /> ex. java Coins 5

這里是一段通用的解題方法，大家可以仔細(xì)琢磨代碼，對(duì)于本段代碼，上面的分析已經(jīng)足夠，剩下的就要大家自己琢磨學(xué)習(xí)了，這樣才能深刻理解。

總結(jié)

以上就是本文關(guān)于java編程實(shí)現(xiàn)求解八枚銀幣代碼分享的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！

您可能感興趣的文章: