Как найти число за 7 попыток - Исправление недочетов и поиск решений вместе с Examum.ru

— Загадал.

— Спорим, я угадаю его за 7 попыток или быстрее? Я буду называть числа, а ты — отвечать, оно больше, меньше или равно загаданному.

6 попыток спустя отец угадал число, а ребёнок сидит в шоке. Они попробовали снова, и во второй раз отец угадал число за семь попыток. В третий — за четыре. Сколько бы они ни играли, число всегда угадывалось за 7 попыток или менее.

Это простейшая алгоритмическая задача, которую показывают на первом уроке информатики, чтобы показать мощь алгоритмического мышления. Смысл в том, чтобы…

👉 каждый раз называть число, которое делит пополам диапазон возможных чисел.

Этот приём каждый раз в 2 раза сокращает область поиска, и в конце нам становится легко угадать даже простым перебором.

Допустим, сын загадал число 63. Тогда делаем так:

Находим середину диапазона от 0 до 100 — это 50. Называем это число. Сын говорит «Больше».
Значит, его число лежит в диапазоне от 50 до 100. Находим его середину — 75. Называем это число. Сын говорит «Меньше».
Ага, значит, его число находится в диапазоне от 50 до 75. Находим середину — 62. Называем это число. Сын говорит «Больше».
Поиск снова сузился: от 62 до 75. Середина — 67. Называем это число. Сын говорит «Меньше».
У нас осталось 3 попытки и 4 числа. Найдём ещё одну середину — 64. Называем это число. Сын говорит «Меньше».
Раз у нас число, которое больше, чем 62, и меньше, чем 64, то это число 63. Даже седьмая попытка не понадобилась.

Этим способом можно угадать любое число от 0 до 100 за 7 попыток или меньше. Главное — быстро и правильно считать в уме середину и помнить, как выглядит сейчас твой рабочий диапазон.

А если число будет больше?

На самом деле за 7 шагов можно угадать любое число от 0 до 127 или от 1 до 128. Всё потому, что два в седьмой степени — это как раз 128. Каждый раз, когда мы делим рабочий диапазон на 2, мы как будто убираем одну степень у двойки, постепенно уменьшая наш диапазон угадывания до двух чисел. Для верности лучше добавить ещё попытку.

Если бы у нас было 8 попыток, можно было бы угадывать числа до 256. 9 попыток — 512 и так далее.

На этом принципе построена модель данных «Бинарное дерево» — это одна из важнейших технологий для составления словарей и поиска данных. Прочитайте об этом в статье про бинарные деревья.

Источник

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

Условие

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

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

Решение

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

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

Можно найти число и в диапазоне побольше — от 0 до 127 или от 1 до 128. Всё потому, что 2⁷=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);
            }
        }
    }
}

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

Источник

The answer is that $2^7=128>100$.

To be more precise:

Say that you start by guessing $50$. Either you’re right, in which case you’re done, or you’re wrong; if you’re wrong, then you know that the number is either in $[1,49]$ or $[51,100]$, so that there are only $49$ or $50$ possibilities left.

Now, assuming that you aren’t already done, you have a collection of $49$ or $50$ possibilities left; guess the middle one. That is, if you are on $[1,49]$, guess (say) $25$; if you’re on $[51,100]$, then guess (say) $75$. If you got it right: great. If not, then you find out whether it should be higher or lower; in particular, if you previously knew it was in $[1,49]$, then you either now know it is in $[1,24]$ or you now know it is in $[26, 49]$. If you previously knew it was in $[51,100]$, then either you know that it is in $[51,74]$ or that it is in $[76,100]$.

In any case, you have either already guess right, or you have narrowed down the possibilities to one of $[1,24]$, $[26,49]$, $[51,74]$, or $[76,100]$. In any one of these cases, there are at most $25$ possibilities left, and it must be one of them.

Continue in this way: cut your current interval of possibilities in half by a guess, so that you are either right or you can discard roughly half of the possibilities based on the announcement of «higher» or «lower».

By continuing this process, in the third step you narrow it down to at most $12$ possibilities; in the fourth, to at most $6$; in the fifth, to at most $3$; in the sixth, to at most $1$; and voila! In your seventh guess, assuming that you’re unlucky enough to have not guessed it yet, there’s only one number that could possibly be it.

Источник

Можно использовать для пикапа

Мы недавно рассказали о том, как угадать любое число от 0 до 100 за 7 попыток или меньше. Сегодня будет другой трюк, который сработает и с первоклассником, и с доктором наук.

А трюк такой: вы можете поспорить с кем угодно, что вы легко назовёте результат вычислений, даже не зная исходного числа.

Работает так:

Ваш собеседник загадывает любое целое число и умножает его на 2.

Прибавляет к результату 8.

Что получилось — делит на 2.

От результата отнимает своё число, которое он загадал.

А вы делаете сосредоточенный вид и после паузы называете число 4. Работает всегда, даже если загадать 945 342 371.

Как это работает

Всё просто: сам ход вычислений построен так, чтобы независимо от первоначального числа получилось 4. Следите за руками.

Обозначим загаданное число за X и умножим его на 2 → получим 2X

Прибавляем 8 → получим 2X + 8

Результат делим на 2 → (2X + / 2 = X + 4

Отнимаем загаданное число X → X + 4 − X = 4

Получается, что бы ни загадал наш собеседник, в результате всегда получится 4. Вот такая простая магия.

А зачем это мне знать?

О, применений этого знания масса:

можно на час занять ребёнка, чтобы он попробовал загадать число, где это не сработает;

заодно и он, и вы потренируетесь считать в уме.

А ещё вывод такой: не всё, что выглядит сложно, на самом деле является сложным. Программирование тоже выглядит сначала сложно, но если разобраться — всё становится просто и очевидно. Прямо как в этом примере.

Источник

0 / 0 / 0

Регистрация: 04.12.2016

Сообщений: 43

06.07.2017, 20:03. Показов 6408. Ответов 3

Задача заключается в том что нужно написать программу который угадывает число пользователя от 1 до 100 есть только 7 попыток. Я понимаю что можно решить с помощью if, else а есть ли более изящный подход?

Herji

299 / 208 / 174

Регистрация: 11.05.2016

Сообщений: 655

06.07.2017, 21:20

C++

    srand(0);
 
    int x;
    std::cin >> x;
 
    for(int i=0; i<7; i++)
        (((rand()%100+1)==x) ? (std::cout << "Right! Its " << x << "n" ) : ( std::cout << "Good one, but no n" ));

anapshy

237 / 263 / 218

Регистрация: 14.11.2016

Сообщений: 992

06.07.2017, 21:23

Tenarius,

C++

#include <iostream>
#include <Windows.h>    // Sleep() SetConsoleCP() SetConsoleOutputCP()
#include <cstdlib>      // system() srand() rand()
#include <ctime>        // time()
#define     MAX_NUM         100
#define     MIN_NUM         0
#define     MAX_HEALTH      7
#define     TIME_SLEEP      3000
int main(void)
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251); // Шрифт консоли: Lucida Console
    std::srand(unsigned(std::time(NULL)));
    unsigned health(MAX_HEALTH);
    signed num(0);
    do
    {
        std::cout << "tВведите число от " << MIN_NUM << " до " << MAX_NUM << " (включительно): ";
        std::cin >> num;
        if (num < MIN_NUM || num > MAX_NUM)
        {
            std::cerr << "[Ошибка] Некорректный ввод!n" << std::endl;
            system("pause");
            system("cls");
        }
    } while (num < MIN_NUM || num > MAX_NUM);
    std::cout << "----------------------------------------------------------" << std::endl;
    std::cout << "n[Компьютер] -Попытаюсь угадать твоё число с " << MAX_HEALTH << " попыток!n" << std::endl;
    Sleep(TIME_SLEEP);
    bool flag(true);
    while (flag && health)
    {
        int buf(MIN_NUM + rand() % ((MIN_NUM*-1) + (MAX_NUM + 1)));
        if (buf == num)
        {
            std::cout << "[Компьютер] -Это число " << buf << std::endl << std::endl << std::endl;
            flag = false;
        }
        else
        {
            std::cout << "[Компьютер] -Это не " << buf << "? Упс, промахнулся..." << std::endl
                << "*** Осталось попыток: " << --health << "***n" << std::endl;
        }
        Sleep(TIME_SLEEP);
    }
    std::cout << "---------------------------------------------------------" << std::endl;
    std::cout << "ttИГРА ЗАКОНЧЕНА!" << std::endl;
    if (health)
    {
        std::cout << "tКомпьютер угадал число с " << (MAX_HEALTH - health) + 1 << " попытки!" << std::endl;
    }
    else
    {
        std::cout << "tКомпьютер не смог угадать число :С" << std::endl;
    }
    std::cout << "---------------------------------------------------------" << std::endl;
    std::cout << std::endl;
    system("pause");
    return 0;
}

5230 / 3202 / 362

Регистрация: 12.12.2009

Сообщений: 8,112

Записей в блоге: 2

07.07.2017, 14:16

бинарный поиск в руки, 2 ^ 7 = 128, после каждой попытки спрашивать юзера «больше» или «меньше»

Источник