2011-gre-cs-practice-book.pdf/Q03

Вопрос: Q03-08c765

Предположим, что любое n-битное положительное целое число x хранится в виде связного списка битов так, что первый элемент списка является наименее значимым битом. Например, x = 14 = 1110₂ хранится как связный список (0,1,1,1) размера n = 4.

Для этой структуры данных операция, которая заменяет x на (целочисленное деление x на 8 с округлением вниз), может быть выполнена за:

Ответы

• Правильный ответ:

Объяснение

Исходники — вопрос 3 на 15 странице книги «2011-gre-cs-practice-book.pdf»

Верный ответ (константное время).

Результат выполнения функции f():

Начальное состояние: result = 0 k = 0

• Шаг 1: k = 0 -> k % 3 = 0 -> 0 != 1 -> result = 0 + 1 = 1

• Шаг 2: k = 1 -> k % 3 = 1 -> 1 == 1 -> result = 1 + 1 = 2

• Шаг 3: k = 2 -> k % 3 = 2 -> 2 != 1 -> result = 2 + 1 = 3

• Шаг 4: k = 3 -> k % 3 = 0 -> 0 != 1 -> result = 3 + 1 = 4

• Шаг 5: k = 4 -> k % 3 = 1 -> 1 == 1 -> result = 4 + 4 = 8

Функция завершается, возвращая значение result = 8

Самопроверка: - цикл выполнился 5 раз (k от 0 до 4) - условие k % 3 == 1 выполнилось дважды: при k = 1 и k = 4 - в остальных случаях добавлялась единица

Задача зарезервирована: Markvernikov 10:19, 18 декабря 2024 (UTC)

Решено: Markvernikov 11:07, 18 декабря 2024 (UTC)

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.