0 / 0 / 0
Регистрация: 05.11.2009
Сообщений: 13
|
|
1 | |
Угадай число05.11.2009, 14:52. Показов 4126. Ответов 10
Метки нет (Все метки)
Я новичок! Пожалуйста помогите!
Игра «Угадай число» Первый игрок задумывает число от 1 до N. Второй может задавать вопросы вида «делится ли задуманное число на …». Надо отгадать задуманное число за наименьшее число вопросов. Программа имитирует действия второго игрока и вычисляет делимость для ответов на вопросы. Входные данные – N и задуманное число n Выходные данные список вопросов, которые задает 2 игрок. Пожалуйста подскажите алгоритм и код!
0
|
05.11.2009, 14:52 | |
Ответы с готовыми решениями:
10
Написать игру “Угадай число!”. Компьютер загадывает число в определенном диапазоне, а пользователь пытается его угадать Угадай число Угадай число C++ Угадай число |
2924 / 1274 / 114
Регистрация: 27.05.2008
Сообщений: 3,465
|
|
05.11.2009, 16:44 | 2 |
Банальный двоичный поиск.
Например, любое число от 1 до 1000000 угадывается за максимум 20 вопросов. Первый вопрос: это число больше 500000 ? Если ответ "да" - то отбрасываем сразу все числа от 1 до 500000 включительно, и тогда второй вопрос: это число больше 750000 ? И так далее....
0
|
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
05.11.2009, 20:35 | 3 |
2CheshireCat: а теперь внимательно прочитай условие задачи.
Ну первый вопрос - делится ли число на 2. Ответ на этот вопрос сокращает число вариантов в 2 раза
0
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
06.11.2009, 15:12 | 4 | |||||
1. Ищем все простые числа, на которые делится искомое число. 2. Все эти простые числа перемножаем. 3. Полученный результат постепенно увеличиваем и как только станет не делится, возвращаемся к предыдущему (это и есть ответ) Я не использовал во вводе задуманное число. Оно здесь не нужно.
0
|
7175 / 3234 / 81
Регистрация: 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 Рискну предположить, что если был ответ, что число делится на два, то далее следует задавать вопросы делится ли число на 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
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
07.11.2009, 13:45 | 6 |
odip,
Добавлено через 18 минут
0
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
07.11.2009, 17:16 | 7 | |||||
odip,
В общем еще раз подумав (уже на трезвую голову), я пришел к выводу что предложенный Вами алгоритм как имеет положительные стороны, так и отрицательные. Положительные: правильно - для более оптимального поиска загаданного числа нужно найти все простые множители этого числа и их количество. Отрицательное состоит в том что при такой проверке: Так вот я взял только положительное от Вами предложенного алгоритма и вот результат:
0
|
7175 / 3234 / 81
Регистрация: 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 минут Это тривиально обходится: До вычисления числа q проверяем условие: p<=N/s[i] или s[i]<=N/p. Так что никакой отрицательной стороны нет. Кстати в твоем алгоритме явно есть проблема с маленькими числами: Я рассчитываю что мой алгоритм будет работать до N==2147483647 включительно Добавлено через 1 минуту Кстати из алгоритма видно, что наибольшее число вопросов будет задано если загадано n==1
1
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
07.11.2009, 23:45 | 9 |
все, окончательно убедил
0
|
7175 / 3234 / 81
Регистрация: 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 - это вопрос хуже. Аналогично любой другой первый вопрос хуже.
0
|
4726 / 2547 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
08.11.2009, 13:53 | 11 |
А для чего (или для кого доказывать). Для меня очевидно, что твой алгоритм оптимальный (по крайней мере с моим).
Даже вот эти выкладки: , они тоже подтверждают это. Или есть какой-то интерес именно в доказательстве? (Если есть, то мне кажется нужно тогда брать какие-нибудь выборки данных (чем их больше и из различных диапазонов тем лучше) и проверять какое количество вопросов получится при твоем алгоритме и сравниваемом). Математически (и чтобы было убедительно), мне кажется будет тяжело доказать. Конструктивно (и тоже чтобы было убедительно) тоже тяжело. Например: Но если я первый вопрос задам о делении на 3. (вроде бы и не самый оптимальный вопрос). А следующий вопрос задам о делении на 2. То как и в твоем алгоритме (на втором шаге) я на столько же уменьшил число возможных комбинаций.
0
|
08.11.2009, 13:53 | |
Помогаю со студенческими работами здесь
11
C++ Угадай число Угадай число Напишите программу "Угадай число", но здесь компьютер угадывает ваше число Игра «Угадай число» Угадай число. За угадчика Игра в угадай число Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |