優化的基於時間的算法

Question

我正在寫一個算法對於這個問題，算法很簡單，我已經寫的代碼，但我看不到任何可能的優化：

我有一個有100個石頭和5個使用它來裝飾沙堡的小孩。 每個孩子反覆拿起一塊石頭每一定的時間跨度，每個孩子都是獨立於他人，更多的孩子可以拿起在同一時間一塊石頭，有5個孩子合計：

• 埃裏克挑一塊石頭，每5分鐘
• 馬克拿起石每10分鐘
• 拉拉拿起石每7分鐘
• 艾瑪拿起石每3分鐘
• 弗蘭克拿起石每3分鐘

我們需要多少分鐘才​​能清空存儲桶？要更加清楚：10分鐘後，埃裏克有兩塊石頭（分鐘5和分鐘10），而艾瑪有3塊石頭（分鐘3,6和9）。

所以，10分鐘後的兒童有總共2 + 1 + 1 + 3 + 3 = 10結石，有90個結石剷鬥

這是我的代碼（Python 3中）：

children_rate = [3, 3, 5, 7, 10] 
bucket = 100 

minutes = 0 

while True: 
    minutes += 1 
    for child in children_rate: 
     if minutes % child == 0: 
      bucket -= 1 
      if bucket == 0: 
       print('bucket empty in',minutes,'minutes') 
       exit() 

此代碼有效，在這種情況下，所需的分鐘數是91，但我不能使用此代碼處理一百萬個石頭和500個孩子的桶。

我可以看到的唯一優化是在總和/加操作中轉換mod操作，因爲分割/乘法更昂貴。我可以使用numpy數組等等，但沒有什麼能夠真正加速這個過程。

我試着將問題適應於我的算法教科書中描述的一些典型的知識問題，但沒有運氣。

Answer 1

有一兩件事你可以做的是對的答案二進制搜索。

假設答案是X分鐘。 然後你知道每個孩子在那段時間會帶多少石頭。 如果結果總數少於預期，X需要更高。 否則，在下半部分搜索。

在代碼：

children_rate = [3, 3, 5, 7, 10] 
bucket = 100 

lo, hi = 0, bucket * max (children_rate) 
while lo < hi: 
    me = (lo + hi) // 2 
    if sum (me // i for i in children_rate) < bucket: 
     lo = me + 1 
    else: 
     hi = me 

print (lo) 

Answer 2

您可以調整算法，以便在給定的分鐘數內計算所有孩子已經使用了多少寶石。

def compute_stones(minutes) 
    stones = 0 
    for child in children_rate: 
     stones += minutes // child # integer division 
    return stones 

然後，你可以做一個二進制印章找到分鐘的編號，在這些石頭= 100

Answer 3

每個孩子挑選在一段時間石頭，所有的孩子一起撿石頭，其中有一個週期，以及一些模式。這種模式的時期是每個孩子時期的Least common multiple。它可以用幾種方法計算，但在這種情況下，我們使用每個週期的因子分解。

3 = 3 
5 =  5 
7 =  7 
10 = 2 * 5 

所以常見的時期是210 = 2 * 3 * 5 * 7。在這段時間裏，埃裏克挑選42塊石頭，馬克挑選21塊石頭，拉拉挑選30塊石頭，埃瑪和弗蘭克挑選70塊石頭。這是每210分鐘233石頭。如果你在一個桶裏有100萬塊石頭，他們會在901110分鐘內挑出999803塊石頭，然後你將運行你原來的代碼，用於其餘的197塊石頭。很簡單，不是嗎？