Подготовка документации.

Самое главное - оформлять в том виде, в котором хотелось бы читать.

1. Следует учесть, что ваше описание должны понять люди, не владеющие предметной областью.

2. Описать план алгоритма «сверху – вниз».

3. Описать форматы данных и требования к вводу - выводу.

Примеры.

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

4. Указать условия функционирования и ограничения. Указать также, в каких случаях программа работает, а в каких не работает или работает плохо.

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

6. Приложить описание тестовых примеров и результаты тестирования.

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

Ниже приводится описание алгоритма генератора перестановок.

Генератор перестановок. (Без доказательства)

1. Располагаем исходную перестановку в порядке убывания. (n … 321)

2. Находим наименьший индекс i, i{2..n},при котором a_i-1>a_i

3. Находим наименьший индекс j, j{1,2,…i-1},при котором a_j>a_i

4. Меняем местами a_j и a_i

5. Вычислим k=[^i-1/₂]. Если к=0, то ничего не делаем. Если к0, то меняем местами компоненты в парах: (a₁,a_i-1), (a₂,a_i-2), … , (a_k,a_i-k).

6. Выводим перестановку и если она больше чем 123 … n, то возвращаемся к шагу 2. (или завести счетчик перестановок, он должен быть равен n!)

Пример

1) 321 i=2, k=0

2) 231 i=3, k=1

132

3) 312 i=2, k=0

4) 132 i=3, k=1

123

5) 213 i=2, k=0

6) 123

Задание к практической работе:

1. Решение задачи коммивояжера: Программирование исчерпывающего алгоритма для задачи коммивояжера. Указание:

2. Дополнить задачу коммивояжера (исчерпывающий алгоритм) процедурой генератора перестановок

3. Докажите, что если матрица стоимостей в задаче коммивояжера с n городами симметрична, то число разных по стоимости путей (гамильтоновых циклов) равно (n-1)!/2