Основные принципы разработки и анализа алгоритмов

 

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

При дедуктивном подходе рассматривается частный случай общеизвестныхалгоритмических моделей. Здесь при заданных предположениях известный алгоритм приспосабливается к условиям решаемой задачи. Например, многие вычислительные задачи линейной алгебры, в частности, нелинейные уравнения, системы алгебраических уравнений и т.п., могут быть решены с использованием известных методов и алгоритмов, для которых существует множество специальных библиотек подпрограмм, модулей. В настоящее время получили распространение специализированные пакеты, позволяющие решать многие задачи (Mathcad, Eureka, Reduce— Autocad и т.п.).

Индуктивный способ предполагает эвристический системный подход (декомпозиция - анализ - синтез). В этом случае общих и наиболее удачных методов не существует. Возможны некоторые подходы, позволяющие в каждом конкретном случае находить и строить алгоритмы. Методы разработки алгоритмов можно разбить на методы частных целей, подъема, отрабатывания назад, ветвей и границ и т.п.

Одним из системных методов разработки алгоритмов является структурное программирование. Принципы структурной алгоритмизации ранее излагались в гл. 1 (п. 1.8). Повторим их более формально с упором на реализацию в практически программировании.

Структурное программирование основано на использовании блок-схем, формируемых с помощью управляющих структурных элементов. Блок-схема - это ориентированная сеть, у которой могут быть вершины типа изображенных на рис. 3.5.

Выделяют три базовых структурных элемента (управляющие структуры): композицию, альтернативу, итерацию.

Рис. 3.5. Функциональные (а), предикатные (б) и объединяющие (в) вершины

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

 

begin S1;S2; end

Рис. 3.6. Структура «композиция»

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

Рис. 3. 7. Структура «альтернатива». Здесь В - условие (логическое выражение)

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

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

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

Рис. 3.8. Структура «итерация»

 

для обозначения связей с окружающей средой добавляют дополнительные структуры ввода-вывода и начала-конца программного блока, модуля, алгоритма:

Заметим, что для начального шага разработки программы чрезвычайно важным и необходимым является определение исходных (ввод) и выходных (вывод) данных задачи. С этого этапа начинается разработка практически любого алгоритма.

Метод разработки программы сверху-вниз предполагает процесс пошагового разбиения алгоритма (блок-схемы) на все более мелкие части до уровня элементарных конструкций, для которых можно составить конкретные команды. Идея структурного программирования сверху-вниз состоит в том, что, если для некоторой функции f существует ее композиция через две другие функции g и h, т.е. f=h(g(х)), то проблема разработки алгоритма для f сводится к проблемам разработки алгоритмов для h и g. В структурном программировании сверху-вниз на каждом шаге пытаются текущую функцию выразить как композицию двух (или более) других функций, которые представимы в виде рассмотренных выше управляющих структур.

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

Пример 1. Технология разработки программы решения квадратного уравнения.

На рис. 3.9 проиллюстрирована пошаговая детализация процесса построения алгоритма. Заметим, что для начального шага разработки программы имеем в качеств исходных данных коэффициенты а, b, с квадратного уравнения ax² + bx + с = 0, а на выходе - значения двух корней х 1, х2.

Пример 2. Рассмотрим более сложный и поучительный пример структурной программирования, известный в литературе как «тур шахматного коня». В задаче необходимо ответить на вопрос, существует ли при заданном положении шахматного коня последовательность его ходов, единожды содержащая все клетки шахматного поля.

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

Одной из эвристических стратегий алгоритма может быть следующая. Haчиная с произвольного поля i,j (на рис.3.10 i = 4,j = 4), пытаемся пойти на поле *1, если невозможно, то на поле *2; при неудаче - на поле *3 и т.д.по часовой стрелке

Рис. 3.9. Пошаговая детализация построения алгоритма

(варианты возможных ходов приведены на рисунке справа). Сделав очередной ход на пустую клетку, запишем в нее номер очередного хода и снова осуществляем процедуру поиска нового хода. В случае, когда из очередной клетки невозможно сделать ход, прерываем маршрут и выводим результат в виде таблицы, соответствующей шахматному полю, в которой раставлены ходы коня. Очевидно, что такая стратегия лишь при удаче может дать полный тур коня.

Итак, исходные данные задачи - произвольные начальные координаты коня i,j от 1 до 8. Результат - возможный маршрут коня из заданного поля. Удачным считается маршрут, содержащий все 64 хода, т.е. полный тур коня.

F Рис.3.10. Иллюстрация к задаче «тур шахматного коня»

 

Инициализация доски предполагает задание двумерного массива размером 8х8 с нулевыми элементами. В дальнейшем элемент a[iJ] принимает значения номера очередного хода. Распечатать результат - означает вывести таблицу а[1..8,1..8].Нарис.3.12 показан один из результатов возможного маршрута коня из начального поля i=l, j=l.

Рис. 3.11. Пошаговая детализация построения алгоритма к примеру 2

Рис. 3.12. Возможный результат маршрута коня из поля (1.1)

 

Программа 35

Program Tur_Konja;

var a: array[1..8,1..8] of integer;

im, jm:array(l..8] of integer;

i, j, k, n, inac, jnac: integer;

inext, jnext: integer;

begin (-----инициализация шахматной доски-—--}

for i:=l to 8 do for j:=l to 8 do a[i,j]:=0;

im[l]:=-2; jm[l]:=l.; im[2]:=-1; jm[2]:=2; im[3]:=1; jm[3]:=2;

im[4]:=2; jm[4):=l; im[5]:=2; jm[5]:=-!; im[6]:=1; jm(6]:=-2;

im[7]:=-l; jm[7]:=-2; im[8]:=-2; jm[8]:=-l;

write('введи начальные координаты коня 0<i,j<9: ');

readln(inac,jnac);

a[inac,jnac]:=1; i:=inac; j:=jnac; n:=2; k:=l;

while k<=8 do

begin inext:=i+im(k]; jnext:=j+jm (k];

if (inext<l) or (inext>8) or (jnext<l) or

(jnext>8) or (a[inext,jnext]<>0)

then k:=k+l

else begin a(inext,jnext]:=n; n^n+l; i:«-inext;

j:«jnext; k:=l;

end;

end;

{--------вывод результата прохода—————)

for i:=l to 8 do

begin writeln; writeln; for j:=l to 8 do write(a(i,j]:2,' ')

end;

writeln; write('кол-во шагов = ',n-l); readln;

end.

Зачастую используют альтернативный процедуре сверху-вниз метод структурного программирования сннзу-вверх. По сути мы приходим к конечному результату системным методом. Сначала разбиваем задачу на отдельные блоки (модули) с их связями между собой (декомпозиция), затем, после их разработки, проводим сборку блоков в единую программу (синтез). Принцип снизу-вверх широко распространен среди программистов, которые предпочитают модульный подход, предполагающий максимальное использование стандартных и специализированных библиотек процедур, функций, модулей и объектов.

 

Задания

1. Используя принцип проектирования сверху-вниз постройте блок-схему и программ) для решения системы линейных алгебраических уравнений методом Гаусса.

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