2001-gre-vs-practice.pdf/Q03 — различия между версиями
Urmat A (обсуждение | вклад) (→Вопрос: Q03-e5724f) |
Urmat A (обсуждение | вклад) (→Вопрос: Q03-e5724f) |
||
| Строка 7: | Строка 7: | ||
{{reserve-task|[[Участник:Urmat A|Urmat A]] 19:03, 19 декабря 2024 (UTC)}} | {{reserve-task|[[Участник:Urmat A|Urmat A]] 19:03, 19 декабря 2024 (UTC)}} | ||
{{reserve-task|[[Участник:Urmat A|Urmat A]] 15:54, 19 декабря 2024 (UTC)}} | {{reserve-task|[[Участник:Urmat A|Urmat A]] 15:54, 19 декабря 2024 (UTC)}} | ||
| + | {{reserve-task|[[Участник:Urmat A|Urmat A]] 19:04, 19 декабря 2024 (UTC)}} | ||
{{reserve-task|[[Участник:Urmat A|Urmat A]] 19:04, 19 декабря 2024 (UTC)}} | {{reserve-task|[[Участник:Urmat A|Urmat A]] 19:04, 19 декабря 2024 (UTC)}} | ||
{{reserve-task|[[Участник:Urmat A|Urmat A]] 19:04, 19 декабря 2024 (UTC)}} | {{reserve-task|[[Участник:Urmat A|Urmat A]] 19:04, 19 декабря 2024 (UTC)}} | ||
| Строка 24: | Строка 25: | ||
{{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 | + | Можно пройтись бинарным поиском[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 вопросов. |
Версия 19:05, 19 декабря 2024
Задача зарезервирована: Urmat A 18:47, 19 декабря 2024 (UTC)
Задача зарезервирована: Urmat A 19:01, 19 декабря 2024 (UTC)
Задача зарезервирована: Urmat A 19:01, 19 декабря 2024 (UTC)
Задача зарезервирована: Urmat A 19:02, 19 декабря 2024 (UTC)
Задача зарезервирована: Urmat A 19:02, 19 декабря 2024 (UTC)
Задача зарезервирована: Urmat A 19:03, 19 декабря 2024 (UTC)
Задача зарезервирована: Urmat A 15:54, 19 декабря 2024 (UTC)
Задача зарезервирована: Urmat A 19:04, 19 декабря 2024 (UTC)
Задача зарезервирована: Urmat A 19:04, 19 декабря 2024 (UTC)
Задача зарезервирована: Urmat A 19:04, 19 декабря 2024 (UTC)
Вопрос: Q03-e5724f
Боб загадал число от 1 до 1000. Мэри должна угадать это число, спрашивая у Боба вопрос на "Да или Нет". Она знает, что он никогда не врёт. Используя оптимальную стратегию, сколько вопросов ей придётся задать в худшем случае, чтобы найти число?
Ответы
- 1000
- 999
- 500
- 32
- Правильный ответ: 10
Объяснение
Исходники — вопрос 3 на 12 странице книги «2001-gre-vs-practice.pdf»
Можно пройтись бинарным поиском[1], это оптимально. Идея в том, чтобы каждый раз делить числовой отрезок на 2 и выбирать тот, что нужно. Есть число 1024, оно же 2^10. А 1000<1024, поэтому максимум ей потребуется 10 вопросов.
Решено: Urmat A 19:05, 19 декабря 2024 (UTC)