Giả sử có 1000 cái xô, trong đó có một cái thùng chứa chất độc, những cái thùng khác đựng đầy nước. Tất cả chúng đều trông giống nhau. Nếu một con lợn uống phải chất độc, nó sẽ chết trong vòng 15 phút. Số lượng lợn tối thiểu mà chúng ta cần để tìm ra cái xô độc trong vòng một giờ là bao nhiêu?
Vì vậy, bây giờ hãy xem xét cho trường hợp chung và đưa ra một thuật toán cho điều này. Vậy trường hợp tổng quát là Nếu có n cái xô khác nhau và một con lợn uống phải chất độc sẽ chết trong vòng m phút thì cần bao nhiêu con lợn để tìm ra cái xô độc trong vòng p phút? Có đúng một thùng chứa chất độc.
Khi n =1000, m =15 và p =60, thì sản lượng sẽ là 5.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- ret:=0
- while (minutesToTest / minutesToDie + 1) ^ ret
- (tăng ret thêm 1)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
1000 15 60
Đầu ra
5