|
0 / 0 / 0
Регистрация: 05.06.2018
Сообщений: 3
|
|
Какие вопросы нужно задать, чтобы за минимальное число вопросов угадать эти числа?20.06.2019, 21:39. Показов 3650. Ответов 16
Метки нет (Все метки)
0
|
|
(| 20.06.2019, 21:39 | |
|
Ответы с готовыми решениями:
16
Играющему нужно угадать загаданное число за минимальное количество вопросов Из банка вопросов выбрать Н вопросов для теста, так чтобы вопросы не повторялись |
|
Диссидент
 
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
| 20.06.2019, 22:02 | |
|
tabbols95, этот алгоритм хорош для одного числа. Когда их двое, имхо, все значительно интереснее.
Но задача требует уточнения. Загаданные числа пронумерованы? То есть я могу спросить "Первое число такое-то?" Или такого типа вопросы запрещены? Второе уточнение. Загаданные числа могут быть одинаковыми? Добавлено через 1 минуту И еще вопрос. А при чем здесь Вероятность и Статистика?
1
|
|
|
Диссидент
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
| 21.06.2019, 09:33 | |
Сообщение от Байт
Сообщение от Nare6ator
Однако, как ни крути... Для ненумерованных чисел возможны X = Каждый вопрос разбивает на 2 области. Меньше чем 13 вопросами не обойтись Точная формула: Наименьшее целое число, большее или равное log2X Для нумерованных X надо умножить на 2, к ответу прибавить 1
1
|
|
|
16 / 13 / 3
Регистрация: 07.10.2016
Сообщений: 115
|
|
| 10.07.2019, 21:42 | |
|
А вопросы в духе "Первое больше чем второе" разве не сильно упрощают жизнь?
0
|
|
|
Диссидент
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
| 10.07.2019, 22:24 | |
|
Сообщение от Tetroghon
Если интересно, попробуйте на 8-ми (или на 7-ми) числах. Для нумерованных чисел вариантов n*(n-1) Соответственно, log2(n*(n-1)), округленный вверх до ближайшего целого.
0
|
|
|
1472 / 827 / 140
Регистрация: 12.10.2013
Сообщений: 5,456
|
|
| 10.07.2019, 22:31 | |
|
0
|
|
| 10.07.2019, 22:41 | |
|
Не по теме: Ну, когда в бой вступили такие умы, простым смертным тут делать нечего! Снимаю подписку на тему и самоудаляюсь
0
|
|
|
16 / 13 / 3
Регистрация: 07.10.2016
Сообщений: 115
|
|
| 10.07.2019, 23:24 | |
|
А вопросы в духе "Первое больше чем второе" разве не сильно упрощают жизнь?
Сообщение от Байт
И если числа "плотно прижаты", то может помочь) Например нашли первое -- 80 и вопрос второе больше первого? Ответ: Да. Тогда нам всего-то 20 шишек перебрать) Это тоже как некоторая эвристика логарифма.
0
|
|
|
Диссидент
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
| 11.07.2019, 10:40 | |
|
Сообщение от Tetroghon
Сообщение от Tetroghon
Конечно, можно спросить - "числа равны 37 и 73?" и случайно угадать за 1 вопрос.  Дело все в том, что любой вопрос разбивает множество допустимых пар на 2 множества.
1
|
|
|
134 / 47 / 11
Регистрация: 27.05.2008
Сообщений: 246
|
|
| 11.07.2019, 15:06 | |
|
С двумя числами больше свободы по вопросам, за счет того, что можно рассматривать не только взаимодействия между ними и границами, но и между ними самими.
Типа так: 1) Разность чисел больше 50? Если да, то локализуем одно из них: 2) Меньшее число меньше 25? В зависимости от этого получаем для меньшего числа интервал от 1 до 24 или от 25 до 48. Если от 25 до 48, то второе автоматически локализуется в 76-99. Дихотомией уточняем первое, потом второе (с учетом положения первого). Худший случай: первое число 1 (выясняем это за 2 приведенных выше вопроса, плюс 4 вопроса), второе еще за 5 вопросов - итого 11.
1
|
|
|
Диссидент
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
| 11.07.2019, 17:45 | |
|
Просто_Юлия, да, исхитряться можно по разному. Но того, что каждый вопрос разбивает множество возможных ответов на 2 множества, как ни крути, обойти не удастся.
Вот я и предлагаю (пост 6) построить дерево вопросов для небольшого количества чисел. И если результат (максимальная высота дерева) будет отличаться от указанного в посте 4
Сообщение от Байт
ЗЫ. По поводу "к ответу прибавить 1", тут я мог и лажануться. Ведь округленный до целого логарифм может не подчиняться формуле LOG(A*B) = LOG(A) + LOG(B). Впрочем, тут надо внимательно посмотреть....
0
|
|
|
16 / 13 / 3
Регистрация: 07.10.2016
Сообщений: 115
|
|
| 11.07.2019, 19:18 | |
|
А вопросы в духе "Первое больше чем второе" разве не сильно упрощают жизнь?
Сообщение от Байт
Сообщение от Байт
Есть конкретная задача. И в этой конкретной задаче жизнь может упроститься.Добавлено через 9 минут
Сообщение от Байт
И варианты возможны разные. Ну, асимптотически 1 вопрос погоду не сделает.
Сообщение от Tetroghon
0
|
|
|
1472 / 827 / 140
Регистрация: 12.10.2013
Сообщений: 5,456
|
|
| 11.07.2019, 19:59 | |
|
Сообщение от Tetroghon
Сообщение от Nare6ator
Сообщение от Nare6ator
0
|
|
|
Диссидент
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
| 11.07.2019, 23:30 | |
|
Сообщение от Tetroghon
Сообщение от Tetroghon
Сообщение от Excalibur921
Сообщение от Excalibur921
Сообщение от Tetroghon
Добавлено через 3 минуты
Сообщение от Excalibur921
 Добавлено через 1 час 26 минут [ Не по теме: quote="Tetroghon;13712609"]И если числа "плотно прижаты", то может помочь[/quote]Когда меня учили англицкому, такая история излагалась. Какие-то страшные воины напали на Лаконию и сказали: "if (вы не сдадитесь) мы изнасилуем всех ваших жен ... (и так далее)". Лаконяне ответили просто - "if"
