1. Понятие о структурном программировании.Задачи и программы, которые мы рассматриваем в этой книге, имеют учебный характер и не являются сложными и большими. На практике задачи, соответствующие алгоритмы и программы обычно являются сложными или громоздкими. В таких случаях следует помнить об основных принципах структурного программирования.
Структурное программирование - это концепция программирования, которая предусматривает:
1. Предварительный анализ сложной задачи или громоздкого алгоритма с целью разбивки ее (его) на отдельные простые части.
2. Последовательную детализацию всех частей и составления соответствующих подпрограмм.
3. Использование трех базовых конструкций языка (простой, ветвления, цикла) при составлении каждой подпрограммы.
4. Написание программ, понятных для людей, которые будут с ними работать.
5. Минимальное использование команд перехода.
6. Систему средств проверки правильности программы: логический анализ программы до ее выполнения, перекрестная проверка программ, коллективная работа над созданием сложных программ и т.п.
Объясним некоторые из этих принципов.
Детализация сверху донизу. При решении сложной задачи алгоритм разбивают на части, выделяют основные подзадачи, которые в свою очередь разбивают на части низшего уровня. Каждую часть разрабатывают отдельно: сначала уточняют (программируют) части верхнего уровня, а позже - низшего. Это называется анализом сверху донизу и пошаговой детализацией алгоритма. В конце отдельные части стыкуют между собой.
Метод пошаговой детализации имеет важное значение не только в информатике. Один человек может руководить разработкой большого алгоритма (созданием бюджета государства, строительством космической станции и т.п.), поручая многим исполнителям детализацию вспомогательных алгоритмов (выполнение отдельных работ).
Принципом пошаговой детализации следует руководствоваться во время решения задач по информатике, в курсе математики и физики, по другим предметам, а также в быту. Об этом принципе не следует забывать и в будущем.
Принцип пошаговой детализации, известный с давних пор, применяли с успехом в военном деле. Провозглашенный древними римлянинами лозунг «Divide and conquer» («Разделяй и властвуй») хорошо усвоили Александр Македонский и Наполеон Бонапарт. Последний сумел в 1805 г. под Аустерлицем разделить превосходящую австрийскую армию на отдельные подразделения и разгромить их поочередно. Наполеон был завоевателем и вошел в историю как гениальный полководец. Сегодня, чтобы подчинить мир, не надо воевать. Это с успехом доказали большие компьютерные фирмы, такие как Microsoft Corporation, IBM Corporation и другие, где над отдельными проектами работают сотни, а то и тысячи специалистов, слаженную деятельность которых обеспечивают руководители проектов (супервизоры), хорошо усвоившие этот принцип.
Базовые конструкции. Целесообразно выяснить, какие конструкции и элементы языка можно использовать во время программирования каждой части. Напомним, что в распоряжении пользователя есть три базовые (основные) алгоритмические конструкции: 1) простая; 2) ветвление; 3) цикл. В 1964 году была доказана теорема о том, что алгоритм произвольной сложности можно построить на базе этих трех конструкций.
Необходимо избегать команд перехода. Бессистемное использование команд перехода (в особенности к предыдущей части программы), которые усложняют чтение программы, нужно сводить к минимуму. Этого можно достичь с помощью таких конструкций языка, как условная команда if-then-else,команда многозначного выбора case,команды цикла whileи подпрограмм с параметрами.
Есть возможность досрочно выйти с некоторой конструкции с помощью таких команд выхода: exit, break, continue и halt.
Необходимо проверять правильность программы до её выполнения на компьютере. Для этого используют, в частности, прием трассировки программы - построения таблицы значений всех переменных.
Подпрограммы предназначены для реализации алгоритмов решения отдельных подзадач. Они дают возможность реализовывать концепцию структурного программирования.
Различают два вида подпрограмм - подпрограммы-процедуры и подпрограммы-функции. Подпрограммы делятся на стандартные и подпрограммы пользователя. Стандартные подпрограммы пользователь не создает, они находятся в стандартных модулях System, Crt, Dos, Graph и т.д. Подпрограмма пользователя — это поименованная группа команд, которую создают и описывают в основной программе в разделах procedureили function.Подпрограмму можно вызвать из любого места программы необходимое количество раз.
2. Процедуры (procedure).Общий вид процедуры:
procedure<имя> (<список формальных параметров>);
<разделы описаний и объявлений процедуры>;
Begin
<раздел команд процедуры>
end;
В списке формальных параметров перечисляют переменные и указывают их типы. Различают параметры-значения (другой термин: параметры-аргументы) - входные данные для процедуры, и параметры-переменные (другой термин: параметры-результаты), через которые можно возвращать результаты работы процедуры в основную программу. Перед списками параметров-переменных каждого типа записывают слово var.Заметим, что массивы фиксированных размеров в этих списках описывать при помощи слова arrayнельзя (см. ниже образцы программ).
Разделы описаний и объявлений в подпрограммах имеют такую же структуру, как и в основной программе.
Пример. Рассмотрим процедуру Сеnа, которая определяет стоимость телефонного разговора с поминутной оплатой 0.6 руб. + 20% НДС.
procedureCena(k : integer; var с : real);
Begin
с := k * 0.6;
с := с + 0.2 * с;
end;
В приведенном примере k — формальный параметр-значение (это количество минут разговора), с - формальный параметр-переменная (сумма, которую необходимо уплатить за k минут разговора).
Процедуру можно вызвать из раздела команд основной программы или другой подпрограммы с помощью команды вызова:
Параметры, которые задают в команде вызова процедуры, называются фактическими. Фактическими параметрами-значениями могут быть константы, переменные, выражения, а параметрами-переменными - только переменные. Типы данных в команде вызова не указывают.
Между фактическими и формальными параметрами должно быть соответствие по количеству и типам. Имена соответствующих пар фактических и формальных параметров могут не совпадать.
Команда вызова работает так: значения фактических параметров присваиваются соответствующим формальным параметрам процедуры, выполняется процедура, определяются параметры-переменные, значения которых присваиваются (возвращаются) соответствующим фактическим параметрам команды вызова.
Переменные, описанные в разделе varосновной программы, называются глобальными. Они действуют во всех подпрограммах данной программы. Переменные, описанные в разделе описания конкретной процедуры, называются локальными. Они действуют только в данной процедуре.
Процедуры могут получать и возвращать значения не только с помощью параметров—переменных, но и через глобальные переменные. Поэтому списков параметров в процедуре может и не быть.
Задача 1. Решить задачу из предыдущего параграфа о количестве вызовов на АТС, используя три процедуры: 1) для определения количества вызовов за каждую секунду (назовём процедуру Kolvyzov); 2) для вычисления количества вызовов за первые 10 секунд (Summavyzov); 3) для определения наибольшего количества вызовов за некоторую секунду (MaxKolvyzov). Использовать функцию random.
programATS1;
usesCrt;
typevyzov = array[1..10] ofinteger;
var у : vyzov;
max, s : integer;
procedureKolvyzov(var у : vyzov); {Процедура Kolvyzov}
var i : integer; {определяет количество вызовов}
begin{за каждую секунду}
fori := 1to10do
Begin
y[i] := random(i);
writeln('y(' , i ,') = ', y[i]:5);
end;
end;
procedureSummavyzov(y : vyzov; var s : integer);
{Процедура вычисляет количество вызовов}
var i : integer; {за первые 10 секунд}
Begin
s := 0;
for i := 1 to 10 do s := s + y[i];
writeln('Сумма вызовов S = ', s:3);
end;
procedureMaxKolvyzov(y : vyzov; var max : integer);
var i : integer; {Процедура MaxKolvyzov определяет}
begin{наибольшее количество вызовов}
max := y[l]; {за некоторую секунду}
for i := 2 to 10 do
ifmax < y[i] thenmax := y[i];
write('Максимальное количество вызовов за одну ');
<раздел команд функции, где должна быть такая команда:
имя:=выражение>
end;
В разделе команд функции должна быть команда присваивания имени функции значения некоторого выражения. Результат функции возвращается в основную программу через её имя (как и в случае использования стандартных функций, таких как sin, cos). Вызов функции осуществляется только из выражений с помощью указателя функции:
<имя>(<список фактических параметров>).
Пример. Опишем функцию для вычисления tg(x) и вычислим значение выражения tg(x)+ctg(x)+tg2(x).
programMyfunc;
uses Crt;
var x, у : real;
functiontg(x : real) : real;
Begin
tg := sin(x) / cos(x)
end;
Begin
clrscr;
writeln('Введите х');
readln(x);
у := tg(x) + 1 / tg(x) + sqr(tg(x));
writeln('y =', y:5:2);
readln
End.
Задача 2. Решить задачу о производстве конфет на фабрике из предыдущего параграфа, используя функции и процедуры пользователя.
programFabrika1;
usesCrt;
constn = 5;
typezatraty = array[l..n, l..n] ofreal;
var imin : integer;
a : zatraty;
functionfunc(i, j : integer) : real;
Begin
func := 2 * abs(sin(i)) + j;
end;
procedureTable(var a : zatraty); var i, j : integer;
Begin
writeln(' Вид сырья');
writeln(' 1 2 3 4 5');
for i := 1 to n do{Создаём таблицу затрат}
begin
write(i, ' сорт');
forj := 1tondo
Begin
{Используем созданную функцию}
a[i, j] := func(i, j);
{Выводим элементы i-ой строки}
write( a[i, j]:7:2);
end;
writeln {Переходим на новую строку}
end;
end;
procedureMinSyr(a : zatraty; var imin : integer);
var i, j : integer;
min : real;
Begin
imin := 1;
min :=a[l, 3];
for i := 2tondo
ifa[i, 3] <min then
Begin
min := a[i, 3];
imin := i
end;
writeln('Меньше всего сырья третьего вида ');
write('необходимо для производства конфет ');
writeln( imin, ' сорта')
end;
Begin
clrscr;
Table(a); {Вызываем процедуру Table}
MinSyr(a, imin); {Вызываем процедуру MinSyr}
readln
End.
Задание 2. Решите задачу № 15 своего варианта с использованием процедур.
4. Рекурсивные функции. Рекурсией называется алгоритмическая конструкция, где подпрограмма вызывает сама себя. Рекурсия дает возможность записывать циклические алгоритмы, не используя команды цикла. Рассмотрим сначала понятия стека.
Стек — это модель оперативной памяти (структура данных), где данные запоминаются и хранятся по принципу «первый пришел — последний ушел». Аналогом в военном деле является рожок для патронов к автомату.
Пример. Рекурсивная функция вычисления суммы целых чисел от а до b имеет вид
functionSumma(a, b : integer) : integer;
Begin
ifa = bthenSumma := a {Это стоп-условие рекурсии}
elseSumma :== b + Summa(a, b-1) (Это неявный цикл]
end;
Вычислим функцию Summa(3, 5). Формально можно записать
Система выполняет такие вычисления за два этапа: на первом этапе формирует стек, куда заносит числа 5, 4, 3. На втором этапе числа прибавляет в обратной последовательности (поскольку они поступают из стека): 3 + 4 + 5 = 12.
Задача 3.Составить рекурсивную функцию Factorial для вычисления факториала числа n (n! = 1•2•3•...•n, 0! = 1,1! = 1), которая основывается на многоразовом (рекурсивном) использовании формулы n! = п•(п - 1)!.
В стек будут занесены числа 4, 3, 2, 1, 1. Следовательно получим результат: 1•1•2•3•4 = 24.
Замечание. Применяя рекурсию, нужно правильно составлять стоп-условия, которые обеспечивают окончание рекурсивных вычислений.
Задание 3.Составить программу решения задачи № 6, используя рекурсивные функции.
5. Открытые массивы. В списках формальных параметров подпрограммы можно описывать открытые массивы — массивы заранее неизвестного размера. Их описание имеет вид:
<имя массива> : array of <имя базового типа>;
Нумерация элементов такого формального массива в подпрограмме всегда начинается с нуля. Номер последнего элемента можно определить с помощью стандартной функции
high(<имя массива>).
Открытый массив используют для поочередной обработки в процедуре массивов различных размеров.
Задача 4.Используя подпрограммы, создать массив у, элементы которого заданы формулой уm = fy(m) = random(m), m = 1, 2, ..., 7, и массив g с элементами gn=fg(n)=n2/2, n = 1, 2, ..., 9. В каждом массиве определить количество элементов, больших 4. Вывести на экран результаты вычислений.
program MyProcedure;
{$F+}
uses Crt;
typemyfunc = function(n: integer) : real;
varу : array[1..7] ofreal;
g : array [1..9] ofreal;
functionfy(m : integer) : real;
Begin
у := random(m)
end;
functionfg(n : integer) : real;
Begin
g := n * n / 2
end;
procedureSozdat(f : myfunc; varz : array ofreal);
var i : integer;
Begin
fori := 0tohigh(z)do
Begin
z[i] := f(i + 1);
write(z[i]:5:2);
end;
writeln
end;
functionkol(z : array ofreal) : integer;
var i, k : integer;
Begin
k :=0;
fori := 0tohigh(z)do
ifz[i] > 4 thenk := k + 1;
kol := k
end;
Begin
clrscr;
randomize;
Sozdat(fy, y);
Sozdat(fg, g);
write('Количество искомых элементов у - ');
writeln('k = ', kol(y):3);
write(' Количество искомых элементов g - ');
writeln('k = ', kol(g):3);
readln
End.
Замечание. Обратите внимание на использование впервые типа данных функция (function):
typemyfunc = fimction(n: integer) : real.
К этому типу отнесены конкретные функции fy(x) и fg(x). Благодаря типу myfunc можно, используя всего одну процедуру, создавать различные массивы. В связи с этим в программу включена директива {$F+}, которая поддерживает необходимую модель (far-модель) вызова подпрограмм.
Задание 4. Решите задачу № 16 своего варианта.
4. Стандартные модули.Подпрограммы, которые имеют универсальное назначение и могут пригодиться многим пользователям, следует объединять в библиотеки и модули.
Модуль — программная единица. Он содержит описание констант, типов данных, переменных и подпрограмм. Различают стандартные модули и модули, созданные пользователем.
Существуют такие стандартные модули:
System — содержит часто используемые процедуры и функции;
String— содержит функции для работы со строковыми переменными;
Printer— модуль для работы с устройством печати;
Graph— содержит процедуры и функции для графических построений;
Overlay— модуль для работы с большими программами;
Dos, Windows— дают возможность выполнять команды операционной системы во время выполнения паскаль—программ или получать определённые данные от операционной системы;
Graph3, ТurЬо3- обеспечивают совместимость с предыдущими версиями ТР и т.д.
Подсоединение модулей в конкретной программе осуществляется с помощью команды
uses<список имён модулей>;
Процедуры и функции из модуля System используются по умолчанию. Именно из этого модуля компилятор берёт процедуры read, readln, write, writeln, стандартные функции sin, cos и т.д.
Рассмотрим несколько полезных процедур, которые принадлежат модулям System и Crt:
exit— служит для выхода из текущей подпрограммы или остановки работы основной программы;
halt— останавливает выполнение программы и передаёт управление операционной системе;
break— служит для принудительного выхода с циклов for, whileили repeat;
continue— предназначена для перехода к выполнению следующей итерации в циклах for, while,или repeat;
delay(n)— приостанавливает выполнение следующей команды на заданное пользователем время (в микросекундах);
clrscr— очищает экран;
textcolor(цвет)— задаёт цвет текста (число от 0 до 15);
textbackground(цвет)— задаёт цвет фона экрана.
Среди функций модуля Crt часто используют символьную функцию readkey,которая приобретает значение нажатого пользователем символа на основной символьно-цифровой части клавиатуры, а также логическую функцию keypressed,которая получает значение true,если пользователь нажмёт любую клавишу на основной клавиатуре.
В модуле Dos определены процедуры и функции для работы с файловой системой в режиме выполнения паскаль-программы. Для выполнения ехе-файла некоторой программы изнутри текущей программы используют процедуру
ехес('<полное имя ехе-файла>','<параметры программы>' или '').
Замечание. В начале программы, где используется процедура ехес,необходимо включить директиву М, например, с такими параметрами
{$М $2000,0,1000}.
Для хронометрирования времени выполнения программы или её фрагментов, а также для обработки даты используют такие две процедуры:
GetTime(Hour, Minute, Second, SotiSec) - присваивает указанным в списке переменным числовые значения текущего времени (час, мин, сек, сотые сек);
GetDate(Year,Month, Day, Number) — присваивает переменным из списка типа word значение текущей даты (год, месяц, день, день недели).
Задание 5. Рассмотрите задание № 3 о вычислении тремя способами знакопеременной суммы с точностью е = 0,00001 (см. § 5, п. 2, задачу-образец № 4, задачу № 7 из раздела "Задачи"). Создайте ехе-файлы для соответствующих трех программ. Напишите программу, которая будет состоять из директивы {$М...}, команды usesCrt, Dos; трех команд типа exec('summal.exe', ''); нескольких команд gettime(...), размещенных так, чтобы измерять время выполнения процессором каждой из подсоединенных подпрограмм. Определите время в микросекундах, затраченное процессором для решения задачи каждым способом. Каким способом результаты были получены быстрее?
5. Модули пользователя (unit).Собственный модуль пользователь составляет по определенным правилам. Структура модуля такая:
unit<имя>;
interface{интерфейсный блок}
<раздел описаний>
implementation{блок реализации заданий}
<тексты подпрограмм пользователя>
Begin
<блок инициализации>
End.
Пользователь дает модулю имя. Оно должно быть уникальным. В разделе описаний можно объявлять другие модули, описывать типы, константы и заголовки подпрограмм, доступные в данном модуле.
В блоке реализации записывают тексты подпрограмм в порядке упоминания их заголовков в описаниях. Списки параметров можно не писать, поскольку они приведены в описаниях заголовков. Блоки интерфейса и реализации могут быть пустыми. Такую возможность используют при необходимости описать, например, общие для многих программ постоянные, переменные, типы данных.
В блоке инициализации можно задавать исходные данные, открывать файлы и т.д. Этот блок выполняется первым, то есть перед командами основного блока главной программы, к которой присоединен данный модуль. Если этот блок не используется, то служебное слово beginне пишут.
Пример. Создадим модуль, который определяет функции tg(x), хyи чистит экран.
