如何为 C/C++ 编写二进制算法

发布于 2024-08-14 00:00:37 字数 165 浏览 6 评论 0原文

我在用 C/C++ 编写二进制算法时遇到问题。
我的问题是这样的:

应用二进制算法在猜数游戏中搜索从 1 到 100 的数字。
如果猜测正确,用户将回答“y”;如果猜测太高,则回答“h”;如果猜测太低,则回答“l”。

我没有任何想法来应用它。有人能给我一个代码示例吗?

I am having trouble to write the binary algorithm in C/C++.
My question is like that:

Apply binary algorithm to search for a number from 1 to 100 in a number guessing game.
The user will respond with 'y' for a correct guess, 'h' if the guess is too high or 'l' if the guess is too low.

I don't have any idea to apply it. Can someone just give me an example of the code.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

银河中√捞星星 2024-08-21 00:00:37

详细说明此处以及各种实现。

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] 

Detailed instructions here plus various implementations.

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] 
丿*梦醉红颜 2024-08-21 00:00:37

我假设你的意思是二分搜索。维基百科拥有大量信息。您还没有指定是否可以使用 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);

但是,如果您需要更多帮助,则需要发布到目前为止的代码。

I assume you mean binary search. Wikipedia has loads of information. You also haven't specified if you can use the stl.

The basic pseudo code is

  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);

So in you case, min is 0, max is 100, where could alter the above algorithm to that it supports user input. All that needs to happen is rather than the comparison checks on an array, you just need to check user input.

  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);

However if you want more help, you will need to post your code so far.

温柔女人霸气范 2024-08-21 00:00:37
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);
 }
}
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);
 }
}
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文