Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.81/21: Рейтинг темы: голосов - 21, средняя оценка - 4.81
0 / 0 / 0
Регистрация: 05.11.2009
Сообщений: 13

Угадай число

05.11.2009, 14:52. Показов 4547. Ответов 10
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Я новичок! Пожалуйста помогите!
Игра «Угадай число»
Первый игрок задумывает число от 1 до N. Второй может задавать вопросы вида «делится ли задуманное число на …». Надо отгадать задуманное число за наименьшее число вопросов.
Программа имитирует действия второго игрока и вычисляет делимость для ответов на вопросы.
Входные данные – N и задуманное число n
Выходные данные список вопросов, которые задает 2 игрок.
Пожалуйста подскажите алгоритм и код!
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
05.11.2009, 14:52
Ответы с готовыми решениями:

Написать игру “Угадай число!”. Компьютер загадывает число в определенном диапазоне, а пользователь пытается его угадать
помогите решить Написать игру “Угадай число!”. Компьютер загадывает число в определенном диапазоне, а пользователь пытается его...

Угадай число
Угадай число Ограничение времени 2 секунды Ограничение памяти 512Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод...

Угадай число
Верных решений 16 37 Август и Беатриса играют в игру. Август загадал натуральное число от 1 до n. Беатриса пытается угадать это число,...

10
Эксперт С++
2924 / 1274 / 114
Регистрация: 27.05.2008
Сообщений: 3,465
05.11.2009, 16:44
Банальный двоичный поиск.
Например, любое число от 1 до 1000000 угадывается за максимум 20 вопросов. Первый вопрос: это число больше 500000 ? Если ответ "да" - то отбрасываем сразу все числа от 1 до 500000 включительно, и тогда второй вопрос: это число больше 750000 ? И так далее....
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
05.11.2009, 20:35
2CheshireCat: а теперь внимательно прочитай условие задачи.
Второй может задавать вопросы вида «делится ли задуманное число на …
Добавлено через 3 минуты
Ну первый вопрос - делится ли число на 2.
Ответ на этот вопрос сокращает число вариантов в 2 раза
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
06.11.2009, 15:12
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<windows.h>
using namespace std; 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    int i, N, temp=1, temp1, del, mas_pr[3450], i_prost=0;
    bool *bArray, fl=false;
    cout<<"Ââåäèòå ìàêñèìàëüíîå ÷èñëî N(íå áîëåå 32767): "<<endl;
    cin>>N;
    N++;
    bArray = new bool [N];
    memset(bArray, 1, N); 
    for(i = 2; i < N; ++i)
        if(bArray[i])
        for(int j = i*i; j < N; j += i)
             bArray[j] = false;
    for(i = 2; i < N; ++i)
        if(bArray[i])
        {
             cout<<"Äåëèòñÿ ëè çàäóìàííîå ÷èñëî íà "<<i<< ".Åñëè äåëèòñÿ íàæìèòå 1, åñëè íåò òî íàæìèòå 0"<<endl;
             cin>>del;
             if(del==1)
             {
                 mas_pr[i_prost]=i;
                 i_prost++;
             }
        }
    for(i=0; i<i_prost; i++)
        temp*=mas_pr[i];
    temp1=temp;
    while(!fl)
    {
        cout<<"Äåëèòñÿ ëè çàäóìàííîå ÷èñëî íà "<<temp<< ".Åñëè äåëèòñÿ íàæìèòå 1, åñëè íåò òî íàæìèòå 0"<<endl;
        cin>>del;
             if(del==1)
                temp+=temp1;
             else
                 fl=true;
    }
    cout<<"Çàäóìàííîå ÷èñëî: "<<temp-temp1<<endl;
    system("pause");
    return 0;
}
Вариант основан на следующем алгоритме:
1. Ищем все простые числа, на которые делится искомое число.
2. Все эти простые числа перемножаем.
3. Полученный результат постепенно увеличиваем и как только станет не делится, возвращаемся к предыдущему (это и есть ответ)
Я не использовал во вводе задуманное число. Оно здесь не нужно.
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
06.11.2009, 22:56
2valeriikozlov: во-первых совершенно не очевидно, что алгоритм оптимальный.
во-вторых он еще немного криво:
Например при N=5, n=4:
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
> 1.exe
Введите максимальное число N(не более 32767):
5
Делится ли задуманное число на 2.Если делится нажмите 1, если нет то нажмите 0
1
Делится ли задуманное число на 3.Если делится нажмите 1, если нет то нажмите 0
0
Делится ли задуманное число на 5.Если делится нажмите 1, если нет то нажмите 0
0
Делится ли задуманное число на 2.Если делится нажмите 1, если нет то нажмите 0
1
Делится ли задуманное число на 4.Если делится нажмите 1, если нет то нажмите 0
1
Делится ли задуманное число на 6.Если делится нажмите 1, если нет то нажмите 0
0
Задуманное число: 4
Добавлено через 10 минут
Рискну предположить, что если был ответ, что число делится на два, то далее следует задавать вопросы делится ли число на 2*2, 2*3, 2*5.

