สมมุติว่าเรากำลังเล่นเกม Guess คุณสมบัติของเกมนี้มีดังนี้ -
ผู้เล่น 1 จะเลือกตัวเลขตั้งแต่ 1 ถึง n ผู้เล่น 2 ต้องเดาว่าผมเลือกหมายเลขอะไร ทุกครั้งที่ผู้เล่น2เดาผิด ผู้เล่น1จะบอกผู้เล่น2ว่าตัวเลขสูงหรือต่ำ
เราสามารถใช้ฟังก์ชัน Guess(num) ซึ่งจะให้ผลลัพธ์ที่เป็นไปได้ 3 แบบดังนี้ −
-
-1 - ผู้เล่นหมายเลข 1 ต่ำกว่า
-
1 - ผู้เล่นหมายเลข 1 สูงกว่า
-
0 - ตัวเลขตรงกัน
ดังนั้น หากอินพุตเท่ากับ n =10 เลือก =5 ผลลัพธ์จะเป็น 5
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ล :=1,r :=น
-
ในขณะที่ l −=r ทำ −
-
m :=l+(r - l)/2
-
ถ้า Guess(m) เท่ากับ 0 แล้ว −
-
กลับม
-
-
ถ้า Guess(m) เหมือนกับ -1 แล้ว −
-
r :=m - 1
-
-
มิฉะนั้น
-
l :=m + 1
-
-
-
คืนค่า 0
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
int number;
int guess(int num){
if(number > num)
return 1;
if(number < num)
return -1;
return 0;
}
public:
Solution(int n){
number = n;
}
int guessNumber(int n) {
int l=1,r=n,m;
while(l<=r){
m=l+(r-l)/2;
if(guess(m)==0)
return m;
if(guess(m)==-1)
r=m-1;
else
l=m+1;
}
return 0;
}
};
main(){
Solution ob(5); //pick = 5
cout << (ob.guessNumber(10));
} อินพุต
5,10
ผลลัพธ์
5
