Задания для самостоятельной работы
Самостоятельно выполните следующие задания:
Создайте приложение, в котором гамма шифра вырабатывается с помощью генератора случайных чисел, а не вводится вручную;
Процесс шифрования/дешифрования опишите как функцию, а не процедуру.
Напишите процедуру и функцию шифрования методом Цезаря. При шифровании методом Цезаря каждый символ в открытом тексте заменяется буквой находящейся на некоторое постоянное число позиций левее или правее него в алфавите. Например, в шифре со сдвигом 3, А была бы заменена на Г, Б станет Д, и так далее.
Контрольные вопросы
Особенности организации процедур и функций в Delphi
Методы описания процедур и функций
Способы передачи параметров в процедурах и функциях
Варианты подключения процедур
Лабораторная работа № 6. Рекурсивные процедуры и функции
ЦЕЛЬ ЗАНЯТИЯ: Освоить работу с рекурсивными процедурами и функциями.
ПОДГОТОВКА К РАБОТЕ:
Ознакомиться с особенностями работы рекурсивных процедур и функций:
Ознакомиться с правилами завершения рекурсивных процедур и функций.
Если процедура или функция в ходе выполнения вызывает саму себя, то мы имеем дело с рекурсией. Рекурсивные процедуры и функции бывают двух видов:
Нисходящая рекурсия;
Восходящая рекурсия.
Рассмотрим эти виды рекурсии на примере вычисления факториала числа. При нисходящей рекурсии функция вычисления факториала числа будет иметь вид:
Function Fact(n:Byte):Integer;
Begin
If n=0 then Fact:=1 // Терминальная ветвь
Else Fact:=n*Fact(n-1) // Рекурсивная ветвь
End;
При нисходящей рекурсии функция вызывает себя до тех пор, пока не будет достигнута терминальная ситуация. При каждом вызове текущие вычисления откладываются, локальные переменные и адрес возврата сохраняются в стеке. При достижении терминальной ситуации рекурсивный спуск заканчивается, начинается рекурсивный возврат изо всех вызванных на данный момент копий функции; сохраненные локальные параметры выбираются из стека в обратной последовательности, а получаемые промежуточные результаты передаются вызывающим функциям. Так при вычислении факториала, например вида Fact(5), функция Fact вызывает себя раз за разом: Fact(4), Fact(3) и т.д. Терминальная ситуация Fact:=1 достигается при n=0. После чего промежуточные результаты: 1*1, 2*1, 3*2*1, 4*3*2*1, 5*4*3*2*1 передаются вызывающим функциям.
При восходящей рекурсии ответ строится на каждой стадии рекурсивного вызова, получаемые промежуточные результаты вычисляются перед рекурсивным вызовом и передаются в виде дополнительного рабочего параметра подпрограммы до тех пор, пока не будет достигнута терминальная ситуация. К этому моменту ответ уже готов и нужно только передать его вызывающей функции верхнего уровня.
При восходящей рекурсии функция вычисления факториала числа будет иметь вид:
Function Fact(n:Byte; w:Integer):Integer;
Begin
If n=0 then Fact:=w // Терминальная ветвь
Else Fact:=Fact(n-1, n*w) // Рекурсивная ветвь
End;
Здесь w – рабочий параметр, применяемый для формирования результата. При первом вызове функции этот параметр надо инициализировать (придать ему начальное значение 1), далее при каждом рекурсивном вызове, например, при вычислении 5!, он принимает последовательно значения: 5*1, 4*5*1, 3*4*5*1, 2*3*4*5*1,1*2*3*4*5*1.
ЗАДАНИЕ: Найти наибольший общий делитель (НОД) двух натуральных чисел n и m по алгоритму Эвклида, используя рекурсивную функцию. Алгоритм заключается в следующем: если m является точным делителем n, то НОД=m, в противном случае нужно брать функцию НОД от m и от остатка деления n на m.
Последовательность действий:
Создайте приложение, изображенное на рисунке 6.1.
Создайте рекурсивную функцию следующего вида:
Function NOD (n,m:byte):byte;
begin
If m>n then NOD:=NOD(m,n) // Рекурсивная ветвь
else
If m=0 then NOD:=n // Терминальная ветвь
else NOD:=NOD(m,n mod m) // Рекурсивная ветвь
end;
Для события OnClick кнопки «Вычислить» напишите следующий программный код:
procedure TForm1.Button1Click(Sender: TObject);
Var n,m,nd:Byte;
begin
n:=StrToInt(Edit1.Text);
m:=StrToInt(Edit2.Text);
nd:=NOD(n,m);
ShowMessage(IntToStr(nd));
end;
Откомпилируйте приложение и проверьте его работу.
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
Используя рекурсию, найдите в массиве максимальный и минимальный элементы.
Используя рекурсию, напишите функцию вычисления суммы цифр натурального числа.
Напишите рекурсивную процедуру для вывода на экран цифр натурального числа в обратном порядке. Напишите рекурсивную процедуру перевода натурального числа из десятичной системы счисления в двоичную.