ধরুন আমরা গেস গেম খেলছি। এই গেমের বৈশিষ্ট্যগুলি নিম্নরূপ -
প্লেয়ার 1 1 থেকে n পর্যন্ত একটি সংখ্যা বেছে নেবে। player2 অনুমান করতে হবে আমি কোন সংখ্যাটি বেছে নিয়েছি। প্রতিবার প্লেয়ার2 ভুল অনুমান করলে, প্লেয়ার1 প্লেয়ার2কে বলবে যে সংখ্যা বেশি নাকি কম।
আমরা guess(num) ফাংশনটি ব্যবহার করতে পারি যা নিম্নরূপ −
3টি সম্ভাব্য ফলাফল প্রদান করবে-
-1 − প্লেয়ার1 এর সংখ্যা কম
-
1 − প্লেয়ার1 এর সংখ্যা বেশি
-
0 − সংখ্যা মিলেছে
সুতরাং, যদি ইনপুট n =10 এর মত হয়, পিক =5, তাহলে আউটপুট 5 হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
l :=1,r :=n
-
যখন l −=r, do −
-
m :=l+(r - l)/2
-
যদি অনুমান(m) 0 এর সমান হয়, তাহলে −
-
ফিরুন m
-
-
যদি অনুমান(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
