識別假幣問題：在n枚外觀相同的假幣中，有一枚是假幣。在一架天平上，我們可以比較任意兩組假幣。也就是說，通過觀察天平是向右傾、向左傾還是停在當(dāng)中，我們可以判斷出兩組硬幣重量是否相同，或者哪一組比另一組更重，但是我們不知道重多少。問題是：設(shè)計(jì)一種有效的算法來檢測出這枚假幣。

簡化版本：已知假幣相對真幣較輕或者較重；

普通版本：不知道假幣輕還是重

除了每次把硬幣分為2份的辦法，還可以用更加高效的把硬幣分為三堆，每堆n/3個硬幣，在比較了兩堆硬幣的重量之后我們可以把實(shí)例的規(guī)模小區(qū)一個因子3. 相應(yīng)的，我們可以期望稱重的次數(shù)大約會是log3 n

設(shè)計(jì)一種可以處理任何是或不是3的倍數(shù)個硬幣的算法

偽代碼如下：

每次平均分三堆的結(jié)果可能有：余數(shù)0 余數(shù)1 余數(shù)2

如果余數(shù)0:

平均分，任選兩堆(堆1+堆2)比較，

如果平衡：

堆3含假幣；

如果不平衡：

比較堆1和堆3，

如果平衡：

堆2含假幣，

如果不平衡：

堆1含假幣；

余數(shù)1:

平均分后得到3堆+1個硬幣，任選兩堆(堆1+堆2)比較，

如果平衡：

比較堆1和堆3，

如果平衡：

剩余的單個硬幣為假，

如果不平衡：

堆3為含假幣的堆

如果不平衡：

比較堆1和堆3，

如果平衡：

堆2含假幣

如果不平衡：

堆1含假幣

余數(shù)2:

平均分后得到3堆+1個硬幣，任選兩堆(堆1+堆2)比較，

如果平衡：

比較堆1和堆3

如果平衡：

假幣在兩個單個硬幣中，這兩個硬幣必然是不平衡的，這時從堆中找出任意一枚硬幣，從兩個單個硬幣中拿出硬幣1進(jìn)行比較

如果平衡

假幣為幣2

如果不平衡

假幣為幣1

如果不平衡：

堆3為含假幣的堆

如果不平衡：

比較堆1和堆3

如果平衡：

堆2含假幣

如果不平衡：

堆1含假幣

分為堆1，堆2，堆3，余數(shù)k

如果堆123數(shù)目為0

if k=0

if k=1

if k=2

Else

if 堆1和堆2平衡：

if 堆1和堆3平衡，

findOutFake(k)

else

findOutFake(堆3)

else：

if 堆1和堆3平衡，

findOutFake(堆2)

else

findOutFake(堆1)

總結(jié)

以上是生活随笔為你收集整理的java 假币问题_减治法解决假币问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。