Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.83
Indira
0 / 0 / 0
Регистрация: 05.11.2009
Сообщений: 13
#1

Угадай число - C++

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

Я новичок! Пожалуйста помогите!
Игра «Угадай число»
Первый игрок задумывает число от 1 до N. Второй может задавать вопросы вида «делится ли задуманное число на …». Надо отгадать задуманное число за наименьшее число вопросов.
Программа имитирует действия второго игрока и вычисляет делимость для ответов на вопросы.
Входные данные – N и задуманное число n
Выходные данные список вопросов, которые задает 2 игрок.
Пожалуйста подскажите алгоритм и код!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2009, 14:52     Угадай число
Посмотрите здесь:

C++ "Угадай число" (напишите программу, хочу проверить со своей).
Составить программу игры «Угадай число». C++
Угадай число. За угадчика C++
Исправить ошибки в программе "угадай число" C++
C++ Написать игру “Угадай число!”. Компьютер загадывает число в определенном диапазоне, а пользователь пытается его угадать
C++ Написать игру «Угадай число»
C++ Builder Таблица рекордов для игры "Угадай число"
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CheshireCat
Эксперт С++
2891 / 1240 / 78
Регистрация: 27.05.2008
Сообщений: 3,345
05.11.2009, 16:44     Угадай число #2
Банальный двоичный поиск.
Например, любое число от 1 до 1000000 угадывается за максимум 20 вопросов. Первый вопрос: это число больше 500000 ? Если ответ "да" - то отбрасываем сразу все числа от 1 до 500000 включительно, и тогда второй вопрос: это число больше 750000 ? И так далее....
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
05.11.2009, 20:35     Угадай число #3
2CheshireCat: а теперь внимательно прочитай условие задачи.
Второй может задавать вопросы вида «делится ли задуманное число на …
Добавлено через 3 минуты
Ну первый вопрос - делится ли число на 2.
Ответ на этот вопрос сокращает число вариантов в 2 раза
valeriikozlov
Эксперт C++
4667 / 2493 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
06.11.2009, 15:12     Угадай число #4
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. Полученный результат постепенно увеличиваем и как только станет не делится, возвращаемся к предыдущему (это и есть ответ)
Я не использовал во вводе задуманное число. Оно здесь не нужно.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
06.11.2009, 22:56     Угадай число #5
2valeriikozlov: во-первых совершенно не очевидно, что алгоритм оптимальный.
во-вторых он еще немного криво:
Например при N=5, n=4:
Код
> 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.
valeriikozlov
Эксперт C++
4667 / 2493 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.11.2009, 13:45     Угадай число #6
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?
Вот эти цитаты считайте неправильными. Тут Вы абсолютно правы. Но вторая цитата остается в силе.
valeriikozlov
Эксперт C++
4667 / 2493 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.11.2009, 17:16     Угадай число #7
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;
}
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
07.11.2009, 22:34     Угадай число #8
Но вторая цитата остается в силе.
Это когда загадано число 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
valeriikozlov
Эксперт C++
4667 / 2493 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.11.2009, 23:45     Угадай число #9
все, окончательно убедил
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
08.11.2009, 12:56     Угадай число #10
все, окончательно убедил


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

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

Если же спросить что-нибудь другое, например делится ли наше число на 3.
При ответе ДА мы получаем N/3 вариантов.
При ответе НЕТ мы получаем 2*N/3 вариантов.
То есть спросить про деление на 3 - это вопрос хуже.
Аналогично любой другой первый вопрос хуже.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.11.2009, 13:53     Угадай число
Еще ссылки по теме:

C++ Программа угадай число
Игра «Угадай число» C++
Реализовать генерацию случайных чисел для игры "Угадай число" C++
Упражнение из книги Страуструпа. Программа угадай число. Можно ли написать лучше? C++
Угадай число C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4667 / 2493 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.11.2009, 13:53     Угадай число #11
Цитата Сообщение от 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. То как и в твоем алгоритме (на втором шаге) я на столько же уменьшил число возможных комбинаций.
Yandex
Объявления
08.11.2009, 13:53     Угадай число
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru