Нетипизированные параметры-переменные
Параметр считается нетипизированным, если тип формального параметра-переменной в заголовке подпрограммы не указан, при этом соответствующий ему фактический параметр может быть переменной любого типа. Заметим, что нетипизированными могут быть только параметры-переменные.
Нетипизированные параметры обычно используются в случае, когда тип данных несущественен. Такие ситуации чаще всего возникают при разного рода копированиях одной области памяти в другую, например, с помощью процедур BLOCKREAD, BLOCKWRITE, MOVE и т.п.
Нетипизированные параметры в сочетании с механизмом совмещения данных в памяти можно использовать для передачи подпрограмме одномерных массивов переменной длины (этот способ можно использовать в Турбо Паскале версии 6.0 и более ранней, в которых нет открытых массивов).
В примере 5.5 функция NORMA вычисляет норму вектора, длина которого меняется случайным образом. Стандартная константа MAXINT содержит максимальное значение целого типа INTEGER и равна 32767.
Следует учесть, что при обращении к функции NORMA массив X помещается в стек и передается по ссылке, поэтому описание локальной переменной А в виде одномерного массива максимально возможной длины в 65532 байта (встроенная константа MAXINT определяет максимально возможное значение типа INTEGER и равна 32767), совпадающего с X, на самом деле не приведет к выделению дополнительного объема памяти под размещение этой переменной. Иными словами, переменная А - фиктивная переменная, размер которой никак не влияет на объем используемой памяти. С таким же успехом можно было бы объявить ее в виде массива из одного элемента, правда, в этом случае необходимо позаботиться об отключении контроля выхода индекса за границы диапазона.
Пример 5.5
const NN = 100; {Максимальная длина вектора}
var а : array [1..NN] of Real;
i, j, N : Integer;
{----------------}
Function Norma (var x; N: Integer) : Real;
var
a : array [1..2*MaxInt div SizeOf (Real) ] of Real absolute x;
i : Integer;
s : Real;
begin {Norma}
s := 0;
for i := 1 to N do
s := s + sqr (a [i] ) ;
Norma := sqrt(s)
end {Norma} ;
{-------------------}
begin {main}
for i := 1 to 10 do
begin
N := Random (NN) + 1; {Текущая длина вектора}
for j := 1 to N do
a [ j ] : = Random ;
WriteLn ('N = ', N:2,’ норма = ',Norma(a, N):4:2)
end
end {main} .
Как видно из рассмотренного примера, передача одномерных массивов переменной длины не вызывает никаких трудностей. Сложнее обстоит дело с многомерными массивами, однако и в этом случае использование описанного приема (нетипизированный параметр и совмещение его в памяти с фиктивной переменной) все-таки проще, чем индексная арифметика. Еще раз напомню, что в случае многомерных массивов их элементы располагаются в памяти так, что при переходе от младших адресов к старшим наиболее быстро меняется самый правый индекс массива.
Рекурсия и опережающее описание
Рекурсия - это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе.
Рассмотрим пример простой программы с использованием рекурсии.
PROCEDURE WriteA;
Begin
Write(‘A’);
WriteA;
End;
BEGIN
WriteA;
END.
Данная программа, будучи запущенной, вызывает на исполнение процедуру WriteA. Первая команда процедуры печатает на экране букву «А», а вторая – вновь вызывает процедуру WriteA, т.е. саму себя. Вновь печатается «А», вновь вызывается процедура WriteA и т.д. Теоретически процесс должен идти бесконечно долго (пример бесконечной рекурсии), однако на практике спустя некоторое время появится сообщение: «Error 202: Stack overflow error – Переполнение стека». Дело в том, что перед каждым вызовом подпрограммы (процедуры или функции), в стеке запоминается текущая ситуация, чтобы корректно продолжить работу основной программы после завершения выполнения вызванной подпрограммы.
После этого стек освобождается от ненужной информации. А так как процедуры запускаются одна за другой, не дожидаясь завершения запущенных ранее, то и происходит переполнение стека.
Этот же пример можно представить в виде конечной рекурсии. Для этого перепишем программу так:
VAR I: Byte; {счетчик количества запусков процедуры WriteA}
PROCEDURE WriteA;
Begin
Inc(I); {подсчёт количества запусков процедуры WriteA}
Write(‘A’);
If I<3 then WriteA; {проверка условия выполнения рекурсии}
End;
BEGIN
I:=0; {сброс счётчика количества запусков процедуры WriteA}
WriteA;
END.
Как видим, процедура WriteA была вызвана только три раза и три раза была напечатана буква «А». После третьего вызова процедуры WriteA условие If I<3 перестало выполняться (а это есть ничто иное, как приказ на прекращение рекурсии) и третья процедура вернула управление второй процедуре, а та – первой и, наконец, первая процедура вернула управление основной программе. При этом стек последовательно разгружался и, наконец, полностью освободился.
Рассмотрим более сложный пример - вычисление факториала. Программа вводит с клавиатуры целое число N и выводит на экран значение N!, которое вычисляется с помощью рекурсивной функции РАС. Для выхода из программы необходимо либо ввести достаточно большое целое число, чтобы вызвать переполнение при умножении чисел с плавающей запятой, либо нажать Ctrl-Z и Enter.
При выполнении правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В примере 5.6 решение при N = 0 тривиально и используется для остановки рекурсии.
Пример 5.6
Program Factorial;
{$S+} {Включаем контроль переполнения стека}
var n: Integer;
Function Fact(fn: Integer): Real;
{Рекурсивная функция, вычисляющая n ! }
begin {Fact}
if fn < 0 then
WriteLn ('Ошибка в задании N')
else
if fn = 0 then
Fact := 1
else Fact := fn * Fact(fn-l)
end {Fact} ;
{---------------}
begin {main}
ReadLn (n);
WriteLn ('n!= ',Fact(n))
end {main} .
Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и дает более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека (при каждом входе в подпрограмму ее локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком). Переполнение стека особенно ощутимо сказывается при работе с сопроцессором: если программа использует арифметический сопроцессор, результат любой вещественной функции возвращается через аппаратный стек сопроцессора, рассчитанный всего на 8 уровней. Если, например, попытаться заменить тип REAL функции FACT (см. пример 5.6) на EXTENDED, программа перестанет работать уже при N = 8. Чтобы избежать переполнения стека сопроцессора, следует размещать промежуточные результаты во вспомогательной переменной. Вот правильный вариант примера 5.6 для работы с типом EXTENDED:
Program Factorial;
{$S+,N+,E+} {Включаем контроль Стека и работу сопроцессора}
var n: Integer;
Function Fact(n: Integer): extended;
var F: extended; {Буферная переменная для разгрузки стека сопроцессора}
{Рекурсивная функция, вычисляющая n! }
begin {Fасt}
if n < 0 then WriteLn ('Ошибка в задании N')
else
if n = 0 then Fact := 1
else
begin
F := Fact(n-l) ;
Fact := F * n
end
end {Fact} ;
{--------------}
begin {main}
ReadLn (n) ;
writeln('n! = ', Fact(n):4:2)
end {main} .
Пример 5.7
Нужно разработать программу, осуществляющую генерацию N чисел Фибоначчи[1]. Алгоритм генерации простой: первые два числа равны 1, каждое следующее число Фибоначчи равно сумме двух предыдущих. Например, для N = 6 это будет такая последовательность чисел: 1, 1, 2, 3, 5, 8.
Решение:
USES Crt;
VAR N, {количество чисел Фибоначчи}
i: Word; {счетчик чисел Фибоначчи}
FUNCTION Fib (N: Word) : Word;
Begin
If N <= 2 then Fib:=1 else
Fib:= Fib(N-1) + Fib(N-2);
End;
{ОСНОВНАЯ ПРОГРАММА:}
BEGIN
ClrScr;
Write(‘Введите количество выводимых чисел Фибоначчи: ‘);
ReadLn(N);
WriteLn(‘Подряд идущие числа Фибоначчи (в количестве ‘,N,’ шт.):’);
For i:=1 to N do Write(Fib(i),’ ‘);
ReadKey;
END.
Пример 5.8
Разработать программу, реализующую известную игру «Ханойские башни». Суть игры заключается в следующем. Имеется три стержня, на одном из которых нанизано N дисков разного диаметра: от самого большого в основании башни до самого малого сверху (рисунок 2).
Рисунок 2 – «Ханойские башни»
Требуется перенести по одному все диски со стержня 1 на стержень 3, используя (в качестве вспомогательного) стержень 2 и неукоснительно соблюдая при этом правило: запрещается укладывать больший диск на меньший[2].
Решение:
USES Crt;
VAR N, {количество дисков}
I:Word; {счетчик шагов}
PROCEDURE Perenos (N, C, Ha, Vspomogat: Word);
Begin
If N>0 then {признак необходимости выполнять новую рекурсию, не завершив текущую}
begin
Perenos(N-1, C, Vspomogat, Ha);
Inc(I); {наращивание показаний счетчика}
Write(I:3,’. ‘);
WriteLn(‘Перенесите диск со стержня ‘,C,’ на стержень ‘,Ha,’. Нажмите [Enter].’);
ReadKey;
Perenos(N-1, Vspomogat, Ha, C);
end;
End;
BEGIN
ClrScr;
TextColor(7);
writeln(‘Введите количество дисков: ‘);
ReadLn(N);
I:=0; {сброс счетчика ходов}
Perenos(N, 1, 3, 2);
TextColor(12);
WriteLn(‘Наступил конец света!’);
ReadKey;
END.
Для того чтобы переместить стопку из N дисков с базового стержня 1 на стержень 3, следует вначале перенести стопку из N-1 верхних дисков на вспомогательный стержень 2, после чего переложить самый нижний (и самый большой) диск со стержня 1 на стержень 3. Дальше, как вы догадались, стержень 2 стал базовым стержнем (здесь сосредоточились N-1 дисков), а опустевший стержень 1 стал вспомогательным. А задача осталась прежней: нужно самый нижний диск со стержня 2 перебросить на 3, где уже лежит самый большой диск. И так далее.
6 Методические рекомендации к выполнению работы
6.1 Протестировать следующую задачу: разработать процедуру, которая выводит на экран строку из символов псевдографики «=». Длина строки (количество символов «=») должна выступать в качестве параметра-значения этой процедуры и вводиться в диалоговом режиме из основной программы.
Решение:
USES Crt;
VAR Len: Byte; {длина строки (количество символов «=»)}
PROCEDURE StrokaSymb (L: Byte {длина строки});
Var I: Byte; {счетчик циклов}
Begin
For I:=1 to L do Write(‘=’);
End;
BEGIN
ClrScr;
Write(‘Введите длину строки (количество символов “=”): ‘);
ReadLn(Len);
StrokaSymb(Len);
ReadKey;
END.
6.2 Протестировать все примеры, приведенные выше в данных методических рекомендациях.
6.3 Выполнить индивидуальное задание, состоящее из трех задач. См. приложения А-В.
7 Контрольные вопросы
7.1 Что называется подпрограммой? В чем состоит сходство и различие подпрограмм-процедур и подпрограмм-функций?
7.2 В чем различие между стандартными и определенными пользователем подпрограммами? Привести примеры.
7.3 Записать синтаксическую диаграмму определения процедуры, функции.
7.4 Описать последовательность событий при вызове процедуры или функции.
7.5 В каких случаях в программе указывается директива компилятору {$I}?
7.6 Что называется параметром, и каково его назначение? Формальные, фактические параметры, их взаимосвязь.
7.7 Для чего используется исполнение программы в пошаговом режиме с заходом в процедуры, и как это осуществить?
7.8 Каковы отличия параметров-значений от параметров-переменных, особенности их описания и применения?
7.9 Каковы особенности параметров-процедур и параметров-функций?
7.10 Чем отличаются локальные и глобальные параметры? Какова область их действия?
7.11 Что такое рекурсия?
7.12 В каких случаях требуется предварительное или внешнее описание подпрограмм? Каковы особенности использования подпрограмм с предварительным описанием?
7.13 Сформулировать правила использования открытых массивов и строк.
7.14 Стандартные директивы, их назначение.
7.15 Назвать процедуры управления программой.
7.16 Определить значения переменных X и Y, которые будут выданы на экран в результате
выполнения следующей программы:
var X, Y : integer;
procedure p1(A : integer; var B : integer);
begin
B:=sqr(3*A)-6
end;
begin
X:=3; p1(X, Y);
write(X, Y)
end.
7.17 Определить значения элементов массива А, которые будут выведены на экран в результате выполнения следующей программы:
const n=8;
type mas = array[1..n] of real;
var A : mas; j : integer;
procedure p2(var B : mas);
var i : integer;
begin
for i:= 2 to n do
B[i] := B[i-1] + 1.0
end;
begin
for j:= 1 to n do A[j] :=0.0;
p2(A);
for j:= 1 to n do writeln(A[j])
end.
7.18 Определить значения переменных X1, X2, A1, A2, которые будут выведены на экран в результате выполнения следующей программы:
var X1, X2 : integer;
procedure p1(A1 : integer; var A2 : integer);
begin
A1 := A1 * A1;
A2 := A1 * A1 + A1;
write(A1, A2)
end;
procedure p2(var A1, A2 : integer);
begin
A1 := A1 * A1;
A2 := A1 * A1 + A1;
writeln(A1, ‘ ‘, A2)
end;
begin
X1 := 1; X2 := 2;
p1(X1, X2);
write(X1, ‘ ‘, X2);
X1 := 2; X2 := 3;
write(X1, ‘ ‘, X2)
end.
7.19 Может ли функция иметь такую структуру:
FUNCTION F: Real;
Label 1, 2;
Var A:Byte;
Begin
Тело функции
End;
приложение А
1. Напишите программу вычисления среднего геометрического модулей двух введенных с клавиатуры целых чисел X и Y. Программа должна использовать цикл WHILE DO.Условие выхода из цикла – значение числа, равное 999. (Средним геометрическим называется корень квадратный из произведения двух чисел.)
2. Напишите программу вычисления выражения y=(tg(x)+sin(x))*ecos(x) при x=3.7. Результат выведите в формате 5:2.
3. Напишите программу, которая находит первое отрицательное число последовательности: A=Sin(i/100).i=1,2,3…
4. Напишите программу, которая с помощью функции Chr выводит на экран кодовую таблицу ASCII. После задержки в 5 сек. очистите экран.
5. Напишите функцию преобразования градусной меры в радианную.6. Напишите функцию преобразования времени выраженного в сутках, часах, минутах и секундах просто в секунды.7. Даны действительные числа s, t. Получить g(1.2,-s) + g(t,s) - g(2s-1,st), где
.8. Даны действительные числа x,y. Определить u = min(x,y), v= min(xy, x+y), z = min(u+v2, 3.14). 9. Напишите программу, выводящую на экран 10 строк по 5 случайных чисел из диапазона 0..36.
10. С помощью цикла for и функции odd напишите программу, выводящую все нечетные числа из диапазона 1..n.
11. Напишите программу, которая по значениям двух катетов вычисляет гипотенузу и площадь треугольника.
12. Напишите программу вычисления расстояния между двумя точками с заданными координатами X1,Y1,X2,Y2.
13. Напишите функцию возведения в степень по формуле: AB=Exp(Ln(A)*B) и используйте ее в программе для возведения в 4-ю степень вещественного числа 2,87.
14. Определите наименьший общий делитель трех натуральных чисел.
15. Данные действительные числа s,t. Напишите программу вычисления выражения f(t,-2s, 1.17)+f(2.2, t, s-t), где f(a, b, c) = (2a – b – sin (c)) / (5+|c|).
16. Создайте программу перевода двоичной записи натурального числа в десятичную.
17. Создайте программу сокращения дроби M/N, где M,N – натуральные числа.
18. Создайте программу для вычисления суммы квадратов простых чисел, лежащих в интервале (M, N).
19. Создайте программу для подсчета количества четных цифр, используемых в записи N-значного числа M.
20. Создайте программу вычисления суммы трехзначных чисел, в десятичной записи которых нет четных цифр.
21. Создайте программу вывода на экран всех натуральных чисел, не превосходящих N и делящихся на каждую из своих цифр,
22. Создайте программу нахождения наименьшего натурального N-значного числа x(x>=10), равного утроенному произведению своих цифр.
приложение Б
1. Дан целочисленный массив, состоящий из 12 элементов. Определить сумму элементов с чётными индексами и сумму элементов с нечётными индексами.- Дано натуральное число n. Напишите программу, определяющую, есть ли среди чисел n, n+1, …, 2n «близнецы», т.е. простые числа, разность между которыми = 2. (Используйте процедуру распознания простых чисел).
- Напишите процедуру – заставку к программе вычисления математических функций в виде
***********************************
* Программа
* вычисления математических функций
* Автор: Фамилия. И.О.
************************************
Заставка должна выводиться на очищенный экран, оставаться на экране в течение 3 сек. С последующей очисткой экрана. Вызовите процедуру Zastavka в начале программы.
11. Дан целочисленный массив, состоящий из 10 элементов. Все положи тельные элементы массива увеличить вдвое.12. Дан символьный массив, состоящий из 10 элементов. Преобразовать все маленькие латинские символы в большие.13. Дан символьный массив А, состоящий из 8 элементов. Получить целочисленный массив В, элементами которого являются номера символов по таблице ASCII. 14. Составить программу удаления лишних пробелов в строке.15. Описать процедуру InvertDigits(K), меняющую порядок следования цифр целого положительного числа К на обратный (К – параметр целого типа, являющийся одновременно входным и выходным). С помощью этой процедуры поменять порядок следования цифр на обратный для каждого из пяти данных целых чисел.16. Описать процедуру AddRightDigit(D,K), добавляющую к целому положительному числу К справа цифру D (D – входной параметр целого типа, лежащий в диапазоне 0-9, К – параметр целого типа, являющийся одновременно входным и выходным). С помощью этой процедуры последовательно добавить к данному числу К справа данные цифры D1 и D2, выводя результат каждого добавления.17. Описать процедуру Swap(X,Y), меняющую содержимое переменных X и Y (X и Y – вещественные параметры, являющиеся одновременно входными и выходными). С помощью этой процедуры для переменных А, В, С и D последовательно поменять содержимое следующих пар: А и В, С и D, В и С и вывести новые значения А, В, С и D.18. Описать процедуру DigitCountSum(K,C,S), находящую количество С цифр целого положительного числа К, а также их сумму S (K – входной, C, S – выходные параметры целого типа). С ее помощью найти количество и сумму цифр для каждого из пяти данных целых чисел.19. Описать процедуру SortInc3 (A,B,C), меняющую содержимое переменных А, В, С таким образом, чтобы их значения оказались упорядоченными по возрастанию (A,B,C – вещественные параметры, являющиеся одновременно входными и выходными). С ее помощью упорядочить по возрастанию два набора из трех чисел: (A1,B1,C1) и (A2,B2,C2).20. Нарисовать на экране с помощью одной процедуры три окна с различными заголовками.приложение В
- Составьте программу вычисления суммы:
- Составьте программу вычисления суммы:
- Напишите программу вычисления N-го члена последовательности, начинающейся с единицы, в которой каждый следующий член равен сумме обратных величин всех предыдущих.
- Напишите программу вычисления N-го члена последовательности, начинающейся с единицы, в которой каждый следующий член равен сумме квадратов всех предыдущих.
10 маленьких негритят пошли купаться в море,
10 негритят резвились на просторе.
Один из них пропал – и вот вам результат:
(небольшая пауза)
9 маленьких негритят пошли купаться в море,
9 негритят резвились на просторе.
Один из них пропал – и вот вам результат:
(небольшая пауза)
…
1 маленький негритенок пошел купаться в море,
1 негритенок резвился на просторе.
Пропал и он – и вот вам результат:
(небольшая пауза)
Нет больше негритят!
7. В массиве Х(n) целых чисел найти минимальное. Поиск осуществить с помощью рекурсии.8. Дано целое число N>0. Написать рекурсивную функцию, выводящую на печать числа 1, 2, …, N.9. Написать рекурсивную функцию, выводящую на печать m строк, состоящих из n символов каждая.10. Написать рекурсивную функцию, вычисляющую произведение элементов массива A(N).11. Дано целое число N>0. Написать рекурсивную функцию, выводящую на печать числа N, N-1, …, 2, 1.12. Написать рекурсивную функцию, вычисляющую сумму первых n целых чисел, хранящихся в массиве, длина которого больше или равна n.13. Написать рекурсивную функцию, выводящую на печать строку символов в обратном порядке.14. Проанализируйте следующее рекурсивное соотношение: f(1)=1; f(2)=1; f(3)=1; f(4)=3; f(5)=5; f(n)=n-1+3*f(n-5) для всех n>5. Вычислите функцию f(n) для следующих значений n: 6, 7, 12, 15.15. Написать рекурсивную функцию вычисления значения xn, использую следующее рекурсивное соотношение: x0=1; хn=(хn/2)2, если n>0 и n – четное число; хn=х*(хn/2)2, если n>0 и n – нечетное число.16.[1] Итальянский математик, известный ещё как Леонардо Пизанский, живший на рубеже XII и XIII веков. Ряд Фибоначчи впервые был применен для моделирования размножения кроликов. Кроме того, ряд имеет тайную силу: если последовательно делить два текущих последних члена ряда друг на друга, то будем получать результаты, известные под названием «золотого сечения».
[2] В соответствии с легендой, когда монахи ханойского храма переместят 64 диска со стержня 1 на стержень 3, наступит конец света. Количество перемещений Р для N дисков подсчитывается по следующей рекурсивной формуле: P(N) = 2 × P(N-1) + 1. В конце концов нужно достичь P(1)=1. Например:
Если N=3, то P(3) = 2 × P(2) +1 = 2 × (2 × 1 + 1) + 1 = 7.
Если N=10, то P(10) = 1023.
Если N=20, то P(20) = 104857.
Если N=64, то P(64) = 18 446 744 073 709 551 615. Если монах будет перемещать диски со скоростью 1 диск в секунду, то на перекладывание 64 дисков со штыря 1 на штырь 3 (в режиме работы 24 часа в сутки, без сна и отдыха, без выходных и отпусков) потребуется почти 585 миллиардов лет! Точнее: 584 942 417 355 лет. Монахи всё ещё работают…