10. Если бы нужно было найти подпоследовательность с наиболее близкой к нулю суммой, как бы вы это сделали? Каков был бы наиболее эффективный алгоритм? Какие методы разработки алгоритмов можно было бы использовать для его написания? Как найти подпоследовательность с суммой, наиболее близкой к некоторому вещественному числу /?
И. Магистраль состоит из п-1 перегонов между п пунктами платежей за перевозку. За каждый перегон нужно платить свою сумму денег. Легко определить стоимость пути между любыми двумя станциями с помощью массива стоимостей за время О(п) или за постоянное время с помощью таблицы с 0(п2) записей. Опишите структуру данных, требующую 0(п) ячеек памяти, но позволяющую находить результат за постоянное время.
12. После инициализации массива х[0..п-1] нулями выполняется п следующих операпий:
for i = [1. u] x[i] += v
где I, u и v — параметры каждой операции (I и и — целые числа, причем 0 <= I <= u < п, a v — вещественное число). После п операций выводятся значения элементов х [0..п-1]. Описанный алгоритм требует 0(п2) операций. Можете ли вы сделать ту же задачу более производительной?
13. Имеется массив n х п вещественных чисел. В нем нужно найти прямоугольную подтаблицу с максимальной суммой элементов. Какова вычислительная сложность данной задачи?
14. Даны целые числа типи вещественный массив х[п], требуется найти целое i (0<=i<=n-m), такое, что сумма x[i]..x[i+m] максимально близка к нулю.
15. Найдите решение рекуррентного соотношения Т(п) - 2Т(п 12) + сп при Г(1) = 0, а п — степень двойки. Докажите результат но методу математической индукции. Что изменится, если Т( 1) = с?
8.8. Дополнительная литература
Только глубокое знание теории и большой опыт дают возможность использовать любые методы разработки алгоритмов. Большинству программистов для их изучения нужно обратиться к учебнику по теории алгоритмов. «Структуры данных и алгоритмы» Аго, Хопкрофта и Ульмана (Aho, Hopcroft and Ullman, Data Structures and Algorithms, Addison Wesley, 1983) — подходящий учебник для студентов. Содержимое главы 10 очень близко к данной теме.
Книга Кормена, Лейзерсона и Ривеста «Введение в алгоритмы» (Cormen, Leisersonand Rivest, Introduction to Algorithms, MIT Press, 1990) объемом в 1000 страниц содержит подробное изложение данной темы. Части 1, 2 и 3 содержат основы теории алгоритмов, методы сортировки и поиска. Часть 4 особенно близка к теме данной главе. Части 5,6 и 7 посвящены сложным структурам данных, алгоритмам на графах и другим избранным темам.
Эта и семь других книг вышли на компакт-диске Dr. Dobb’s Essential Book on Algorithms and Data Structures. Диск был выпущен в 1999 году корпорацией Miller Freeman. Это бесценный справочник для любого программиста, интересующегося алгоритмами и структурами данных. На момент выхода моей книги в печать электронную версию компакт-диска можно заказать по адресу: http://www.ddj.com.
Опубликовал vovan666
April 17 2013 00:00:51 ·
0 Комментариев ·
3880 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
