C++ 中的豬圈問題

假設有 1000 個水桶，其中一個裝有毒藥，其他的裝滿了水。它們看起來都一樣。如果豬喝了毒藥，它會在 15 分鐘內死亡。我們需要至少多少頭豬才能在一小時內找出有毒的水桶？

現在考慮一般情況併為此設計一個演算法。一般情況是，如果有 n 個不同的水桶，並且豬喝了毒藥會在 m 分鐘內死亡，那麼在 p 分鐘內找到有毒水桶需要多少頭豬？只有一個水桶有毒。

當 n = 1000，m = 15 且 p = 60 時，輸出將為 5。

為了解決這個問題，我們將遵循以下步驟 -

  • ret := 0
  • 當 (測試時間 / 致死時間 + 1)^ret < 水桶數量 時，執行 -
    • (ret 加 1)
  • 返回 ret

讓我們看看以下實現以更好地理解 -

示例

 線上演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
      int ret = 0;
      while(pow((minutesToTest / minutesToDie + 1), ret) < buckets) ret++;
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.poorPigs(1000,15,60));
}

輸入

1000
15
60

輸出

5

更新於: 2020-06-01

164 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告