2011-gre-cs-practice-book.pdf/Q63 — различия между версиями
Материал из DISCOPAL
| Строка 1: | Строка 1: | ||
== Вопрос: Q63-08c765 == | == Вопрос: Q63-08c765 == | ||
| + | Алгоритм берет список из <m>2^n</m> чисел <m>[a_1, a_2, \ldots, a_{2^n}]</m> и заменяет его на <m>[b_1, b_2, \ldots, b_{2^{n-1}}]</m>, где | ||
| + | <m>b_1 = \max \{a_1, a_2\}</m>, <m>b_2 = \max \{a_3, a_4\}</m> и так далее. Затем он выполняет ту же операцию на получившемся списке (заменяя каждую пару последовательных элементов их максимумом) и продолжает это делать до тех пор, пока в списке не останется только два элемента. Например, если исходный список — <m>[3, 7, 6, 8, 2, 1, 4, 5]</m>, то после первого шага он становится <m>[7, 8, 2, 5]</m>, а затем <m>[8, 5]</m>. | ||
| − | + | Предположим, что элементы исходного списка — целые числа от 1 до 64 в случайном порядке. Какова вероятность того, что число 63 появится в финальном списке из двух элементов? | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
=== Ответы === | === Ответы === | ||
| − | |||
| − | |||
| − | * | + | * <m>\frac{1}{63}</m> |
| − | * | + | * <m>\frac{1}{4}</m> |
| − | * | + | * Правильный ответ: <m>\frac{32}{63}</m> |
| − | + | * <m>\frac{62}{63}</m> | |
| − | + | * 1 | |
| − | + | ||
| − | < | + | |
| − | + | ||
| − | + | ||
=== Объяснение === | === Объяснение === | ||
| − | + | {{cstest-source|2011-gre-cs-practice-book.pdf|44|63}} | |
| − | {{cstest-source|2011-gre-cs-practice-book.pdf| | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | |||
{{question-ok|}} | {{question-ok|}} | ||
{{reserve-task|[[Участник:Nikitashapovalov|Nikitashapovalov]] 20:51, 8 января 2025 (UTC)}} | {{reserve-task|[[Участник:Nikitashapovalov|Nikitashapovalov]] 20:51, 8 января 2025 (UTC)}} | ||
Версия 21:37, 11 января 2025
Вопрос: Q63-08c765
Алгоритм берет список из чисел и заменяет его на , где , и так далее. Затем он выполняет ту же операцию на получившемся списке (заменяя каждую пару последовательных элементов их максимумом) и продолжает это делать до тех пор, пока в списке не останется только два элемента. Например, если исходный список — , то после первого шага он становится , а затем .
Предположим, что элементы исходного списка — целые числа от 1 до 64 в случайном порядке. Какова вероятность того, что число 63 появится в финальном списке из двух элементов?
Ответы
- Правильный ответ:
- 1
Объяснение
Исходники — вопрос 63 на 44 странице книги «2011-gre-cs-practice-book.pdf»
Задача зарезервирована: Nikitashapovalov 20:51, 8 января 2025 (UTC)