Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - [47]
Ответ: O(n2).
Глава 5
Какие из следующих функций являются последовательными?
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
Примените алгоритм поиска в ширину к каждому из этих графов, чтобы найти решение.
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 — дерево. В последнем примере дерево просто повернуто набок. Деревья составляют подкатегорию графов, поэтому любое дерево является графом, но граф не обязательно является деревом.
Глава 7
7.1 Каков вес кратчайшего пути от начала до конца в каждом из следующих графов?
Ответы: A — 8; B — 60; C — каверзный вопрос (кратчайший путь не существует из-за наличия цикла с отрицательным весом).
Глава 8
8.1 Вы работаете в фирме по производству мебели и поставляете мебель по всей стране. Коробки с мебелью размещаются в грузовике. Все коробки имеют разный размер, и вы стараетесь наиболее эффективно использовать доступное пространство. Как выбрать коробки для того, чтобы загрузка имела максимальную эффективность? Предложите жадную стратегию. Будет ли полученное решение оптимальным?
Ответ: Жадная стратегия заключается в том, чтобы выбрать самую большую коробку, помещающуюся в оставшемся пространстве, и повторять это до тех пор, пока еще можно выбрать хотя бы одну коробку. Нет, такое решение оптимальным не будет.
8.2 Вы едете в Европу, и у вас есть 7 дней на знакомство с достопримечательностями. Вы присваиваете каждой достопримечательности стоимость в баллах (насколько вы хотите ее увидеть) и оцениваете продолжительность поездки. Как обеспечить максимальную стоимость (увидеть все самое важное) во время поездки? Предложите жадную стратегию. Будет ли полученное решение оптимальным?
Ответ: Выбирайте достопримечательность с наибольшей стоимостью в баллах, которую вы успеете посетить в оставшееся время. Остановитесь, когда таких достопримечательностей не останется. Нет, такое решение оптимальным не будет.
Для каждого из приведенных ниже алгоритмов укажите, является ли этот алгоритм жадным или нет.
8.3 Быстрая сортировка.
Ответ: Нет.
8.4 Поиск в ширину.
Ответ: Да.
8.5 Алгоритм Дейкстры.
Ответ: Да.
8.6 Почтальон должен доставить письма в 20 домов. Ему нужно найти кратчайший путь, проходящий через все 20 домов. Является ли эта задача NP-полной?
Ответ: Да.
8.7 Имеется задача поиска максимальной клики в множестве людей (кликой называется множество людей, каждый из которых знаком со всеми остальными.) Является ли эта задача NP-полной?
Ответ: Да.
8.8 Вы рисуете карту США, на которой два соседних штата не могут быть окрашены в одинаковый цвет. Требуется найти минимальное количество цветов, при котором любые два соседних штата будут окрашены в разные цвета. Является ли эта задача NP-полной?
Ответ: Да.
Глава 9
9.1 Предположим, к предметам добавился еще один: MP3-плеер. Он весит 1 фунт и стоит $1000. Стоит ли брать его?
