Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - страница 58

Ответ:

def sum(list):

  if list == []:

    return 0

  return list[0] + sum(list[1:])

4.2 Напишите рекурсивную функцию для подсчета элементов в списке.

Ответ:

def count(list):

  if list == []:

    return 0

  return 1 + count(list[1:])

4.3 Найдите наибольшее число в списке.

Ответ:

def max(list):

  if len(list) == 2:

    return list[0] if list[0] > list[1] else list[1]

  sub_max = max(list[1:])

  return list[0] if list[0] > sub_max else sub_max

4.4 Помните бинарный поиск из главы 1? Он тоже относится к классу алгоритмов «разделяй и властвуй». Сможете ли вы определить базовый и рекурсивный случай для бинарного поиска?

Ответ: Базовым случаем для бинарного поиска является массив, содержащий всего один элемент. Если искомый элемент совпадает с элементом массива – вы нашли его! В противном случае элемент в массиве отсутствует.

В рекурсивном случае для бинарного поиска массив делится пополам, одна половина отбрасывается, а для другой половины проводится бинарный поиск.

Запишите «O-большое» для каждой из следующих операций.

4.5 Вывод значения каждого элемента массива.

Ответ: O(n).

4.6 Удвоение значения каждого элемента массива.

Ответ: O(n).

4.7 Удвоение значения только первого элемента массива.

Ответ: O(1).

4.8 Создание таблицы умножения для всех элементов массива. Например, если массив состоит из элементов [2, 3, 7, 8, 10], сначала каждый элемент умножается на 2, затем каждый элемент умножается на 3, затем на 7 и т.д.

Ответ: O(n2).

Какие из следующих функций являются последовательными?

5.1 f(x) = 1   

Ответ: Функция последовательна.

5.2 f(x) = rand()   

Ответ: Функция непоследовательна.

5.3 f(x) = next_empty_slot()   

Ответ: Функция непоследовательна.

5.4 f(x) = len(x)   

Ответ: Функция последовательна.

Предположим, имеются четыре хеш-функции, которые получают строки.

1. Первая функция возвращает «1» для любого входного значения.

2. Вторая функция возвращает длину строки в качестве индекса.

3. Третья функция возвращает первый символ строки в качестве индекса. Таким образом, все строки, начинающиеся с «a», хешируются в одну позицию, все строки, начинающиеся с «b», — в другую и т.д.

4. Четвертая функция ставит в соответствие каждой букве простое число: a = 2, b = 3, c = 5, d = 7, e = 11 и т.д. Для строки хеш-функцией становится остаток от деления суммы всех значений на размер хеша. Например, если размер хеша равен 10, то для строки «bag» будет вычислен индекс 3 + 2 + 17 % 10 = 22 % 10 = 2.

В каком из этих примеров хеш-функции будут обеспечивать хорошее распределение? Считайте, что хеш-таблица содержит 10 элементов.

5.5 Телефонная книга, в которой ключами являются имена, а значениями — номера телефонов. Задан следующий список имен: Esther, Ben, Bob, Dan.

Ответ: Хеш-функции С и D обеспечивают хорошее распределение.

5.6 Связь размера батарейки с напряжением. Размеры батареек: A, AA, AAA, AAAA.

Ответ: Хеш-функции B и D обеспечивают хорошее распределение.

5.7 Связь названий книг с именами авторов. Названия книг: «Maus», «Fun Home», «Watchmen».

Ответ: Хеш-функции B, С и D обеспечивают хорошее распределение.

Примените алгоритм поиска в ширину к каждому из этих графов, чтобы найти решение.

6.1 Найдите длину кратчайшего пути от начального до конечного узла.

Ответ: Длина кратчайшего пути равна 2.

6.2 Найдите длину кратчайшего пути от «cab» к «bat».

Ответ: Длина кратчайшего пути равна 2.

6.3 Перед вами небольшой граф моего утреннего распорядка.

Для каждого из следующих трех списков укажите, действителен он или недействителен.

Ответы: A — недействителен; B — действителен; С — недействителен.

6.4 Немного увеличим исходный граф. Постройте действительный список для этого графа.

Ответ: 1 — Проснуться; 2 — Сделать зарядку; 3 — Принять душ; 4 — Почистить зубы; 5 — Одеться; 6 — Упаковать обед; 7 — Позавтракать.

6.5 Какие из следующих графов также являются деревьями?

Ответы: A — дерево; B — не дерево; C — дерево. В последнем примере дерево просто повернуто набок. Деревья составляют подкатегорию графов, поэтому любое дерево является графом, но граф не обязательно является деревом.