0
|
|
 
|
|
| 12.07.2019, 01:21 | |
|
Сообщение от Байт
Числа от 1 до 8. x>y. Геометрически, в системе координат XOY это точки внутри прямоугольного треугольника с вершинами (2;1), (8;1) и (8;7). 28 точек. Вопросы будут 4-х видов: Большее из двух чисел (т.е. х)<=... ? Меньшее из двух чисел (т.е. y)<=... ? x+y<=... ? x-y<=... ? Ответ на каждый вопрос делит прямоугольный треугольник на два равных прямоугольных треугольника проведением высоты на гипотенузу и вопрос относится к тому, с какой стороны от этой высоты лежит точка с координатами (x;y) (при равенстве на самой высоте). .... начал был строить само дерево... долго всё это расписывать. Да и ТС как-то самоустранился.
1
|
|
|
Диссидент
27710 / 17328 / 3810
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
| 12.07.2019, 10:17 | |
|
Сообщение от jogano
"Будет ли решением одна из пар ... (перечисление)?" Некоторые вопросы такого вида можно задать в более короткой форме типа "Большее из двух чисел (т.е. х)<=... ?", но это совсем не обязательно. del
0
|
|
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
| 12.07.2019, 10:17 | ||||||
|
Помогаю со студенческими работами здесь
17
Имеются числа 1, 5, 25, 625. необходимо определить какое минимальное кол-во чисел нужно использовать, чтобы собрать введенное число
Загадано целое число из интервала [A,B]. Написать программу, которая за минимальное число вопросов отгадает это число
Искать еще темы с ответами Или воспользуйтесь поиском по форуму:
|
|
Новые блоги и статьи
|
||||
|
Обмен данными в микросервисной архитектуре
ArchitectMsa 06.04.2025
Когда разработчики начинают погружаться в мир микросервисов, они часто сталкиваются с парадоксальным правилом: "два сервиса не должны делить один источник данных". Эта мантра звучит повсюду в. . .
|
PostgreSQL в Kubernetes: Автоматизация обслуживания с CNPG
Mr. Docker 06.04.2025
Администраторы баз данных сталкиваются с целым рядом проблем при обслуживании PostgreSQL в Kubernetes: как обеспечить правильную репликацию данных, как настроить автоматическое переключение при. . .
|
Async/await в TypeScript
run.dev 06.04.2025
Асинхронное программирование — это подход к разработке программного обеспечения, при котором операции выполняются независимо друг от друга. В отличие от синхронного выполнения, где каждая последующая. . .
|
Многопоточность в C#: Синхронизация потоков
UnmanagedCoder 06.04.2025
Многопоточное программирование стало неотъемлемой частью разработки современных приложений на C#. С появлением многоядерных процессоров возможность выполнять несколько задач параллельно значительно. . .
|
TypeScript: Классы и конструкторы
run.dev 06.04.2025
TypeScript, как статически типизированный язык, построенный на основе JavaScript, привнес в веб-разработку новый уровень надежности и структурированности кода. Одним из важнейших элементов этой. . .
|
|
Многопоточное программирование: Rust против C++
golander 06.04.2025
C++ существует уже несколько десятилетий и его поддержка параллелизма постепенно наращивалась со временем. Начиная с C++11, язык получил стандартную библиотеку для работы с потоками, а в последующих. . .
|
std::vector в C++: от основ к оптимизации производительности
NullReferenced 05.04.2025
Для многих программистов знакомство с std::vector происходит на ранних этапах изучения языка, но между базовым пониманием и подлинным мастерством лежит огромная дистанция. Контейнер std::vector. . .
|
Реляционная модель и правила Кодда: фундамент современных баз данных
Codd 05.04.2025
Конец 1960-х — начало 1970-х годов был периодом глубоких трансформаций в области хранения и обработки данных. На фоне растущих потребностей бизнеса и правительственных структур существовавшие на тот. . .
|
Асинхронные операции в Django с Celery
py-thonny 05.04.2025
Разработчики Django часто сталкиваются с проблемой, когда пользователь нажимает кнопку отправки формы и. . . ждёт. Секунды растягиваются в минуты, терпение иссякает, а интерфейс приложения замирает. . . .
|
Использование кэшей CPU: Максимальная производительность в Go
golander 05.04.2025
Разработчикам хорошо известно, что эффективность кода зависит не только от алгоритмов и структур данных, но и от того, насколько удачно программа взаимодействует с железом. Среди множества факторов,. . .
|
Наверх