То есть видимо алгоритм такой (не факт что оптимальный).
Строим ряд простых чисел: 2 3 5 ...
Спрашиваем делится ли n на 2, n на 3, n на 5.
Двигается по этому ряду пока получаем ответ не делится.
Например:
n%2!=0, n%3!=0, n%5==0.

Если мы уже превысили N, а число так и не делится ни на что, то значит ответ: n==1.

Как только получили ответ что делится на простое число, то начинаем задавать вопросы уже другие.
Делится ли на 5*2, 5*3, 5*5, 5*7, ...
Так как проверять деление на 2 и на 3 уже нет смысла, то следующий вопрос будет:
Делится ли на 5*5, 5*7, 5*11, ...

Например если в данном примере мы больше не получим ответов что делится, то значит ответ: n==5.

И еще раз повторю - нужно еще доказать что это оптимальный алгоритм.

Добавлено через 12 минут
Продолжу алгоритм далее.
Если на вопрос делится ли на 5*11 следует ответ - ДА.
То дальше нужно проверять число 5*11*11.
Если опять ответ - ДА, то дальше нужно проверять 5*11*11*11.

Пусть p=1.
Пусть s[] - массив простых чисел.
Пусть ans= 1
Каждый раз мы спрашиваем: делится ли n на число q, где q= p*s[i].
Если ответ НЕТ - то делаем i++.
Если ответ ДА - то делаем ans= q; p*= s[i].
Вопросы заканчиваются когда число q>N.
Ответ: число ans.
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
07.11.2009, 13:45
odip,
Рискну предположить, что если был ответ, что число делится на два, то далее следует задавать вопросы делится ли число на 2*2, 2*3, 2*5.
А если это число 2*4?
Как только получили ответ что делится на простое число, то начинаем задавать вопросы уже другие.
Делится ли на 5*2, 5*3, 5*5, 5*7, ...
Так как проверять деление на 2 и на 3 уже нет смысла, то следующий вопрос будет:
Делится ли на 5*5, 5*7, 5*11, ...
это тоже самое по смылу что проверять деления просто на 5, 7, 11 (на пять то мы уже знаем что оно делится)
И еще раз повторю - нужно еще доказать что это оптимальный алгоритм.
я не собираюсь ничего доказывать. Я выложил этот алгоритм как вариант, если сможете придумать более оптимальный, да ради бога.
Продолжу алгоритм далее.
Если на вопрос делится ли на 5*11 следует ответ - ДА.
То дальше нужно проверять число 5*11*11.
Если опять ответ - ДА, то дальше нужно проверять 5*11*11*11.
Ну это совсем тупик. А если число 5*11*2, то мы его вообще никогда не найдем.

Добавлено через 18 минут
Цитата:Продолжу алгоритм далее.
Если на вопрос делится ли на 5*11 следует ответ - ДА.
То дальше нужно проверять число 5*11*11.
Если опять ответ - ДА, то дальше нужно проверять 5*11*11*11.

Ну это совсем тупик. А если число 5*11*2, то мы его вообще никогда не найдем.
Цитата:Рискну предположить, что если был ответ, что число делится на два, то далее следует задавать вопросы делится ли число на 2*2, 2*3, 2*5.

