Главная Промышленная автоматика.

повторяющиеся строки в своем входном файле f, создавая выходной файл Д, содержащий слова из исходного файла (без прописных букв и повторений), упорядоченные в алфавитном порядке. Наконец, к файлу Д применяется команда diff, имеющая параметр, который указывает на файл /5, содержащий в алфавитном порядке слова из словаря, расположенные по одному в строке. Результатом этой команды будет список слов из файла f, которые не совпадают со словами из файла f, т.е. те слова из исходного списка, которых нет в словаре. Программа spell состоит из следующей последовательности команд:

speH: translate [A-Z] -> [a-z], пробел -> новая строка sort unique diff словарь

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

1.7. Расширение языка Pascal

Большинство программ в этой книге написаны на языке Pascal. Чтобы сделать листинги программ более читабельными, мы иногда будем применять три конструкции, которые вы не найдете в стандартном Pascal, но которые легко трансформируются в операторы языка Pascal. Одна из таких конструкций - нечисловые метки. Если в программе необходимо использовать несколько меток, то нечисловые метки значительно облегчат понимание программы. Например, оператор goto выход, очевидно, более понятен, чем goto 561. Для преобразования программы с нечисловыми метками в "чистую" программу Pascal, надо заменить все нечисловые метки различными числами и затем объявить их метками (label) в начале программы. Этот процесс можно полностью автоматизировать.

Другой нестандартной конструкцией является оператор возврата return, который позволяет писать более понятные программы без использования операторов goto. Оператор возврата будем использовать в следующей форме: теЬитп(выражение), где скобка (выражение) необязательна. Преобразовать процедуру с операторами возврата в стандартную программу Pascal очень просто. Сначала надо объявить новую метку, скажем 999, и затем поместить ее на последний оператор end процедуры. Например, оператор return(x) в некой функции zap заменяется следующим блоком:

begin

zap:= X;

goto 999

Оператор return, не имеющий аргументов, просто заменяется на оператор goto 999.

Пример 1.12. В листинге 1.6 представлена программа, вычисляющая факториал, в которой использованы операторы возврата. В листинге 1.7 показана та же программа после замены операторов return стандартными операторами Pascal. □

Листинг 1.6. Программа вычисления факториала с операторами возврата

function fact ( п: integer ) : integer; begin

if и <= 1 tlien



return(1)

else

rвtum(л * factin - 1) ) end; { fact }

Листинг \.y. Лрограмма вычисления ()акто}11ала на языке Pascal

function fact ( п: integer ) •- integer; label

999;

begin

if л < 1 then begin

fact:= 1;

goto 999

else

begin

fact:= n * factin - 1) ; goto 9 99

999;

end; { fact }

Третье расширение языка Pascal, которое мы будем применять, заключается в постоянном использовании выражений, описываюших типы, в качестве имен типов. Например, выражения, подобные Т celltype, мы считаем допустимыми в качестве имен типов, но недопустимыми для типов параметров процедур или значений, возврашаемых функциями. Технически Pascal требует, чтобы мы использовали имена для типов данных, например prtocell (указатель на ячейку). В этой книге мы будем допускать такие описы-ваюшие выражения в качестве имен типов, надеясь, что читатель сможет придумать имя для типа данных и механически заменить описываюшее тип выражение именем типа. Другими словами, мы будем использовать операторы, подобные

function zap( А: array[1.. 10] of integer ): t celltype

подразумевая под этим следующий оператор (здесь arrayofmteger обозначает "массив целых чисел"):

function zap ( А: arrayof integer ): prtocell ,

Наконец, замечание о применяемых нами соглашениях в отношении листингов программ. Зарезервированные слова Pascal выделяются полужирным начертанием, типы данных пишутся обычным начертанием, а имена процедур, функций и переменных - курсивом. Мы различаем строчные и прописные буквы.

Упражнения

1.1. В состязаниях футбольной лиги участвуют шесть команд: Соколы, Львы, Орлы, Бобры, Тигры и Скунсы. Соколы уже сыграли с Львами и Орлами. Львы также сыграли с Бобрами и Скунсами. Тигры сыграли с Орлами и Скунсами. Каждая команда играет одну игру в неделю. Найдите расписание матчей, чтобы все команды сыграли по одному разу друг с другом в течение минимального количества недель. Совет. Создайте граф, где вершины будут соответство-

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



вать парам команд, которые еще не играли между собой. Что должны обозначать ребра в таком графе, если при правильной раскраске графа каждый цвет соответствует матчам, сыгранным в течение определенной недели?

*1.2. Рассмотрим руку робота с закрепленным одним концом. Рука состоит из двух "колен", каждое из которых может поворачивать руку на 90 градусов вверх и вниз в вертикальной плоскости. Какую математическую модель следует применить для описания перемещения оконечности руки? Разработайте алгоритм для перемещения оконечности руки из одного возможного положения в другое.

*1.3. Предположим, что необходимо перемножить четыре матрицы действительных чисел Ml X Мах Мзх М, где Mj имеет размер 10 х 20, размер Мг составляет 20 X 50, Мз - 50 X 1 и М4 - 1 х 100. Предположим, что для перемножение двух матриц размером р х q и q х г требуется pqr скалярных операций, это условие выполняется в обычных алгоритмах перемножения матриц. Найдите оптимальный порядок перемножения матриц, который минимизирует общее число скалярных операций. Как найти этот оптимальный порядок в случае произвольного числа матриц?

**1.4. Предположим, что мы хотим разделить множество значений квадратных корней целых чисел от 1 до 100 на два подмножества так, чтобы суммы чисел обоих подмножества были по возможности максимально близки. Если мы имеем всего две минуты мащинного времени для рещения этой задачи, то какие вычисления необходимо выполнить?

1.5. Опищите "жадный" алгоритм для игры в щахматы. Каковы, по ващему мнению, его достоинства и недостатки?

1.6. В разделе 1.2 мы рассмотрели абстрактный тип данных SET (Множество) с операторами MAKENULL, UNION и SIZE. Для определенности положим, что все множества являются подмножествами множества {О, 1, 31}, а АТД SET интерпретируется как тип данных языка Pascal set of С.31. Напишите процедуры на языке Pascal для выполнения этих операторов, используя данную реализацию АТД SET.

1.7. Наибольшим общим делителем двух целых чисел р и q называется наиболь-щее целое число d, которое делит р и q нацело. Мы хотим создать программу для вычисления наибольщего общего делителя двух целых чисел р и q, используя следующий алгоритм. Обозначим через г остаток от деления р на q. Если г равно О, то q является наибольщим общим делителем. В противном случае положим р равным q, затем - q равным г и повторим процесс нахождения остатка от деления р на q.

а) покажите, что этот алгоритм правильно находит наибольщий общий делитель;

б) запищите алгоритм в виде программы на псевдоязыке;

в) преобразуйте программу на псевдоязыке в программу на языке Pascal.

1.8. Мы хотим создать программу форматирования текста, которая выравнивала бы текст по щирине строк. Программа долясна иметь буфер слов и буфер строки. Первоначально оба буфера пусты. Очередное слово считывается в буфер слов. Если в буфере строки достаточно места, то слово переносится в буфер строки. В противном случае добавляются пробелы между словами до полного заполнения буфера строки, затем после печати строки этот буфер освоболсдается.

а) запищите алгоритм в виде программы на псевдоязыке;

б) преобразуйте программу на псевдоязыке в программу на языке Pascal.

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





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 118 119 120 121 122 123

0.0018