สมมติว่ามี 1,000 ถัง อันหนึ่งเป็นพิษ อีกอันเต็มไปด้วยน้ำ พวกเขาทั้งหมดดูคล้ายกัน ถ้าหมูกินยาพิษมันจะตายภายใน 15 นาที จำนวนสุกรขั้นต่ำที่เราต้องหาถังพิษภายในหนึ่งชั่วโมงจะเป็นเท่าใด?
ตอนนี้ให้พิจารณากรณีทั่วไปและกำหนดอัลกอริทึมสำหรับสิ่งนี้ กรณีทั่วไปคือ หากมี n ถังต่างกันและพิษของสุกรจะตายภายใน 1 นาที ต้องใช้หมูกี่ตัวในการหาถังพิษภายใน p นาที? มีถังพิษอยู่หนึ่งถัง
เมื่อ n =1,000, m =15 และ p =60 ผลลัพธ์จะเป็น 5
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ret :=0
- ในขณะที่ (minutesToTest / minutesToDie + 1)^ret
- (เพิ่มการถอนคืนโดย 1)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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
