2011-gre-cs-practice-book.pdf/Q03 — различия между версиями
| Строка 7: | Строка 7: | ||
=== Ответы === | === Ответы === | ||
| − | * | + | * <m>\Theta(1) шагов</m> |
| − | * | + | * <m>\Theta(log n) шагов</m> |
| − | * | + | * <m>\Theta(n) шагов</m> |
| − | * | + | * <m>\Theta(n log n) шагов</m> |
| − | * | + | * <m>\Theta(n²) шагов</m> |
=== Объяснение === | === Объяснение === | ||
Версия 10:33, 18 декабря 2024
Вопрос: Q03-08c765
Предположим, что любое n-битное положительное целое число x хранится в виде связного списка битов так, что первый элемент списка является наименее значимым битом. Например, x = 14 = 11102 хранится как связный список (0,1,1,1) размера n = 4.
Для этой структуры данных операция, которая заменяет x на ⌊x/8⌋ (целочисленное деление x на 8 с округлением вниз), может быть выполнена за:
Ответы
Объяснение
Сначала заполните номер страницы с этим вопросом Исходники — вопрос 3 на 15 странице книги «2011-gre-cs-practice-book.pdf»
Если все сделаете правильно, по ссылке выше будет открываться правильная страница в правильном PDFе.
Ну и наконец, вики-разметкой напишите ваше понимание, почему правильный ответ — правильный, а неправильные варианты — неправильны. Тут тоже могут быть полезны ссылки на википедию, решение вами рекуррентных уравнений в sympy.
Задача зарезервирована: Markvernikov 10:19, 18 декабря 2024 (UTC)