Как написать двоичный алгоритм для C / C ++

Question

У меня возникли проблемы с написанием двоичного алгоритма на C / C ++.
Мой вопрос звучит примерно так:

Примените двоичный алгоритм для поиска числа от 1 до 100 в игре на угадывание чисел.
Пользователь ответит "y" за правильное предположение, "h", если предположение слишком высокое, или "l", если предположение слишком низкое.

У меня нет ни малейшей идеи применить это.Может кто-нибудь просто привести мне пример кода.

Answer 1

Подробные инструкции здесь плюс различные реализации.

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] 

Answer 2

Я предполагаю, вы имеете в виду бинарный поиск.В Википедии есть огромное количество информации.Вы также не указали, можете ли вы использовать 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);

Итак, в вашем случае min равно 0, max равно 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);

Однако, если вам нужна дополнительная помощь, вам нужно будет опубликовать свой код до сих пор.

Answer 3

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