Угадать число от 0 до 100 за 7 попыток — математический трюк

Этот математический фокус не так сложен, как может показаться на первый взгляд. Более того, решение мы реализуем программно на языке Java. Приступим?

Условие

Если расписать весь процесс поэтапно, выглядит это следующим образом:

1. Вы загадываете число от 0 до 100.
2. Программа выводит целое число в рамках данного диапазона.
3. Вы отвечаете, ваше число больше, меньше или равно тому, что вывела программа.
4. Если число больше либо меньше, программа продолжает предлагать варианты.
5. За 7 или менее попыток число гарантированно угадывается.

Решение

На самом деле, никакого особого секрета здесь нет, и решение строится на бинарном поиске. Это простая алгоритмическая задача, смысл которой в том, чтобы каждый раз делить оставшийся диапазон на 2. Таким образом мы с каждой попыткой вдвое сокращаем область поиска, увеличивая шансы на успех. Вот и весь математический фокус.

Допустим, первой догадкой алгоритма будет число 50, после чего становится понятно, в какую сторону исходного диапазона «шагать» дальше: это будет область 0–50 либо 51–100. Если первый вариант, то далее алгоритм предложит число 25 и так далее. Математические законы предполагают, что если число 100 делить вдвое 7 раз, мы гарантированно получим результат в районе единицы.

Можно найти число и в диапазоне побольше — от 0 до 127 или от 1 до 128. Всё потому, что 27=128. Соответственно, если у нас будет 8 попыток, область можно увеличить до 256, если 9 — до 512 и т. д. По этому же принципу работают бинарные деревья.

Но решать всё вручную с калькулятором наперевес — прошлый век. Давайте подключим код и посмотрим, как с этим справится программа.

Решение кодом

Воспроизведём решение с помощью Java без использования графического интерфейса. При желании всегда можно подключить Swing или JavaFX.

Для начала определимся с переменными, которые нам потребуются:

			//заданные границы:
int min = 0;
int max = 100;

//середина области:
int midrange = Math.round((min + max) / 2);

//строка для работы с терминалом:
String strInput = "";
		

Поскольку мы будем работать с терминалом, подключим слушатель событий с помощью класса Scanner:

			import java.util.Scanner;
		

И объявим переменную слушателя:

			Scanner scan = new Scanner(System.in);
		

Далее всё просто: программа выводит варианты, а пользователь отправляет +, - или =, в зависимости от того, больше загаданное число, меньше или идентично. Пока введённое значение не = (while (!strInput.equals("="))), продолжаем вычислять и делить заданный диапазон:

			import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int min = 0;
        int max = 100;
        int midrange = Math.round((min + max) / 2);
        String strInput = "";
        Scanner scan = new Scanner(System.in);

        System.out.println("Загадайте число от 0 до 100: я угадаю его за 7 попыток!\n" +
                "Чтобы продолжить, введите любое значение:");
        strInput = scan.nextLine();

        while (!strInput.equals("=")) {
            System.out.println("Это число больше, меньше или равно " + midrange + "? " +
                    "Введите '+' если больше, '-' если меньше и '=' если равно:");
            strInput = scan.nextLine();
            if (strInput.equals("=")) {
                System.out.println("Отлично! Ваше число " + midrange + ". Спасибо за игру ;)");
                break;
            } else if (strInput.equals("+")) {
                //уменьшаем диапазон:
                min = midrange;

                //находим новую середину диапазона:
                midrange = Math.round((min + max) / 2);

                //если округление сравнило середину с нижней границей, увеличиваем середину на 1:
                if (min == midrange && midrange!=100) {
                    midrange += 1;
                }
            } else if (strInput.equals("-")) {
                max = midrange;
                midrange = Math.round((min + max) / 2);
            }
        }
    }
}
		

Понравилась задачка? Держите ещё один математический фокус в виде гипотезы Коллатца.