|
0 / 0 / 0
Регистрация: 05.11.2009
Сообщений: 13
|
|
Угадай число05.11.2009, 14:52. Показов 4575. Ответов 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++ Угадай число Угадай число Напишите программу "Угадай число", но здесь компьютер угадывает ваше число Игра «Угадай число» Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
|
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога
Финальные проекты на Си и на C++:
hello-sdl3-c. zip
hello-sdl3-cpp. zip
Результат:
|
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога
MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
|
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд.
Даже если у вас. . .
|
|
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает
монорепозиторий в котором находятся все исходники.
При создании нового решения, мы просто добавляем нужные проекты
и имеем. . .
|
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение:
В этой книге («Подход, основанный на вариантах использования») Ивар утверждает,
что архитектура программного обеспечения — это
структуры,. . .
|
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога
Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
|
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога
Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip
На первой гифке отладочные линии отключены, а на второй включены:. . .
|