C++ задача GuessNumber

Question

C++ задача GuessNumber

Артём Калайда Ученик (99), открыт 1 месяц назад

В этой задаче вам предстоит отгадать число, загаданное жюри.
Жюри загадало число от 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

Для решения этой задачи вы можете использовать алгоритм бинарного поиска, который позволяет найти число за логарифмическое время. В данном случае, вы сможете отгадать число за меньше, чем 30 попыток, так как log2(100) < 7. Вот пример реализации функции guess с использованием бинарного поиска:

 #include  
 
class ExceptionLess : public std::exception { 
}; 
 
class ExceptionGreater : public std::exception { 
}; 
 
class ExceptionEqual : public std::exception { 
}; 
 
class BlackBox { 
public: 
    void GuessNumber(int x) const; 
}; 
 
int guess(const BlackBox& box) { 
    int left = 1; 
    int right = 100; 
    int mid; 
 
    while (left <= right) { 
        mid = left + (right - left) / 2; 
        try { 
            box.GuessNumber(mid); 
        } catch (const ExceptionLess& e) { 
            right = mid - 1; 
        } catch (const ExceptionGreater& e) { 
            left = mid + 1; 
        } catch (const ExceptionEqual& e) { 
            return mid; 
        } 
    } 
 
    // Эта строка не должна быть достигнута, но добавлена для предотвращения ошибок компиляции 
    return -1; 
}

Теперь функция guess может отгадать число, используя объект BlackBox, и делает это за менее чем 30 попыток. Вы можете отправить код функции guess и необходимые библиотеки в систему.