Грокаем алгоритмы

Что же в действительности использует сервис Facebook? Вероятно, десяток разных баз данных, за которыми стоят разные структуры данных: хеш-таблицы, в-деревья и т.д. Массивы и связанные списки становятся структурными элементами для построения более сложных структур данных.

Глава 3

3.1 Предположим, имеется стек вызовов следующего вида:

Что можно сказать о текущем состоянии программы на основании этого стека вызовов?

Ответ: Некоторые наблюдения, о которых вы могли бы упомянуть:

• сначала вызывается функция greet для переменной name= maggie;

• затем функция greet вызывает функцию greet2 для переменной name = maggie;

• на этой стадии функция greet находится в незавершенном, приостановленном состоянии;

• текущим вызовом функции является вызов greet2;

• после завершения этого вызова функция greet продолжит выполнение.

3.2 Предположим, вы случайно написали рекурсивную функцию, которая бесконечно вызывает саму себя. Как вы уже видели, компьютер выделяет память в стеке при каждом вызове функции. А что произойдет со стеком при бесконечном выполнении рекурсии?

Ответ: Стек будет расти бесконечно. Каждой программе выделяется ограниченный объем памяти в стеке. Когда все пространство будет исчерпано (а рано или поздно это произойдет), программа завершится с ошибкой переполнения стека.

Глава 4

4.1 Напишите код для функции sum (см. выше).

Ответ:

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

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

5.1 f(x) = 1      Возвращает "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

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

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

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