2001-gre-vs-practice.pdf/Q03 — различия между версиями
Материал из DISCOPAL
Urmat A (обсуждение | вклад) (→Вопрос: Q03-e5724f) |
StasFomin (обсуждение | вклад) |
||
| (не показаны 2 промежуточные версии 1 участника) | |||
| Строка 1: | Строка 1: | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Вопрос: Q03-e5724f == | == Вопрос: Q03-e5724f == | ||
| − | Боб загадал число от 1 до 1000. Мэри должна угадать это число, спрашивая у Боба вопрос на | + | Боб загадал число от 1 до 1000. Мэри должна угадать это число, спрашивая у Боба вопрос на «Да или Нет». Она знает, что он никогда не врёт. Используя оптимальную стратегию, сколько вопросов ей придётся задать в худшем случае, чтобы найти число? |
=== Ответы === | === Ответы === | ||
| − | + | * 1000 | |
| − | + | * 999 | |
| − | + | * 500 | |
| − | + | * 32 | |
| − | + | * Правильный ответ: 10 | |
=== Объяснение === | === Объяснение === | ||
| Строка 24: | Строка 14: | ||
{{cstest-source|2001-gre-vs-practice.pdf|12|3}} | {{cstest-source|2001-gre-vs-practice.pdf|12|3}} | ||
| − | Можно пройтись | + | Можно пройтись [https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA бинарным поиском ], это оптимально. |
| + | * Идея в том, чтобы каждый раз делить числовой отрезок на 2 и выбирать тот, что нужно. | ||
| + | * Есть число 1024, оно же 2^10. | ||
| + | * А 1000<1024, поэтому максимум ей потребуется 10 вопросов. | ||
| − | {{question-ok | + | {{question-ok|[[Участник:StasFomin|StasFomin]] 21:09, 19 декабря 2024 (UTC)}} |
| − | + | ||
| − | [[Категория: | + | [[Категория:Бинарный поиск]] |
Текущая версия на 21:09, 19 декабря 2024
Вопрос: Q03-e5724f
Боб загадал число от 1 до 1000. Мэри должна угадать это число, спрашивая у Боба вопрос на «Да или Нет». Она знает, что он никогда не врёт. Используя оптимальную стратегию, сколько вопросов ей придётся задать в худшем случае, чтобы найти число?
Ответы
- 1000
- 999
- 500
- 32
- Правильный ответ: 10
Объяснение
Исходники — вопрос 3 на 12 странице книги «2001-gre-vs-practice.pdf»
Можно пройтись бинарным поиском , это оптимально.
- Идея в том, чтобы каждый раз делить числовой отрезок на 2 и выбирать тот, что нужно.
- Есть число 1024, оно же 2^10.
- А 1000<1024, поэтому максимум ей потребуется 10 вопросов.