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

[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]

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

Первый пример (рис. 2.1.5) соответствует ситуации, обрабатываемой на Фортране оператором COMPUTED GO ТО. Лингвистически


Рис. 2.1.5. Блок-схема для оператора case.

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

case i of SI; S2; . . .; Sm fo

что эквивалентно

if t=l then SI else if t=2 then S2 else

if i=m then Sm fi ... fi fi )

Вторая запись по сравнению с первой выглядит менее естественно.

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

while В do S1; if С then S2

else goto OUT fi od

Хотя более строгие формы структурного программирования исключают применение оператора goto, блок-схемы, в которых оператор

) Строго говоря, если i не равно ни одному значению 1, 2, , , . , т, то данный оператор пропускается. Это не отражено на рис, 2.1.5,



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

Еще один пример простой неструктурированной блок-схемы, часто встречающийся в программировании, приведен на рис. 2.1.7, а. На рис. 2.1.7, б указан один из способов структурирования этой блок-схемы, хотя получаемый результат и нельзя считать вполне естественным. Заметим, что лингвистический оператор для неструктурированной блок-схемы на рис. 2.1.7, а требует применения оператора goto. Например,

k: Sl;il В then S2; goto k fi



с \f ггреждевре-

МЕНКЫЙ

Выход

тогда как лингвистический оператор для структурированной блок-схемы на рис. 2.1.7,6 его не содержит. Например,

do SI; while В do S2; SI od od

Вообще говоря, структурное программирование определяет процесс разработки алгоритмов в терминах «квазиструктурированных» блок-схем, в которых элементарные структуры управления являются, как правило, структурами Бома и Якопини. Впрочем, допускаются и другие структуры «простого типа» при условии, что они обладают свойством «один вход и один выход».

Рис. 2.1.6. Блок-схема для Программирование сверху-вниз и пра- преждевременного окончания Бильность программ цикла.

Как отмечалось в разд. 1.3, программирование сверху-вниз - это процесс пошагового разбиения алгоритма на всё более мелкие части с целью получит!? такие элементы, для которых можно легко написать конкретные команды. На рис. 2.1.8 этот процесс иллюстрируется для случая блок-схемы на рис. 2.1.4, б.

Структурное программирование сверху-вниз - это процесс программирования сверху вниз, ограниченный использованием структурных блок-схем. Идея весьма проста. Предположим, что требуется разработать алгоритм для некоторой конкретной функции /. Пусть далее можно доказать, что / есть композиция двух других (надо полагать, более простых) функций g я h, т. е. f{x)==h(£{x)), как показано на рис. 2.1.9. Тогда проблема разработки алгоритма для f сводится к проблемам разработки алгоритмов для g м h.

Пусть далее можно доказать, что функция g равна некоторой функ-



ции i, когда заданный параметр х неотрицателен, или равна некоторой другой функции /, когда х отрицателен. Тогда алгоритм для вычисления g можно выразить в форме конструкции if-then-else (рис. 2.1.10).



Рис. 2.1.7. (с) Неструктурированная блок-схема; (б) эквивалентная структурированная блок-схема.

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

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

В структурном программировании сверху-вниз на каждом шаге процесса разработки спрашивается, нельзя ли текущую функцию (подфункцию) выразить как композицию двух (или более) других функций, т. е. функций типа do SI; S2 od, if-then-else, do-while или while-do. Конкретный пример поможет нам выразить эти идеи яснее.

Тур коня

В шахматах конь может пойти из заданного поля (положения) на одно из самое большее восьми других полей, как показано на рис. 2.1.11. Так как конь не может сойти с доски, то из произвольного поля он не всегда может пойти на все восемь полей. Например, из поля



[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.0016