Составление программ с использованием подпрограмм - функций
Цель работы. Получение навыков в написании программ с использованием функций.
Задание. Организация программ с использованием функций.
Постановка задачи. По своему варианту написать программу, которая вычисляет заданную функцию. Изучить механизм передачи параметров по значению.
Варианты заданий
В каждом из вариантов заданий необходимо определить:
1. Число перемен знака в массиве X1, X2, ..., Xn.
2. Количество элементов среди Х1, Х2,..., Хn , значения которых совпадают со значениями элементов массива Y1 , Y2 ,..., Yn.
3. Сумма отрицательных элементов массива Y1 , Y2 ,..., Yn.
4. Произведение положительных элементов среди элементов X1, X2, ..., Xn.
5. Полу сумма минимального и максимального элементов массива X1, X2,.., Xn.
6. Значение многочлена Y1 Zn-1 + У2 Zn-2+...+ Yn-1Z+ Yn (Z —исходное значение для внешней функции).
7. Количество нулей в массиве X1, X2, ..., Xn.
8. Наибольшая абсолютная величина элемента среди Y1 , Y2 ,..., Yn.
9. Число элементов массива Y1 , Y2 ,..., Yn, значения которых совпадают со значениями элементов X1, X2, ..., Xn.
10. Скалярное произведение, равное .
11. Произведение максимальных элементов исходных массивов.
12. Число элементов массива X1, X2, ..., Xn, которые больше максимального элемента в массиве Y1 , Y2 ,..., Yn.
13. Число элементов среди X1, X2, ..., Xn, которые не превосходят максимального элемента Y1 , Y2 ,..., Yn и в то же время не меньше его минимального элемента.
14. Число элементов массива X1, X2, ..., Xn , которые делятся на 7 без остатка (обоснованно выбрать тип элементов массива X).
15. Расстояние от начала координат до точки n-мерного пространства с координатами X1, X2, ..., Xn, (оно равно корню квадратному из ).
16. Значение наибольшего элемента главной диагонали матрицы А.
17. Количество положительных элементов в двух заданных строках матрицы А.
18. Абсолютная величина разности максимальных элементов двух заданных столбцов матрицы А.
19. Общее количество нулей в i-ой и последней строке, i-м и последнем столбце матрицы А.
20. Количество локальных минимумов матрицы А.
21. Среднее арифметическое элементов над главной диагональю матрицы А.
22. Количество строк матрицы А, сумма элементов каждой из которых меньше нуля.
23. Максимальный элемент в заданной группе соседних строк матрицы А.
24. Наибольшее число подряд идущих положительных элементов среди X1, X2, ..., Xn.
25. Наименьший элемент в совокупности элементов двух массивов X1, X2, ...,Xn , Y1 , Y2 ,..., Yn.
26. Разность сумм элементов над и под главной диагональю матрицы А.
27. Общее количество отрицательных элементов на главной диагонали и на двух соседних с ней (сверху и снизу) диагоналях матрицы А.
28. Наименьшая сумма строки в матрице А.
29. Наибольший из минимальных элементов строк матрицы А.
30. Общее количество локальных максимумов в строках матрицы А.
Рекурсия
Рекурсивным называется объект, который частично определяется через самого себя. Рассмотрим функцию n!
n!:= 1 * 2 * 3 *..* n;
Такое произведение можно вычислить с помощью интерактивных циклических конструкций.
f:=l;
for i:=l to n do f := f * i;
Однако существует другое определение факториала, в котором используется рекуррентная формула. Тогда, факториал определяется следующим образом:
1. 0! = 1;
2. для любого n > 0 n! = n* (n-1)!;
Организация вычисления по рекуррентным формулам можно и без использования рекурсий. Однако при этом встаёт вопрос о качестве программы и доказательстве её эквивалентности формы.
Использование рекурсии позволяет почти дословно запрограммировать вычисление по рекуррентным формулам.
Так, прямая формула чисел Фибоначчи:
1. F(1)=l;
2. F(2)=l;
3. для любого n > 0 F(n) = F(n-l) + F(n-2);
Вычисление факториала
Для написания рекурсивных алгоритмов необходимо и достаточно наличие понятия процедуры и функции.
Рекурсия- это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих её операторов обращается сама к себе.
Рассмотрим классический пример — вычисление факториала. Программа вводит с клавиатуры целое число N и выводит на экран значение n!, которое вычисляется с помощью рекурсивной функции Fасt. Для выхода из программы необходимо либо ввести достаточно большое целое число, чтобы вызвать переполнение при умножении чисел с плавающей запятой, либо нажать Ctrl-Z и Enter.
При выполнении правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В ниже приведённом примере решение при n=0 тривиально и используется для остановки рекурсии.
Пример 8.3.
Листинг программы
Program Factorial;
{$S+} {Включаем контроль переполнения стека}
var n : integer;
function Fасt (n : integer) :real;
{Рекурсивная функция, вычисляющая n!}
begin
if n < 0 then writeln ('Ошибка в задании N')
else
if n = 0 then Fact := 1
else Fact := n * Fact (n-1);
end;
begin
repeat
readln (n);
writeln ('n! = ', Fact (n));
until EOF;
end.
Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и даёт более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека (при каждом входе в программу её локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком). Переполнение стека особенно ощутимо сказывается при работе с сопроцессором: если программа использует арифметический сопроцессор, результат любой вещественной функции возвращается через аппаратный стек сопроцессора, рассчитанный всего на 8 уровней. Если, например, попытаться заменить тип real функции Fасt на Extended, программа перестанет работать уже при n = 8. Чтобы избежать переполнения стека сопроцессора, следует размещать промежуточные результаты во вспомогательной переменной. Правильный пример для работы с типом Extended:
Пример 8.4.
Листинг программы
Program Factorial; {$S+, $N+, $E+}
{Включаем контроль переполнения стека и работу сопроцессора}
var n : integer;
function Fact (n : integer) :real;
var F : extended;
{Рекурсивная функция, вычисляющая n!}
begin
if n < 0 then writeln ('Ошибка в задании N')
else
if n = 0 then Fact := 1
else
begin
F:= Fact (n-1);
Fact := F * n;
end;
end;
begin
repeat
readln (n);
writeln ('n! = ', Fact (n));
until EOF;
end.
Напишем процедуру, которая будет бесконечно печатать некоторую фразу. Обратим внимание, если операторы переставить.
Например,
Uses crt;
Procedure pop;
Begin
Writeln ('\У попа была собака...');
Pop;
End;
Begin
Pop;
End.
Но, если в теле процедуры изменить последовательность операторов:
Например,
Uses crt;
Procedure pop;
Begin
Pop;
Writeln ('У попа была собака...');
End;
Begin
Pop;
End.
Такое качество алгоритма вытекает из того, что рекурсивная процедура указывает, что нужно делать.
В нашем примере вызов копии процедуры происходит раньше, чем вызов процедуры.
Формы рекурсивных процедур
Главное требование к рекурсивным программам заключается в том, что вызов рекурсивных процедур должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным.
Существуют 3 формы рекурсивных процедур:
1. форма с выполнением действий до рекурсивного вызова (на рекурсивном спуске):
procedure rec;
begin
s :=..;
if <условие> then rec;
end;
2. форма с выполнением действий после рекурсивного вызова (на рекурсивном возврате):
procedure rec;
begin
if <условие> then rec;
s :=..;
end;
3. форма с выполнением действий как до, так и после рекурсивного вызова (выполнение действий, как в рекурсивном спуске, так и в рекурсивном возврате).
Пример 1.
procedure rec;
begin
fl;
if <условие> then rec;
end;
Пример 2.
procedure rec;
begin
if <условие> then
begin
fl;
rec;
f2;
end;
end;
Задача 8.8. Составить процедуру вывода на печать символов строки в обратном направлении.
Листинг программы
Uses crt;
Procedure r;
Var
с : char;
Begin
If not eoln then
Begin
Read(c);
R;
Write(c);
End;
End;
Begin
Clrscr;
R;
End.
Задача 8.9о перевёртывании строки. Составить программу, которая позволяет вводить любой текст, и слово "end" будет прекращать работу программы.
Uses crt;
Type
st = string[20];
Var
s, s1 : st;
Function r (s_t :st): st;
Var
fl : char;
f2:st;
begin
if length (s_t) = 1 then r := s_t;
else
begin
fl := s_t[l];
delete (s_t, 1, 1);
f2:=r(s_t);
r := concat (f2,fl);
end;
end;
begin
clrscr;
repeat
writeln ('введите любой текст');
writeln ('слово "end" прекратит программу');
readln (s);
s1 := г (s);
writeln (s1, ' есть перевёрнутая ', s);
until s = 'end';
end.
Числа Фибоначчи
Первое и второе числа равны 1. Каждое последующее, начиная с третьего, есть сумма двух предшествующих: 1, 1, 2, 3, 5, 8, ...
Листинг программы
Uses crt;
Var
n, i : integer;
A : array [1..100] of integer;
Function fib (n : integer) : integer;
Begin
If (n = 1) and (n = 2) then fib := 1
Else
fib := fib (n- 1 ) + fib (n-2);
End;
Begin
Writeln (‘…’);
Readln (n);
For I := 1 to n do Writeln (Fib (i));
End.
Рекурсивный вызов может быть косвенным. В этом случае подпрограмма обращается к себе опосредованно, путём вызова другой подпрограммы, в которой содержится обращение к первой.
Например:
Procedure A (i : Byte);
Begin
…
B(i);
…
End;
Procedure В (j : Byte);
Begin
…
A(j);
…
End;
Если строго следовать правилу, согласно которому каждый идентификатор перед употреблением должен быть описан, то такую программную конструкцию использовать нельзя. Для того чтобы такого рода вызовы стали возможны, вводится опережающее описание:
Procedure B (j: Byte); forward;
Procedure A (i: Byte);
Begin
…
B(i);
…
End;
Procedure B;
Begin
…
A(j);
…
End;
Итак, опережающее описание заключается в том, что объявляется лишь заголовок процедуры В, а её тело заменяется стандартной директивой FORWARD. Теперь в процедуре А можно использовать обращение к процедуре В - ведь она уже описана, точнее, известны её формальные параметры, и компилятор может правильным образом организовать её вызов. Обратим внимание на то, что тело процедуры В начинается заголовком, в котором уже не указываются описанные ранее формальные параметры.
Вопросы для самопроверки
1. Дайте определение рекурсии?
2. Какие существуют формы рекурсивных процедур?
3. Что означает косвенный рекурсивный вызов подпрограмм?
4. В чём заключается назначение опережающего описания рекурсивной подпрограммы?
Модули
Модуль– это автономно – компилируемая программная единица, включающая в себя различные компоненты раздела описаний (типы, константы, переменные, процедуры и функции), и некоторые исполняемые операторы инициирующей части.
Компилятор Турбо Паскаля размещает программный код модулей в отдельном сегменте памяти. Максимальная длина сегмента не может превышать 64 Кбайт, однако, количество одновременно используемых модулей ограничивается лишь доступной памятью, что даёт возможность создавать весьма крупные программы.
Модули представляют собой прекрасный инструмент для разработки библиотек прикладных программ и мощное средство модульного программирования.
Модуль можно разделить на несколько разделов:
· Заголовок;
· Интерфейсная часть;
· Реализационная часть;
· Инициализационная часть.
Структура модуля
Заголовок модуля
UNIT Имя модуля
{$N+} Глобальные директивы компилятора
Интерфейсная часть
INTERFACE Начало раздела объявлений
USES Используемые при объявлении модули
Подразделы объявления доступных глобальных соответственно
LABEL меток
CONST констант
TYPE типов и
VAR переменных
Заголовки доступных соответственно
PROCEDURE процедур и
FUNCTION функций
Реализационная часть
IMPLEMENTATION Начало раздела реализации
USES Используемые при реализации модули
Подразделы объявления скрытых глобальных соответственно
LABEL меток
CONST констант
TYPE типов
VAR переменных
Тела доступных и скрытых соответственно
PROCEDURE процедур и
FUNCTION функций
Инициализационная часть
BEGIN
Основной блок модуля
END.
Заголовок модуля аналогичен заголовку программы: в модуле вместо зарезервированного слова PROGRAM используется слово UNIT.
Здесь могут присутствовать директивы компилятору, дающие общие установки и соглашения для всего модуля.
Например,
{$S+} - директива компилятору: включить (отключить) контроль возможного переполнения стека;
{$N+} - директива компилятору: использовать числовой процессор (реализовать операции с плавающей точкой программно), применяют для переменных типа real;
{$E+} - директива компилятору: включить (отключить) режим программной эмуляции сопроцессора, применяют для переменных типа extended – вещественное число повышенной точности (10 байт).
При написании модуля необходимо придерживаться следующих основных правил:
- Имя модуля, как и имя программы не должно совпадать с именами объектов (процедур, функций и т. д.) внутри модуля (программы).
- Имя модуля должно совпадать с именем файла, в котором он будет храниться. Отсюда, имя модуля не может состоять более чем из 8 символов.
В интерфейсной частиописываются все константы, типы данных и переменных, процедуры и функции, доступные в этом модуле для использования внешними программами. Интерфейсная часть модуля несёт всю информацию, необходимую для использования процедур и функций, определённых в модуле. Любая другая информация о модуле для обычного его использования не нужна.
Примечание. В рамках приложение Турбо Паскаль 7.0 поставляются стандартные модули System, Strings, Crt, Printer, Dos, WinDos, Graph, Overlay, Graph3 и Turbo3.
В интерфейсной части, возможно, сделать доступными для использования уже существующие готовые модули, указав их имена в операторе USES.
Следом за оператором USES описываются доступные извне и необходимые для описания процедур и функций определения типов данных, констант и переменных.
Все процедуры и функции, доступные для общего пользования и определённые в данном модуле, должны быть описаны в интерфейсной части своей строкой – заголовком с указанием типов параметров. Текст программы этих процедур и функций находится (с дубликатом их заголовка) в реализационной части.
Нет необходимости упоминать в интерфейсной части все процедуры и функции, используемые в реализационной части. Возможна ситуация, когда интерфейсная часть вообще ничего не содержит.
Реализационная часть – это часть, в которой определяются процедуры и функции.
Можем определить здесь, как и внутри обычной программы, глобальные (для модуля) переменные, типы данных и константы, которые не доступны извне, и могут использоваться программами, входящими в реализационную часть.
Как и интерфейсная часть, часть реализационная может быть пустой. Такую возможность используют, если необходимо определить некоторые общие для многих программ типы данных, константы и переменные. Имея такое определение в рамках одного проекта, легко включить его во все программы (неявные и подчинённые) с помощью оператора USES.
Инициализационная часть представляет собой основной блок модуля. Приведённые в ней операторы выполняются первыми, то есть они выполняются перед операторами основного блока главной программы, в которую включён данный модуль.
Чтобы окончательно оформить эту программу как модуль, необходимо сохранить объектный модуль данной программы на диске. Для опции Compile / Destination установить значение Disk и выполнить компиляцию с помощью комбинации клавиш [Ctrl + F9].
ТП7.0 распознаёт в начале текста модуля оператор модуля UNIT и автоматически создаст файл с расширением *.TPU вместо *.EXE (как для обычных программ). Выдаваемое при этом сообщение “Can not run a unit!” просто информирует Вас о том, что модуль самостоятельно не выполняется.
В опции Options / Directories установить значение параметра Include Directory равным пути, где расположен, подключаемый к основной программе, файл с расширением *.TPU (Turbo Pascal Unit), то есть модуль.
Задача 9.1. Вычислить значение функции F(x) по формуле
.
Нахождение корня n-ой степени осуществить через подпрограмму - функцию, а расчёт значения по формуле – через подпрограмму - процедуру. Подпрограммы поместить в модуль.
Листинг модуля Second
Unit second; {Имя модуля}
{second.pas}
interface {Начало раздела объявлений}
Function FunSqrt (x1 : real; k : integer) : real; {Вычисление корня числа}
Procedure ProcY (var y1 : real; x1 : real); {Расчёт значения по формуле}
Implementation {Начало раздела реализации}
Uses Crt;
Function FunSqrt; {Тело функции}
begin
FunSqrt := exp((1/k) * ln(x1));
end;
Procedure ProcY; {Тело процедуры}
Const b = 10.7;
c = 0.4;
var a : real;
begin
a := exp(0.1*x1) + x1;
y1 := ln(FunSqrt(a,2)) / (x1 + FunSqrt(b,3) + arctan(x1)) + c;
end;
End.
Листинг основной программы
program Task;
Uses crt,
second;{Подключение модуля, в котором хранятся функция вычисления корня и процедура вычисления значения по формуле}
Var x, y : real; {Глобальные переменные}
s : char;
begin
ClrScr;
Repeat
TextColor(12); {Розовый цвет текста}
Writeln('Введите значение переменной Х:');
Readln (x);
ProcY (y,x); {Вычисляется значение по формуле}
TextColor(9); {Синий цвет текста}
Writeln('Значение переменной Y равно :', '':2, y:10:6);
TextColor(14); {Жёлтый цвет текста}
Writeln('Продолжить (Y/N) ?');
Readln (s);
Until (s = 'N') or (s = 'n');
end.
Примечание. Так как заголовки функции Funsort и процедуры Procy в модуле были описаны в интерфейсной части, то это позволит пользователю использовать эти подпрограммы в любой другой внешней программе, подключив соответствующий модуль. Учитывая условия задачи, где требовалось во внешней программе вычислить только значение переменной y по указанной формуле, подставляя каждый раз различные значения x, то есть использовать только процедуру, необходимо изменить листинг модуля. Для этого достаточно описание заголовка функции Funsort, вычисляющей корень n-ой степени, из интерфейсной части переместить в раздел реализации.
Задача 9.2.Дана матрица A(n, m). Необходимо: упорядочить элементы в каждой строке матрицы по возрастанию, а сами строки расположить по убыванию количества положительных элементов в строке. В программе организовать вызов процедуры, реализующей общую часть задания. Формирование элементов массива A случайным образом, вывод элементов массива оформить в виде процедур. Сортировку строк и элементов в строках матрицы A оформить в подпрограммах (процедурах). Нахождение количества положительных элементов в строке матрицы А выполнить с помощью функции. Процедуры и функцию описать в модуле.
Листинг модуля Second2
unit second2;
Interface
Const n = 5; m = 5;
Type matr = array [1..n,1..m] of real;
mass1 = array [1..n] of real;
mass2 = array [1..m] of real;
var i1, j1, t, b : integer;
new : real;
Procedure wwod (var d : matr);
Procedure wuwod (var d : matr);
Procedure SortElem (i : integer; var d : matr);
Function Sum (i : integer; d:matr) : real;
Procedure SortRow (var d:matr; q : mass1);
Implementation
Procedure wwod;
begin
randomize;
for i1 := 1 to n do
for j1 := 1 to m do
d[i1,j1] := random;
end;
Procedure wuwod;
begin
for i1 := 1 to n do begin
for j1 := 1 to m do begin
write(d[i1,j1]:6:2); end;
writeln; end;
end;
procedure SortElem;
begin
b := m;
while b <> 0 do
begin
t := 0;
for j1 := 1 to B-1 do
begin
if d[i,j1] > d[i,j1+1] then
begin
new := d[i,j1];
d[i,j1] := d[i,j1+1];
d[i,j1+1] := new;
t := j1;
end;
end;
b := t;
end;
end;
Function Sum;
var s : real;
begin
s := 0;
for j1 := 1 to m do
if d[i,j1] > 0 then s := s + d[i,j1];
Sum := s;
end;
Procedure SortRow;
var new1 : mass2;
begin
b := n;
while b <> 0 do
begin
t := 0;
for i1 := 1 to b-1 do
begin
if q[i1] < q[i1+1] then
begin
for j1 := 1 to m do
begin
new1[j1] := d[i1,j1];
d[i1,j1] := d[i1+1,j1];
d[i1+1,j1] := new1[j1];
end;
new := q[i1];
q[i1] := q[i1+1];
q[i1+1] := new;
t := i1;
end;
end;
b := t;
end;
end;
end.
Листинг основной программы
Program First;
Uses crt, second2;
var i2, j : integer;
a : matr;
s1 : mass1;
begin
clrscr;
wwod(a);
writeln('***********');
for i2 := 1 to n do
begin
SortElem(i2,a);
s1[i2] := Sum(i2,a);
writeln('[',i2,']=',s1[i2]:6:2);
end;
wuwod(a);
writeln('***********');
SortRow(a,s1);
wuwod(a);
readln;
end.
Вопросы для самопроверки
1. Дайте определение модуля?
2. Какова структура модуля?
3. В чём заключается назначение заголовка модуля?
4. В чём заключается специфика интерфейсной части модуля?
5. В чём назначение реализационной части модуля?
6. Каково назначение инициализационной части модуля?
7. Как осуществляется компиляция, сохранение модуля на диске и подключение модуля во внешних программах?
Лабораторная работа №9
составление программ с использованием
модулей
Цель работы. Получение навыков в написании программ с использованием модулей.
Задание. Организация программ с использованием модулей.
Постановка задачи. По своему варианту написать программу, в которой подсоединяется модуль, содержащий подпрограммы - процедуры и - функции. Изучить структуру модуля, его разделы. Определиться с подпрограммами в модуле, которые могут использоваться внешними программами.
Варианты заданий
Оформить в основной программе вызов процедур и функций, содержащихся в модуле, в соответствии с вариантами заданий лабораторной работы №10.