г- I

£2 I

По этой причине такие программы иногда называют программами со структурой дерева.

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

Второе предостережение связано с термином «программирование без

Рис. 2.1.20. Структурированная блок-схема глубины вложения три.

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

Упражнения 2.1

2.1.1. Находит ли программа KNIGHT (КОНЬ) тур коня из произвольного начального поля? Со всех начальных полей?

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

2.1.3. Можно ли с помощью эвристики из упр. 2.1.2. найти тур коня из произвольного начального поля?

2.1.4. Каково различие между понятием «правильности программы», о котором мы говорили в этом разделе, и понятием правильности алгоритмов в разд. 1.3?

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

*L2.1.6. Заново рассмотрите некоторые задачи из упражнений к гл. 1, включающие написание программ. Переделайте алгоритмы в соответствии с требованиями структурирования сверху-вниз. Сравните и сопоставьте старые и новые версии этих программ. На основании полученных результатов сформулируйте преимущества и недостатки метода структурирования сверху-вниз в программировании,

2.2. Сети!)

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

Рис. 2.2.1. (а) Остовные деревья и электрические сети; (б) представление органических соединений: метионин (без атомов Н).

социология, лингвистика и много разделов математики (включая численный анализ, теорию матриц, теорию групп, топологи.ю, дискретные вероятностные процессы, теорию игр и комбинаторику). Более того, сети, и в частности деревья, являются, по-видимому, наиболее часто используемыми математическими структурами в вычислительной математике. Сети и деревья используются при изучении структур данных, в компиляции, языках программирования, операционных системах, теории вычислений, сортировке, теории поиска и искусственном интеллекте. На рис. 2.2.1 и 2.2.2 приведены некоторые примеры использования сетей в качестве моделей. В этом разделе мы представим основы теории сетей, обсудим различные способы представления сетей в памяти вычислительной машины и сформулируем некоторые алгоритмы определения элементарных свойств сетей.

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

((C + D) *В + А)

INTEGER ЗОЮ PROCEDURE 1000 REAL 2110

WORDS

Рис. 2.2.2. Некоторые применения деревьев в вычислительной математике: (а) таблицы символов; (б) арифметические выражения; (в) подмножества множеств и вложенные структуры; (г) деревья сортировки (здесь представлено английское нредложепие: The words in this sentence have been alphabetically sorted as a rooted binary tree - слова в этом предложении были отсортированы по алфавиту как двоичное корневое дерево); (б) игровые деревья; конкретное дерево для игры НИМ,