А если это число 2*4?
Вот эти цитаты считайте неправильными. Тут Вы абсолютно правы. Но вторая цитата остается в силе.
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
07.11.2009, 17:16
odip,
В общем еще раз подумав (уже на трезвую голову), я пришел к выводу что предложенный Вами алгоритм как имеет положительные стороны, так и отрицательные.
Положительные: правильно - для более оптимального поиска загаданного числа нужно найти все простые множители этого числа и их количество.
Отрицательное состоит в том что при такой проверке:
Как только получили ответ что делится на простое число, то начинаем задавать вопросы уже другие.
Делится ли на 5*2, 5*3, 5*5, 5*7, ...
Так как проверять деление на 2 и на 3 уже нет смысла, то следующий вопрос будет:
Делится ли на 5*5, 5*7, 5*11, ...
получится что мы найденное число (а оно может быть и не маленькое) будем умножать на простые числа под верхней границой заданного диапазона (а оно может тоже не маленьким). В этом случае мы превышаем максимальное значение для int, то есть на экране могут отражаться "левые" числа.
Так вот я взял только положительное от Вами предложенного алгоритма и вот результат:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<windows.h>
#include<math.h>
using namespace std; 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
        int i, N, temp, temp1=1, del, mas_pr[3450], i_prost=0;
        bool *bArray, fl;
        cout<<"Ââåäèòå ìàêñèìàëüíîå ÷èñëî N(íå áîëåå 32767): "<<endl;
        cin>>N;
    N++;
    bArray = new bool [N];
    memset(bArray, 1, N); 
    for(i = 2; i < N; ++i)
        if(bArray[i])
        for(int j = i*i; j < N; j += i)
             bArray[j] = false;
    for(i = 2; i < N; ++i)
        if(bArray[i])
                {
             cout<<"Äåëèòñÿ ëè çàäóìàííîå ÷èñëî íà "<<i<< ".Åñëè äåëèòñÿ íàæìèòå 1, åñëè íåò òî íàæìèòå 0"<<endl;
                         cin>>del;
                         if(del==1)
                         {
                                 mas_pr[i_prost]=i;
                                 i_prost++;
                         }
                }
        for(i=0; i<i_prost; i++)
           temp1*=mas_pr[i];
        for(i=0; i<i_prost; i++)
        {
            fl=false;
            temp=mas_pr[i];
            while(!fl)   
            {
                temp=pow(temp,2);
                cout<<"Äåëèòñÿ ëè çàäóìàííîå ÷èñëî íà "<<temp<< ".Åñëè äåëèòñÿ íàæìèòå 1, åñëè íåò òî íàæìèòå 0"<<endl;
                cin>>del;
                         if(del==1)
                                temp1*=pow(temp, 0.5);
                         else
                                 fl=true;
            }
        }
        cout<<"Çàäóìàííîå ÷èñëî: "<<temp1<<endl;
        system("pause");
    return 0;
}
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
07.11.2009, 22:34
Но вторая цитата остается в силе.
Это когда загадано число 8 что-ли ?
Читаем алгоритм и смотрим что получается:
Вопрос: n делится на 2 ?
Ответ: да
Вопрос: n делится на 4 ?
Ответ: да
Вопрос: n делится на 8 ?
Ответ: да
Вопрос: n делится на 16 ?
Ответ: нет
Вопрос: n делится на 24 ? ( 8*3 )
Ответ: нет
Вопрос: n делится на 40 ? ( 8*5 )
Ответ: нет
...
И так далее - пока q<=N.
Ответ будет 8.

Добавлено через 10 минут
получится что мы найденное число (а оно может быть и не маленькое) будем умножать на простые числа под верхней границой заданного диапазона (а оно может тоже не маленьким). В этом случае мы превышаем максимальное значение для int, то есть на экране могут отражаться "левые" числа.
Тебя смущает вычисление q= p*s[i] и проверка потом q<=N ?
Это тривиально обходится:
До вычисления числа q проверяем условие: p<=N/s[i] или s[i]<=N/p.
Так что никакой отрицательной стороны нет.

Кстати в твоем алгоритме явно есть проблема с маленькими числами:
Введите максимальное число N(не более 32767)
Почему такое странное ограничение ?
Я рассчитываю что мой алгоритм будет работать до N==2147483647 включительно

