Question

В этой задаче вам предстоит отгадать число, загаданное жюри. Жюри загадало число от 1 до 100 включительно. Требуется отгадать его за неболее чем 30 попыток. А именно, есть объект типа BlackBox class BlackBox { public: void GuessNumber(int x) const; }; В этом объекте хранится число. У него есть единственный публичный метод GuessNumber. Этот объект будет передан вам по константной ссылке. Пусть жюри загадало число y от 1 до 100. Если вызвать метод GuessNumber у объекта BlackBox с аргументом x, то может произойти одна из 3 ситуаций: 1. y < x. Тогда будет брошено исключение типа ExceptionLess 2. y == x. Тогда будет брошено исключение типа ExceptionEqual 3. y > x. Тогда будет брошено исключение типа ExceptionGreater Все исключения будут подключены к вашему коду, а задаются они так: class ExceptionLess : public std::exception { }; class ExceptionGreater : public std::exception { }; class ExceptionEqual : public std::exception { }; Также к вашему коду будет добавлена реализация самого класса BlackBox, однако его код не раскрывается. Ваша задача написать функцию int guess(const BlackBox& box) Она принимает объект типа BlackBox, а возвращает загаданное число. У вас есть неболее 30 попыток, чтобы отгадать это число, иначе рещение получит вердикт RE В систему отправляйте лишь код функции guess и необходимые библиотеки, всё остальное будет подключено автоматически

Answer 1

Ответ:

int guess(const BlackBox& box) {

  int left = 1, right = 100;

  int middle;

  for (int i = 0; i < 30; ++i) {

      middle = (left + right) / 2;

      try {

          box.GuessNumber(middle);

          return middle;

      }

      catch (ExceptionLess& e) {

          right = middle - 1;

      }

      catch (ExceptionGreater& e) {

          left = middle + 1;

      }

      catch (ExceptionEqual& e) {

          return middle;

      }

  }

}

Объяснение:

Answer 2

Для решения этой задачи, нам нужно использовать бинарный поиск.

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

Начнем с того, что установим начальные границы интервала возможных чисел: левую границу установим на 1, а правую на 100.

Затем, в цикле будем сокращать этот интервал пополам, пока не отгадаем число или пока не исчерпаем все попытки.

В каждой итерации цикла будем вызывать метод GuessNumber объекта box с текущим числом. Если метод выбрасывает исключение ExceptionLess, значит загаданное число меньше текущего, и мы сокращаем интервал, устанавливая правую границу на текущее число минус 1. Если метод выбрасывает исключение ExceptionGreater, значит загаданное число больше текущего, и мы сокращаем интервал, устанавливая левую границу на текущее число плюс 1. Если метод выбрасывает исключение ExceptionEqual, значит мы угадали число и можем вернуть его.

Если после 30 попыток число не будет отгадано, то выбрасываем исключение RE.

Вот код функции guess:

int guess(const BlackBox& box) {
    int left = 1;
    int right = 100;
    
    for (int i = 0; i < 30; i++) {
        int mid = (left + right) / 2;
        
        try {
            box.GuessNumber(mid);
            return mid;
        } catch (const ExceptionLess&) {
            right = mid - 1;
        } catch (const ExceptionGreater&) {
            left = mid + 1;
        } catch (const ExceptionEqual&) {
            return mid;
        }
    }
    
    throw std::runtime_error("RE");
}

В данном коде мы используем конструкцию try-catch для перехвата исключений, которые могут быть выброшены в методе GuessNumber. Если исключение выбрасывается, мы изменяем границы интервала и продолжаем цикл.

Обратите внимание, что код функции guess не зависит от реализации класса BlackBox и использует только публичный метод GuessNumber.

Надеюсь, это поможет вам решить задачу!