|
0 / 0 / 0
Регистрация: 05.11.2009
Сообщений: 13
|
|
Угадай число05.11.2009, 14:52. Показов 4547. Ответов 10
Метки нет (Все метки)
Я новичок! Пожалуйста помогите!
Игра «Угадай число» Первый игрок задумывает число от 1 до N. Второй может задавать вопросы вида «делится ли задуманное число на …». Надо отгадать задуманное число за наименьшее число вопросов. Программа имитирует действия второго игрока и вычисляет делимость для ответов на вопросы. Входные данные – N и задуманное число n Выходные данные список вопросов, которые задает 2 игрок. Пожалуйста подскажите алгоритм и код!
0
|
|
| 05.11.2009, 14:52 | |
|
Ответы с готовыми решениями:
10
Написать игру “Угадай число!”. Компьютер загадывает число в определенном диапазоне, а пользователь пытается его угадать
|
|
2924 / 1274 / 114
Регистрация: 27.05.2008
Сообщений: 3,465
|
|
| 05.11.2009, 16:44 | |
|
Банальный двоичный поиск.
Например, любое число от 1 до 1000000 угадывается за максимум 20 вопросов. Первый вопрос: это число больше 500000 ? Если ответ "да" - то отбрасываем сразу все числа от 1 до 500000 включительно, и тогда второй вопрос: это число больше 750000 ? И так далее....
0
|
|
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
||
| 05.11.2009, 20:35 | ||
|
2CheshireCat: а теперь внимательно прочитай условие задачи.
Ну первый вопрос - делится ли число на 2. Ответ на этот вопрос сокращает число вариантов в 2 раза
0
|
||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
| 06.11.2009, 15:12 | ||||||
1. Ищем все простые числа, на которые делится искомое число. 2. Все эти простые числа перемножаем. 3. Полученный результат постепенно увеличиваем и как только станет не делится, возвращаемся к предыдущему (это и есть ответ) Я не использовал во вводе задуманное число. Оно здесь не нужно.
0
|
||||||
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
||||||
| 06.11.2009, 22:56 | ||||||
|
2valeriikozlov: во-первых совершенно не очевидно, что алгоритм оптимальный.
во-вторых он еще немного криво: Например при N=5, n=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
|
||||||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|||||||
| 07.11.2009, 13:45 | |||||||
|
odip,
Добавлено через 18 минут
0
|
|||||||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|||||||
| 07.11.2009, 17:16 | |||||||
|
odip,
В общем еще раз подумав (уже на трезвую голову), я пришел к выводу что предложенный Вами алгоритм как имеет положительные стороны, так и отрицательные. Положительные: правильно - для более оптимального поиска загаданного числа нужно найти все простые множители этого числа и их количество. Отрицательное состоит в том что при такой проверке:
Так вот я взял только положительное от Вами предложенного алгоритма и вот результат:
0
|
|||||||
|
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
|
||||
| 07.11.2009, 22:34 | ||||
Читаем алгоритм и смотрим что получается: Вопрос: 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
|
||||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
|
| 07.11.2009, 23:45 | |
|
все, окончательно убедил
0
|
|
|
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
|
||
|
4728 / 2549 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||
| 08.11.2009, 13:53 | ||||
|
Даже вот эти выкладки: Или есть какой-то интерес именно в доказательстве? (Если есть, то мне кажется нужно тогда брать какие-нибудь выборки данных (чем их больше и из различных диапазонов тем лучше) и проверять какое количество вопросов получится при твоем алгоритме и сравниваемом). Математически (и чтобы было убедительно), мне кажется будет тяжело доказать. Конструктивно (и тоже чтобы было убедительно) тоже тяжело. Например:
0
|
||||
| 08.11.2009, 13:53 | |
|
Помогаю со студенческими работами здесь
11
C++ Угадай число C++ Угадай число Угадай число Напишите программу "Угадай число", но здесь компьютер угадывает ваше число Игра «Угадай число» Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
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
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов.
. . .
|