模擬使用陣列的假硬幣

有70個硬幣，其中有一個假硬幣。需要以最少的稱量數量檢測假幣。你只有一個體重秤，你知道假硬幣更輕。模擬使用陣列的假硬幣

我不確定下面的問題的模擬是對還是錯，即在數組中表示它並進行比較，就像我在代碼中所做的那樣。我試圖用一個數組來模擬它，除了一個零被認爲是假硬幣。以下是我的代碼。請讓我知道，如果我錯了。

如果有人能夠證明/解釋爲什麼三分法在簡單的數學中更好，這將是非常有幫助的。

爲下面的代碼

僞代碼：

INPUT : integer n 

if n = 1 then 
    the coin is fake 
else 
    divide the coins into piles of A = ceiling(n/3), B = ceiling(n/3), 
     and C = n-2*ceiling(n/3) 
    weigh A and B 
    if the scale balances then 
     iterate with C 
    else 
     iterate with the lighter of A and B

代碼：

import random 

def getmin(data, start, end, total_items): 
    if total_items == 1: 
     #for sure we have a fake coin 
     return (0, start) 
    elif total_items == 2: 
     if data[start] > data[end]: 
      return (1, end) 
     elif data[start] < data[end]: 
      return (1, start) 
    else: 
     partition = total_items/3 
     a_weight = sum(data[start:start+partition]) 
     b_weight = sum(data[start+partition:start+2*partition]) 
     c_weight = sum(data[start+2*partition:end]) 
     if a_weight == b_weight: 
      result = getmin(data, start+2*partition, end, end-(start+2*partition)) 
      return (1+result[0], result[1]) 
     else: 
      if a_weight > b_weight: 
       result = getmin(data, start+partition, start+2*partition, partition) 
       return (1+result[0], result[1]) 
      else: 
       result = getmin(data, start, start+partition, partition) 
       return (1+result[0], result[1]) 

n = int(raw_input()) 
data = [1]*n 
data[random.randint(0, n-1)] = 0 
total_weighing, position = getmin(data, 0, len(data), len(data)) 
print(total_weighing, position)

來源

2016-09-25 newbie_old

如果您尚未確定是否有問題，則不應發佈。爲您測試程序不在SO的範圍內。簡單的代碼審查屬於codereview網站。 – Prune

@Prune我不想檢查我的程序。我正在檢查我的陣列模擬是否是解決假硬幣問題的正確方法。代碼只是爲了更好地說明我的問題。 –

明白了;謝謝。我收回了我的近距離投票，並且我會在我的答案中編輯該部分。 – Prune

你問「爲什麼三分法在簡單的數學中更好」。好於什麼？在這個問題上，這是最好的解決方案，因爲它可以在最少的稱量中實現答案。瑣碎平衡量表的特性產生了三個基本結果：左邊更重，右邊更重，等重。這是一個三方決策，因此信息理論認爲最好的算法是在每個階段將對象分成三部分（如果實際上可以實現的話）。

您需要對28-81個硬幣進行4次稱量。

幸運的是，您的問題允許進行詳盡的測試。上面的代碼執行一次隨機測試。對於初學者來說這沒問題，但只有70個案例需要檢查，我建議您嘗試一下。在一個循環中總結主程序超範圍（70），這樣的事情：

n = 70 
for bad_coin in range(70): 
    data = [1]*n 
    data[bad_coin] = 0 
    total_weighing, position = getmin(data, 0, n, n) 
    print ("trial", bad_coin) 
    if total_weighing != 4: 
     print ("Wrong number of weighings:", total_weighing) 
    if position != bad_coin: 
     print ("Wrong ID:", position)

這很快就會顯示出你的程序中的任何錯誤分配的70個硬幣。

BTW，與斷言更換如果語句，如果你熟悉這個功能。

來源

2016-09-26 17:14:39 Prune

謝謝，但我已經測試過它，它適用於所有情況。我只是想確認我的解決方案是否是模擬假幣和真幣的正確方法。 http://puzzling.stackexchange.com/questions/18/learning-to-solve-a-river-crossing-puzzle如果你看到圖論是用來模擬問題並解決它的。同樣的方式，我想知道如果我的陣列模擬是最好的方法來處理它。 –

它的工作原理很容易理解和維護，而且效率很高。是的，這是解決問題的有效方法。 – Prune

的這種算法的複雜度O（登錄 N）因爲你減少你的問題大小每次迭代1/3。複雜明智爲O（log （n））的 == 爲O（log 2 （n））的 == 爲O（log （n））的所以不管doen't您將問題大小除以3或10. 只有更好的複雜性是O（1）這意味着無論問題的大小，您都可以在固定數量的操作中找到假幣，這是不太可能的。注意，在這個算法中，我們假設我們可以找到O（1）中元素範圍的總和，否則算法的複雜度是O（n）。

來源

2016-09-25 18:17:03 Tempux

你剛纔談到了複雜性，但是如何用數組和代碼模擬呢？你認爲我說得對嗎？ –

看起來不錯。但要確定你需要對很多不同的測試進行測試。 – Tempux

一個小小的問題 - 「唯一更好的複雜性是O（1）」並不是真的。「有關反例，請參閱http://stackoverflow.com/a/16472013/2166798。 – pjs

模擬使用陣列的假硬幣

回答

相關問題