Добавлено через 1 минуту
Кстати из алгоритма видно, что наибольшее число вопросов будет задано если загадано n==1
1
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
07.11.2009, 23:45
все, окончательно убедил
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
08.11.2009, 12:56
все, окончательно убедил


Я вот думаю как доказать что этот алгоритм оптимальный.
Программно - тупо перебрать все вопросы - но при увеличении N число вариантов быстро растет.
Математически. Методом от противного.

Или конструктивно
Из алгоритма ясно, что на каждом шаге мы максимально уменьшаем число возможных комбинаций. То есть любое наше действие и так оптимально.
Например начало.
Изначально у нас N вариантов ответа.
Первый шаг: делится ли n на 2.
При ответе ДА мы получаем N/2 вариантов.
При ответе НЕТ мы получаем N/2 вариантов.

Если же спросить что-нибудь другое, например делится ли наше число на 3.
При ответе ДА мы получаем N/3 вариантов.
При ответе НЕТ мы получаем 2*N/3 вариантов.
То есть спросить про деление на 3 - это вопрос хуже.
Аналогично любой другой первый вопрос хуже.
0
Эксперт С++
 Аватар для valeriikozlov
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
08.11.2009, 13:53
Цитата Сообщение от odip Посмотреть сообщение
Я вот думаю как доказать что этот алгоритм оптимальный.
А для чего (или для кого доказывать). Для меня очевидно, что твой алгоритм оптимальный (по крайней мере с моим).
Даже вот эти выкладки:
Цитата Сообщение от odip Посмотреть сообщение
Из алгоритма ясно, что на каждом шаге мы максимально уменьшаем число возможных комбинаций. То есть любое наше действие и так оптимально.
Например начало.
Изначально у нас N вариантов ответа.
Первый шаг: делится ли n на 2.
При ответе ДА мы получаем N/2 вариантов.
При ответе НЕТ мы получаем N/2 вариантов.
Если же спросить что-нибудь другое, например делится ли наше число на 3.
При ответе ДА мы получаем N/3 вариантов.
При ответе НЕТ мы получаем 2*N/3 вариантов.
То есть спросить про деление на 3 - это вопрос хуже.
Аналогично любой другой первый вопрос хуже.
, они тоже подтверждают это.
Или есть какой-то интерес именно в доказательстве?
(Если есть, то мне кажется нужно тогда брать какие-нибудь выборки данных (чем их больше и из различных диапазонов тем лучше) и проверять какое количество вопросов получится при твоем алгоритме и сравниваемом). Математически (и чтобы было убедительно), мне кажется будет тяжело доказать.
Конструктивно (и тоже чтобы было убедительно) тоже тяжело. Например:
Цитата Сообщение от odip Посмотреть сообщение
Изначально у нас N вариантов ответа.
Первый шаг: делится ли n на 2.
При ответе ДА мы получаем N/2 вариантов.
При ответе НЕТ мы получаем N/2 вариантов.
Если же спросить что-нибудь другое, например делится ли наше число на 3.
При ответе ДА мы получаем N/3 вариантов.
При ответе НЕТ мы получаем 2*N/3 вариантов.
То есть спросить про деление на 3 - это вопрос хуже.
Аналогично любой другой первый вопрос хуже.
Но если я первый вопрос задам о делении на 3. (вроде бы и не самый оптимальный вопрос). А следующий вопрос задам о делении на 2. То как и в твоем алгоритме (на втором шаге) я на столько же уменьшил число возможных комбинаций.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
08.11.2009, 13:53
Помогаю со студенческими работами здесь

C++ Угадай число
#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;locale&gt; #include &lt;ctime&gt; void result(unsigned number) { srand(time(NULL)); ...

C++ Угадай число
#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;locale&gt; #include &lt;ctime&gt; void result(unsigned number) { ...

Угадай число
#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;locale&gt; #include &lt;ctime&gt; void result(unsigned number) { srand(time(NULL)); ...

Напишите программу "Угадай число", но здесь компьютер угадывает ваше число
Напишите программу &quot;Угадай число&quot;, но здесь компьютер угадывает ваше число. Желательно, чтобы в выводе писали, сколько попыток потратил...

Игра «Угадай число»
4. Игра «Угадай число». Компьютер загадывает число, человек отгадывает. Всего 5 попыток. (random)


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Новые блоги и статьи
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru