Файл: Могилев А.В. Информатика.pdf

266 

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

Индуктивный способ предполагает эвристический системный подход (декомпозиция - ана-

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

Одним  из  системных  методов  разработки  алгоритмов  является  структурное  программиро-

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

Структурное  программирование  основано  на  использовании  блок-схем,  формируемых  с  помощью 

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

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

итерацию. 

Рис. 3.5.

 Функциональные (а), предикатные 

(б)

 и объединяющие (в) вершины 

 
Композиция -

  это  линейная  конструкция  алгоритма,  составленная  из  последовательно  сле-

дующих друг за другом функциональных вершин, рис.3.6. 

begin S1;S2; end 

Рис. 3.6.

 Структура «композиция» 

 
Альтернатива -

 это конструкция ветвления, имеющая предикатную вершину. Конструкция 

ветвления  в  алгоритмах  может  быть  представлена  в  виде  развилки  (а),  неполной  развилки  (б)  и 
выбора 

(в)

 (рис.

 3.7).

Рис. 3.

7.

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

267 

Итерация -

 это циклическая конструкция алгоритма, которая, вообще говоря, является со-

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

(а)

 и с постусловием (о) (рис.3.8). 

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

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

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

Для представления алгоритма в полном и законченном виде, а также 

Рис. 3.8.

 Структура «итерация» 

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

да-вывода и начала-конца программного блока, модуля, алгоритма: 

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

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

Метод разработки программы сверху-вниз предполагает процесс пошагового разбиения ал-

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

Для иллюстрации технологии структурного программирования сверху-вниз рассмотрим два 

примера - сначала простой, затем существенно более сложный.  

Пример 1.

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

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

Заметим, что для начального шага разработки программы имеем в качеств исходных данных ко-
эффициенты 

а, b, с

 квадратного уравнения 

ax

2

 + bx + с =

 0, а на выходе - значения двух корней х 

1, х2.  

Пример 2.

 Рассмотрим более сложный и поучительный пример структурной программиро-

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

Попытка  быстро  ответить  на  этот  вопрос  приводит  к  перебору  всех  возможн  маршрутов 

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

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

вольного поля i,j (на рис.3.10 i = 4,j 

=

 4), пытаемся пойти на поле *1, если невозможно, то на поле 

268 

*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. 

269 

Рис. 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; 

270 

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. Разработайте алгоритм и программу поиска тура коня по другой стратегии, например, по 

случайному выбору очередного хода из числа возможных. 

4.3. МЕТОДЫ ПОСТРОЕНИЯ АЛГОРИТМОВ,  

ОРИЕНТИРОВАННЫЕ НА СТРУКТУРЫ ДАННЫХ 

Часто  на  технологию  разработки  алгоритма  влияют  структуры  данных,  используемых  в 

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

Сортировка массивов данных, т.е. расположение их элементов в определенном порядке, яв-

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

Попробуем  проблему  решить  с  помощью  линейного  связанного  списка.  Массив  преобра-

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

Info 
 

Link