我无法用 C/C++ 编写二进制算法。
我的问题是这样的:
应用二进制算法在数字猜谜游戏中搜索从 1 到 100 的数字。
用户将回答“y”以表示正确猜测,“h”如果猜测太高,或者“l”如果猜测太低。
我没有任何想法来应用它。谁能给我一个代码示例。
我无法用 C/C++ 编写二进制算法。
我的问题是这样的:
应用二进制算法在数字猜谜游戏中搜索从 1 到 100 的数字。
用户将回答“y”以表示正确猜测,“h”如果猜测太高,或者“l”如果猜测太低。
我没有任何想法来应用它。谁能给我一个代码示例。
此处的详细说明以及各种实现。
int low = 1;
int high = 100;
while (low <= high) {
int mid = (low + high) / 2;
char answer = evaluateGuess(mid); //return l, h or y;
if ('y'==answer) {
return mid;
}
if ('l' == answer) {
low = mid + 1;
} else {
high = mid - 1;
}
}
// If you get here the human player lied and the answer wasn't in [1..100]
我假设您的意思是二进制搜索。维基百科有大量信息。您还没有指定是否可以使用 stl.
基本伪代码是
min := 1;
max := N; {array size: var A : array [1..N] of integer}
repeat
mid := (min + max) div 2;
if x > A[mid] then
min := mid + 1
else
max := mid - 1;
until (A[mid] = x) or (min > max);
因此,在您的情况下,最小值为 0,最大值为 100,其中可以将上述算法更改为支持用户输入。所需要做的不是对数组进行比较检查,您只需要检查用户输入。
min := 1;
max := 100;
repeat
mid := (min + max) div 2;
print mid;
c := getChar();
if c == 'h' then
min := mid + 1
else if c == 'l'
max := mid - 1;
else if c == 'y'
return mid
until (min > max);
但是,如果您需要更多帮助,到目前为止,您需要发布您的代码。
getRandomNumber(lower, upper){
return random number between lower and upper;
}
main(){
lower = 0;
upper = 101;
num = getRandomNumber(lower, upper);
response = askUser(num);
while(response != Y){
if (response==H)
//if secret is higher than num
lower = num;
else
//if secret is lower than num
upper = num;
num = getRandomNumber (lower, upper);
response = askUser(num);
}
}