2001-gre-vs-practice.pdf/Q03 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Вопрос: Q03-e5724f)
(Вопрос: 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)}}
 
== Вопрос: Q03-e5724f ==
 
== Вопрос: Q03-e5724f ==
Строка 23: Строка 24:
 
{{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, оно же <m>2^10</m>. А 1000<1024, поэтому максимум ей потребуется 10 вопросов.
+
Можно пройтись бинарным поиском[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<m>^10</m>. А 1000<1024, поэтому максимум ей потребуется 10 вопросов.
  
  
 
{{question-ok|}}
 
{{question-ok|}}
{{checkme|[[Участник:Urmat A|Urmat A]] 19:04, 19 декабря 2024 (UTC)}}
+
{{checkme|[[Участник:Urmat A|Urmat A]] 19:05, 19 декабря 2024 (UTC)}}
  
 
[[Категория:Надо не забыть выбрать тему]]
 
[[Категория:Надо не забыть выбрать тему]]

Версия 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)

Вопрос: Q03-e5724f

Боб загадал число от 1 до 1000. Мэри должна угадать это число, спрашивая у Боба вопрос на "Да или Нет". Она знает, что он никогда не врёт. Используя оптимальную стратегию, сколько вопросов ей придётся задать в худшем случае, чтобы найти число?

Ответы

  1. 1000
  2. 999
  3. 500
  4. 32
  5. Правильный ответ: 10

Объяснение

Исходники — вопрос 3 на 12 странице книги «2001-gre-vs-practice.pdf»

Можно пройтись бинарным поиском[1], это оптимально. Идея в том, чтобы каждый раз делить числовой отрезок на 2 и выбирать тот, что нужно. Есть число 1024, оно же 2. А 1000<1024, поэтому максимум ей потребуется 10 вопросов.Check-me-animated.gif Решено: Urmat A 19:05, 19 декабря 2024 (UTC)