Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [ 5 ] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

было распознать, то их можно было бы избежать. К сожалению, данная область исследований еще не достигла такого уровня, при котором мы можем выявлять такие вводы, но к этому надо стремиться.

Документация

На самом деле этап документации не является последним шагом в процессе полного построения алгоритма. В частности, он не заключается в том, чтобы добавить карты с комментариями, когда вы закончили все остальное. Процесс документации должен переплетаться со всем процессом построения алгоритма, и особенно с этапами разработки и реализации.

Трудно читать чужую программу в коде. Наиболее очевидный мотив для документации - дать возможность людям понять программы, которые написаны другими. Конечно, лучший способ - это составить программу настолько понятно, чтобы она сама себя поясняла. Но это невозможно осуществить ни для каких программ, кроме простейших; и программа в коде должна быть дополнена другими формами пояснений. Обычно для этого используются карты с комментариями.

Но в действительности это только надводная часть айсберга. Документация включает в себя всю информацию и помогает объяснить, что делается в программе, т. е., в частности, блок-схемы, описания ступеней в вашем построении сверху-вниз, вспомогательные доказательства правильности, результаты тестирования, детальные описания формата и требований к вводу/выводу и т. д. В разд. 4.3 проводится более детальное обсуждение документации. В настоящий момент предлагаем вам золотое правило: оформляйте ваши программы в таком виде, в каком вам хотелось бы видеть программы, написанные другими.

Упражнения 1.3

1.3.1. Решение задачи коммивояжера. Найдите оптимальное решение задачи коммивояжера, изображенной на рис. 1.3.1, применив алгоритм ETS из данного раздела.

1.3.2. Факториалы (проверка). Каково наибольшее целое положительное N, такое, что N\ уложится точно в одпо слово вашей ЭВМ? Предскажите аналитически свой ответ прежде, чем выходить на машину. Хорошо подумайте. Какие ухищрения можно использовать, чтобы втиснуть в слово как можно большее число?

1.3.3. Кодироюние- декодирование (полное построение). Один элементарный шифр состоит в том, чтобы поставить буквы алфавита во взаимно-однозначное соответствие с буквами пересортированного алфавита. Например, если соответствие следующее:

Алфавит: ABCDEFGHIJKLMNOPQRSTUVWXYZ EyKBbL кода: MTJCZEOKLNSUXYADFBWVG Н I Р R Q,

тогда слово CODE будет зашифровано как JACZ.

Постройте, реализуйте, проверьте и оформите документацией алгоритм, для которого код является вводом и который кодирует и декодирует произвольные записи.



1.3.4. Перестатвки (доказательстео). Покажите, что число перестановок первых п целых положительных чисел равно п\ .

1.3.5. Генератор перестановок {полное построение). Полностью постройте алгоритм, генерирующий все перестановки первых п целых положительных чисел. Подойдет ли ваш алгоритм для шага 2 алгоритма ETS?

1.3.6. Построение туров (разработка). Постройте подалгоритм для построения туров в шаге 3 алгоритма ETS.

1.3.7. Чшло туров коммивояжера (доказательстео). Покажите, что если матрица стоимостей С в задаче коммивояжера с п городами симметрична, т. е. cij=Cji р.ля всех i и /, то число разных туров равно (п-1)1/2. Два тура считаются разными, если им не соответствуют в точности одинаковые последовательности городов.

1.3.8. Алгебра сложности.

(а) Покажите, что /(/г)=3.7к+100.8/г+10 имеет порядок О(и) при «->- оо.

(б) Покажите, что /(/г)=2«/100-100 имеет порядок 0(2") при п- со.

(в) Покажите, что п1 имеет порядок 0(п") при п-у со.

(г) Покажите, что 2" возрастает при к оо быстрее, чем любой полином от п конечной степени.

1.3.9. Предположение в задаче коммивояжера (модель и разработка). Рассмотрим матрицу стоимостей С задачи коммивояжера с п городами. Если мы выберем п элементов из С таким образом, что в точности один элемент будет выбран из каждой строки и каждого столбца, будут ли отрезки пути, соответствующие этим элементам, образовывать тур?

1.3.10. Римские цифры (полное построение). Постройте алгоритм, преобразовывающий произвольное положительное целое число, записанное в арабских цифрах, в систему римских цифр и наоборот.

1.3.11. Стороны треугольника (полное построение). Для произвольной тройки чисел (х, у, г) полностью постройте алгоритм, определяющий, существует ли треугольник Т со сторонами х, у к г.

*1.3.12. Перестановки (сравнение алгоритмов). Разработайте и реализуйте два разных алгоритма для генерирования случайных перестановок.Сравнитс их эффективность.

*1.3.13. Факториалы (разработка). Разработайте алгоритм, вычисляющий значение функции F{n)=m, где т - число знаков, содержащихся в десятичной записи «!

1.3.14. Экспоненциальные функции (сложность). Разработайте алгоритм, который будет определять, сколько времени потребуется вашей ЭВМ для выполнения 2", к" и к! элементарных операций, для п=1, 2, 3, . . . , 50.

*1.3.15. Экспоненциальные функции (сложность). Разработайте алгоритм для вычисления G(m, n)=k, где k определяется следующим образом: R-i-<mВычислите некоторые значения G(m, п).

L1.3.16. Программный профиль (сложность, проверка). Профиль программы для данного ввода - это, по существу, гистограмма, показывающая, сколько раз выполняется каждый оператор программы во время ее работы.

Реализуйте алгоритм МАХ из разд. 1.2. Для n=20 создайте входной массив равномерно распределенных на отрезке [О, 100] чисел, используя датчик случайных чисел. Постройте усредненный профиль для вашей программы, основанный на испытании 50 вводимых наборов.



Глава 2. Некоторые основные приемы и алгоритмы

Есть несколько основных приемов, которыми должен уметь пользоваться каждый, кто разрабатывает и анализирует алгоритмы. В этой главе мы представим некоторые фундаментальные теоретические положения и алгоритмы из четырех различных областей: структурное программирование сверху-вниз, сети, структуры данных и вероятность и статистика. Материалом этих разделов мы будем пользоваться на протяжении всей книги.

2.1. Структурное программирование сверху-вниз и правильность программ

Математическая функция /: X-Y может быть определена как правило, которое каждому элементу х из некоторого множества X, называемого областью определения, ставит в соответствие (единственное) значение у из некоторого множества Y, называемого областью значений. Конкретную функцию / из данного множества X в данную область У можно полностью описать одним из двух способов: либо приведя таблицу упорядоченных пар [х, f{x)], указывающих для каждого аргумента хХ значение функции f{x); либо указав правило вычисления или набор правил (т. е. алгоритм), который позволяет для значения X вычислять значение f{x). Второй способ необходим тогда, когда область определения функции X является либо бесконечным, либо очень большим конечньм множеством.

Первое, что требуется от алгоритма, это правильно реализовывать данную функцию /: Х-У. Другими словами, каждый алгоритм служит для определения функции а: Х-У из множества X допустимых исходных данных в область У возможных результатов. Алгоритм является правильной реализацией функции /, если ХХ и УУ и если

f{x)=a{x) для каждого хХ.

Второе это то, что от алгоритма требуется такая реализация функции, чтобы время и требуемые усилия для вычисления произвольного значения f{x)=a{x) были по возможности наименьшими.

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

Последнее требование важно главньш образом потому, что по мере того, как алгоритмы становятся все более и более сложными, соот-



[0] [1] [2] [3] [4] [ 5 ] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0013