Реферат: Методика создания программ

Нам нужна методика создания ясных, правильных, эффективных программ.

Ясность означает, что любой, кто знаком с языком Pascal и прикладной областью, поймет алгоритм, читая текст программы, комментарии и спецификацию проблемы.

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

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

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

Давайте напишем небольшую программу, сосредоточив теперь наше внимание именно на процессе её создания. Пусть к нам обратились с просьбой написать программу на Pascal, которая размещает компоненты вектора в возрастающем порядке. Пусть после общения с заказчиком нам удалось выяснить, что:

компонентами вектора могут быть только натуральные числа;

компонентов всегда 100;

все компоненты попарно различны.

Мы уже специфицировали исходные данные для этой задачи в лекции 7. Там исходные данные мы специфицировали так:

Q₁ = "i : 1 £i £ 100 :v_i ÎN Ù v_i >0.

Теперь надо выразить тот факт, что все компоненты различны:

Q₂ = "i : 1 £i £ 100 : Ø$j : 1 £ j £ 100 : v_i = v_j Ù i¹j.

Отсюда спецификация исходных данных выглядит так:

Q=Q₁ ÙQ₂ ="i : 1 £i £ 100 : (v_i ÎN Ù v_i >0)ÙØ$j : 1 £ j £ 100 : v_i = v_j Ù i¹j .

Спецификация множества возможных результатов там была записана в следующей форме:

"i : 1 £i < 100 :(o_i ÎN Ù o_i >0 Ù o₁₀₀ ÎN Ù o₁₀₀ >0 Ù o_i <o_i+1 )Ù

"i : 1 £i £ 100 : $k : 1 £ k £ 100 : v_i =o_k .

Основные шаги нашего алгоритма представлены на рис. 13.1. Нам надо лишь детализировать шаг “Обработка данных”. Для упорядочения компонентов вектора по возрастанию мы воспользуемся известным алгоритмом сортировки, называемым линейный выбор.

Суть этого алгоритма состоит в том, что в цикле по числу компонентов вектора

выбираем наименьший;

размещаем его в первом свободном компоненте результирующего вектора;

наименьший компонент в исходном векторе заменён на предопределённую величину, не встречающуюся в исходном векторе.

Так мы действуем до тех пор, пока не заполним все компоненты вектора - результата. Это алгоритм правильно упорядочивает компоненты исходного вектора. Доказательство его корректности можно посмотреть в книге Г. Ларина “Сортировка и системы сосртировки” Наука 1984 г.

Мы адаптируем этот алгоритм применительно к нашим условиям, а именно:

числу компонентов в рассматриваемых векторах;

типам компонентов наших векторов;

именам наших переменных;

в качестве предопределённой величины, которая используется в алгоритме для замены наименьшего компонента исходного вектора, возьмём - 1