Нетипизированные параметры-переменные

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

Нетипизированные параметры обычно используются в случае, когда тип данных несущественен. Такие ситуации чаще всего возникают при разного рода копированиях одной области памяти в другую, например, с помощью процедур 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))*e^cos(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+v², 3.14).

9. Напишите программу, выводящую на экран 10 строк по 5 случайных чисел из диапазона 0..36.

10. С помощью цикла for и функции odd напишите программу, выводящую все нечетные числа из диапазона 1..n.

11. Напишите программу, которая по значениям двух катетов вычисляет гипотенузу и площадь треугольника.

12. Напишите программу вычисления расстояния между двумя точками с заданными координатами X1,Y1,X2,Y2.

13. Напишите функцию возведения в степень по формуле: A^B=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 элементов. Определить сумму элементов с чётными индексами и сумму элементов с нечётными индексами.

1. Дано натуральное число n. Напишите программу, определяющую, есть ли среди чисел n, n+1, …, 2n «близнецы», т.е. простые числа, разность между которыми = 2. (Используйте процедуру распознания простых чисел).

3. Дан целочисленный массив размером 5x4. Отсортировать столбцы данного массива.4. Дан целочисленный массив размером 3x5. Определить максимальный элемент данного массива.5. Дан линейный массив из 15 целых чисел. Пересортировать массив по закону: первый меняется с последним, второй с предпоследним и т.д.6. Дан линейный массив из 25 целых чисел. Определить сумму положительных и сумму отрицательных элементов данного массива.7. Составить программу преобразования строки в "строку наоборот".8. Составить программу удаления лишних пробелов в строке.9. Составить программу определения количества цифр в целом числе.

1. Напишите процедуру – заставку к программе вычисления математических функций в виде

 

***********************************

* Программа

* вычисления математических функций

* Автор: Фамилия. И.О.

************************************

Заставка должна выводиться на очищенный экран, оставаться на экране в течение 3 сек. С последующей очисткой экрана. Вызовите процедуру Zastavka в начале программы.

11. Дан целочисленный массив, состоящий из 10 элементов. Все положи тельные элементы массива увеличить вдвое.12. Дан символьный массив, состоящий из 10 элементов. Преобразовать все маленькие латинские символы в большие.13. Дан символьный массив А, состоящий из 8 элементов. Получить целочисленный массив В, элементами которого являются номера символов по таблице ASCII. 14. Составить программу удаления лишних пробелов в строке.15. Описать процедуру InvertDigits(K), меняющую порядок следования цифр целого положительного числа К на обратный (К – параметр целого типа, являющийся одновременно входным и выходным). С помощью этой процедуры поменять порядок следования цифр на обратный для каждого из пяти данных целых чисел.16. Описать процедуру AddRightDigit(D,K), добавляющую к целому положительному числу К справа цифру D (D – входной параметр целого типа, лежащий в диапазоне 0-9, К – параметр целого типа, являющийся одновременно входным и выходным). С помощью этой процедуры последовательно добавить к данному числу К справа данные цифры D₁ и D₂, выводя результат каждого добавления.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 – вещественные параметры, являющиеся одновременно входными и выходными). С ее помощью упорядочить по возрастанию два набора из трех чисел: (A₁,B₁,C₁) и (A₂,B₂,C₂).20. Нарисовать на экране с помощью одной процедуры три окна с различными заголовками.

 

приложение В

1. Составьте программу вычисления суммы:

1. Составьте программу вычисления суммы:

При увеличении n эта сумма приближается к значению sin(x).

1. Напишите программу вычисления N-го члена последовательности, начинающейся с единицы, в которой каждый следующий член равен сумме обратных величин всех предыдущих.
2. Напишите программу вычисления N-го члена последовательности, начинающейся с единицы, в которой каждый следующий член равен сумме квадратов всех предыдущих.

5. Определите рекуррентное соотношение и напишите программу определения следующих трёх членов последовательности:1, 2, 6, 24, 120, 720, 5040,...6. Разработайте программу, где с помощью рекурсии осуществить вывод на экран монитора такой текст:

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. Написать рекурсивную функцию вычисления значения xⁿ, использую следующее рекурсивное соотношение: x⁰=1; хⁿ=(х^n/2)², если n>0 и n – четное число; хⁿ=х*(х^n/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 лет. Монахи всё ещё работают…