ИСПОЛЬЗОВАНИЕ РЕКУРСИИ ПРИ РЕШЕНИИ
ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ
1. Подпрограммы в языке Pascal
Очень часто в тексте программы встречаются одинаковые или очень похожие фрагменты. В этом случае их можно оформить в виде подпрограммы (вспомогательного алгоритма), т.е. одинаковые команды записываются в программе один раз, а вызываются на выполнение неограниченное число раз из любого места основной программы.
Результаты использования подпрограмм (ПП):
1) сокращается объем всей программы
2) уменьшается вероятность ошибок и облегчается процесс отладки программы
3) программа делится на отдельные блоки-подзадачи, которые могут разрабатываться разными программистами
3) возможность создания рекурсивных программ
Подпрограмму можно оформить 2 способами:
1) подпрограмма-функция - группа операторов, имеющая имя, вычисляющая какое-либо значение. Пример: y=sqrt(x).
2) подпрограмма-процедура - группа операторов, имеющая имя, выполняющая какое-либо действие. Пример: writeln(x,y).
Если в результате выполнения ПП необходимо получить только одно значение, то лучше использовать функцию, в остальных случаях - процедуру.
При работе с ПП необходимо знание следующих понятий:
Глобальные переменные объявляются в основной части программы и доступны в любом месте программы в т.ч. и всем подпрограммам.
Локальные переменные описываются в конкретной ПП и доступны только инструкциям этой ПП. После возврата из ПП локальные переменные недоступны.
Примечание: не рекомендуется давать глобальным и локальным переменным одинаковые имена, т.к. это затрудняет процесс отладки и читаемость программы.
Параметры ПП – переменные, которые используются для обмена значениями с основной программой.
Формальные параметры - параметры, используемые при описании подпрограммы.
Фактические параметры - параметры, используемые при вызове подпрограммы. Фактические параметры могут быть:
1) переменными или константами: sin(x),sin(pi)
2) функциями:sin(sqrt(x)+y)
3) числами: sin(3)
Параметры ПП делятся на 2 вида:
1) входные параметры - исходные данные. Во время выполнения ПП можно использовать как обычные локальные переменные, после выхода из ПП значения не сохраняются.
Оформление формальных параметров:
ИмяПП(имя1, имя2: тип1; имя3, имя4: тип2);
Оформление фактических параметров:
ИмяПП(имя1, имя2, имя3, имя4);
2) выходные параметры - используются для передачи результатов в основную программу. Во время выполнения ПП можно использовать как обычные глобальные переменные, значения после выхода из ПП сохраняются.
Оформление формальных параметров:
ИмяПП(var имя1, имя2: тип1; var имя3, имя4: тип2);
Оформление фактических параметров:
ИмяПП(имя1, имя2, имя3, имя4);
Примечания:
1) выходные параметры можно использовать и в качестве входных.
2) типы, кол-во и порядок записи переменных при вызове и описании ПП должны быть одинаковыми.
3) параметры ПП могут отсутствовать
4) ПП может использовать другую ПП
5) ПП может содержать вложенные ПП, которые будут доступны только этой ПП.
Оформление процедуры
Объявление:
procedureИмяПроцедуры(формальные параметры);
vаr {описание локальных переменных}
begin
{операторы процедуры}
end;
Вызов:
ИмяПроцедуры(фактические параметров);
Оформление функции
Объявление:
functionИмяФункции(формальные параметры): тип результата;
var{описание локальных переменных}
begin
{операторы функции};
ИмяФункции:=результат;
end:
Вызов:
Переменная:=ИмяФункции(список фактических параметров);
Примечание: тип переменной и тип результата функции должны совпадать.
Более подробные сведения по использованию ПП можно получить в справочнике по языку Pascal.
Пример: оформить в виде функции и процедуры ПП нахождения tg(x), где x задан в грудусах.
1) в виде функции
varx,y:real; {глобальные переменные}
functiontg(a:real):real; {a – формальный параметр, входной}
varb:real; {локальная переменныя}
begin
b:=a*pi/180;
tg:=sin(b)/cos(b); {вычисление результата функции}
end;
BEGIN
readln(x);
y:=tg(x); {вызов функции, x – фактический параметр}
writeln(y);
END.
2) в виде процедуры
varx,y:real; {глобальные переменные}
proceduretg(a:real;varc:real); {формальные параметры: a-входной,c-выходной}
varb:real; {локальная переменныя}
begin
b:=a*pi/180;
c:=sin(b)/cos(b); {запись результата в выходной параметр}
end;
BEGIN
readln(x);
tg(x,y); {вызов процедуры, фактические параметры:}
writeln(y); {х-входной, у-выходной}
END.
2. Понятие рекурсии
Рекурсивным называется объект, частично состоящий или определяемый с помощью самого себя (лат. recursio – «возвращение назад»).
Любое рекурсивное определение состоит из двух частей:
1) базовая часть – определяет объект через другие понятия
2) рекурсивная часть - определяет объект через него же
Пример рекурсивного определения стада коров:
1) 3 коровы – это стадо коров (базовая часть).
2) стадо из n коров – это стадо из n–1 коровы и еще одна корова (рекурсивная часть)
Попробуем применить это определение для проверки, является ли стадом группа из пяти коров (обозначим ее К5). Объект К5 не удовлетворяет первому пункту определения, поскольку пять коров – это не три коровы. Согласно второму пункту К5 – стадо, если там есть одна корова, а остальная часть К5, назовем ее К4, – тоже стадо коров. Решение относительно объекта К5 откладывается, пока не будет принято решение относительно К4. Объект К4 снова не подходит под первый пункт, а второй пункт гласит, что К4 – стадо, если объект К3, полученный из К4 путем отделения одной коровы, тоже стадо. Решение о К4 тоже откладывается. Наконец, объект К3 удовлетворяет первому пункту определения, и мы можем смело утверждать, что К3– стадо коров. Теперь и о К4 можно утверждать, что это стадо, а значит, и К5 является стадом коров.
Рекурсивные определения часто используются в математике. Так, многие определения математических формул рекурсивны. Например, вычисление факториала числа:
1) 0!=1, (базовая часть).
2) n!=n*(n-1)! (рекурсивная часть)
Если алгоритм прямо или косвенно вызывает самого себя, то он называется рекурсивным (или просто рекурсией). Часто в основе такого алгоритма лежит рекурсивное определение какого-либо понятия. На языке Pascal рекурсию можно записать с помощью рекурсивной процедуры или функции. Возможны 2 случая такого вызова:
1) Простая рекурсия – подпрограмма «A» непосредственно вызывает саму себя.
Общий вид оформления простой рекурсии (где СФоП – список формальных параметров, СфаП – список фактических параметров):
function ИмяФункции(СФоП): тип_резульата;
begin
…
if <условие> then ИмяФункции:=значение {базовая часть}
else ИмяФункции(СфаП); {рекурсивная часть}
…
end;
2) Косвенная рекурсия - подпрограмма «A» вызывает одну или несколько промежуточных ПП (B и С), которые уже, в конце концов, вызывают первую подпрограмму «A».
В языке Pascal перед использованием любого объекта необходимо его определить. Т.е. следующее описание будет ошибочным:
procedureC(СФоП);
begin
...
A(СфаП);
…
end;
procedure B(СФоП);
begin
...
С(СфаП);
…
end;
procedure A(СФоП);
begin
...
B(СфаП);
…
end;
В строке, выделенной жирным шрифтом, будет ошибка, т.к. процедура A еще не определена. Порядок описания процедур тоже не помогает. Возникает вопрос: «Как оформить такую рекурсию?».
В этом случае необходимо использовать директиву предописания forward,т.е. можно делать процедуры или функции известными без фактического определения ее операторной части. Где-то после предописания, тело процедуры или функции должно быть определено в соответствии с объявлением, определяющим операторную часть подпрограммы.
Верное описание косвенной рекурсии:
procedure B(СФоП);forward;
procedure C(СФоП); forward;
procedure A(СФоП);
begin
...
B(СфаП);
…
end;
procedure B; {СФоПне пишется}
begin
...
С(СфаП);
…
end;
procedureC; {СФоП не пишется}
begin
...
A(СфаП);
…
end;
Необходимо отметить, что косвенная рекурсия при решении задач встречается довольно редко.
3. Примеры решения задач
Задача №1. Вычислить факториал данного числа n.
Решение. Математическое определение: n!=1*2*…*(n-1)*n при n>0 и 0!=1. Для сравнения запишем решение «вычислением произведения».
varx,fact,i:longint;
BEGIN
readln(x);
fact:=1;
for i:=1 to x do fact:=fact*i;
writeln(fact);
END.
Рекурсивное определения факториала с помощью кусочно-заданной функции:
{$S+} {проверка переполнения стека – вкл.}
var x,y: longint;
function fact(n:longint):longint; {рекурсивнаяфункция}
begin
if n=0 then fact:=1 {базоваячасть}
else fact:=n*fact(n-1); {рекурсивнаячасть}
end;
BEGIN
readln(x);
y:=fact(x);
writeln(y);
END.
Работа рекурсивной функции. Если в функцию передается n>0, то происходит следующее: запоминаются известные значения членов выражения в ветви ELSE, а для вычисления неизвестных вызываются те же функции, но с «предшествующими» аргументами. При этом вновь запоминаются (в другом месте памяти!!!) известные значения членов и далее происходят вызовы. Так происходит до тех пор, пока выражение не станет полностью определенным (в данной задаче - это присваивание в ветви THEN), после чего алгоритм начинает “раскручиваться” в обратную сторону, изымая из памяти “отложенные” значения. Поскольку при этом на каждом очередном шаге все члены выражения уже будут известны, через n таких “обратных шагов” мы получим конечный результат.
Примечание. Внесение рекурсивности в программы придает им изящность. Но всегда оно же «заставляет» программы расходовать больше памяти. При вызове рекурсивной функции значения сохраняются в структуре типа СТЕК (метод доступа - «последним пришёл — первым вышел»). При достаточно большом количестве вызовов функции самой себя стек может переполниться и программа «зависнет». Рекомендуется компилировать программу с директивой {$S+}. Эта директива включает проверку переполнения стека, что приводит к завершению работы программы, а на экран выдается сообщение об ошибке 202Stackoverflow («ошибка переполнения стека»).
Также можно вручную попробовать увеличить размер стека с помощью директивы {$M+} – управление распределением памяти.
Синтаксис: {$M размер_стека, начало, конец}
Параметр "размер_стека" должен быть целым числом в диапазоне от1024 до 65520, что определяет размер сегмента стека.
Параметры "начало" должен быть в диапазоне от 0 до 655360, а "конец" в диапазоне от "начало" до 655360.
Чтобы не запоминать данные директивы можно нажать 2 раза клавиши <Ctrl>+<O>. В начале программы появятся две строки параметров, которые можно изменить по своему усмотрению (например,увеличить стандартный размер стека 16384).
{$A+,B+,D+,E+,F+,G-,I+,L+,N-,O+,P-,Q-,R-,S+,T-,V+,X+}
{$M 16384,0,655360}
Задача №2. Вычислить целую степень n числа x. Попробуйте решить эту задачу самостоятельно.
Решение. Рекурсивное определение факториала с помощью кусочно-заданной функции:
{$S+} {проверка переполнения стека – вкл.}
var a,b,x,n,y:longint;
function stepen(x,n:longint):longint;
begin
if n=0 then stepen:=1 {базоваячасть}
else stepen:=x*stepen(x,n-1); {рекурсивнаячасть}
end;
BEGIN
readln(a,b);
y:=stepen(a,b);
writeln(y);
END.
Задача №3. Найти наибольший общий делитель (НОД) двух заданных чисел x и y.
Решение. Рассмотрим сначала классическое решение с помощью алгоритма Евклида.
Для «ручного» счета алгоритм Евклида выглядит так:
1) если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма;
2) заменить большее число разностью большего и меньшего из чисел;
3) вернуться к выполнению п. 1.
varx,y:integer;
BEGIN
readln(x,y);
while x<>y do
if x>y then x:=x-y else y:=y-x;
writeln(x);
END.
Не всегда можно дать рекурсивное определение какого-либо понятия, хотя в данном случае это вполне возможно:
{$S+} {проверка переполнения стека – вкл.}
var a,b,x,y:integer;
function nod(x,y:integer):integer;
begin
if x=y then nod:=x {базоваячасть}
else
if x>y then nod:=nod(x-y,y) {рекурсивнаячасть}
else nod:=nod(x,y-x);
end;
BEGIN
readln(a,b);
writeln(nod(a,b));
END.
Т.к. в данном рекурсивном определении изменяются две переменные, то вместо рекурсивной функции можно использовать рекурсивную процедуру.
{$S+} {проверка переполнения стека – вкл.}
var x,y,a,b,c: integer;
procedure nod(x,y:integer; var z:integer); {рекурсивная процедура}
begin
ifx=ythenz:=x {базовая часть}
else if x>y then nod(x-y,y,z) {рекурсивнаячасть}
else nod(x,y-x,z);
end;
BEGIN
readln(a,b);
nod(a,b,c);
writeln(c);
END.
Примечание: в данной рекурсивной процедуре x,y – это входные параметры, z – выходной, поэтому перед ним стоит служебное слово var.
Необходимо отметить, что для решения задач, где рекурсивное определение можно записать с помощью кусочной функции (например, математические понятия) лучше подходит использование рекурсивной функции, а в остальных случаях - рекурсивной процедуры.
Задача №4 «Шахматный номер» (муниципальный тур олимпиады, 2002г.)
Телефонный номер называется "шахматным", если его цифры набираются на телефонном кнопочном номеронабирателе ходом шахматного коня. Написать программу, подсчитывающую, сколько можно набрать различных семизначных "шахматных" номеров, начинающихся с заданной цифры:
123
456
789
0
Технические требования:
Входной файл: INPUT.TXT содержит число [0..9].
Выходной файл: OUTPUT.TXT должен содержать единственное число – решение задачи.
Решение. Найдем количество возможных перемещений ходом шахматного коня из заданной цифры:три (для цифр 1, 3, 4, 6, 7, 9), два (для цифр 2, 8, 0) или нуль (для цифры 5). Определим эти перемещения в виде двумерного массива-константыmas с максимальным количеством возможных ходов три (отсутствие варианта хода обозначим -1). Например, строка с номером 2 означает, что из цифры 2 ходом шахматного коня можно попасть на цифру 7 или 9 (третий вариант -1, т.е. отсутствует).
Для подсчета общего количества найденных номеров будем использовать глобальную переменнуюtel, а для поиска номеров – рекурсивную процедуру poisk. В качестве параметров у этой процедуры будет текущая цифра в номере – d и количество цифр в уже найденном номере –s.
Определим необходимое для работоспособности рекурсивных процедур условие окончания рекурсивных вызовов (базовая часть). В данной задаче таких условия будет два:
1) невозможно получить следующую цифру в номере (d=-1)
2) найден "шахматным" номер из 7 цифр (s=7), при этом также необходимо увеличить на единицу общий счетчик найденных номеровtel.
const mas:array[0..9,1..3] of integer=
{0}(( 4, 6,-1),
{1} ( 6, 8,-1),
{2} ( 7, 9,-1),
{3}( 4, 8,-1),
{4} ( 3, 9, 0),
{5}(-1,-1,-1),
{6}( 1, 7, 0),
{7} ( 2, 6,-1),
{8} ( 1, 3,-1),
{9} ( 2, 4,-1));
varn,tel:integer; {tel – количество найденных номеров}
procedure poisk(d,s:integer); {рекурсивнаяпроцедура,где}
vari:integer; {d-текущая цифра,
begin {s-количество цифр в номере}
ifd<>-1then {базаовая часть, 1 условие}
if s=7 then tel:=tel+1 {базаоваячасть, 2 условие}
else {тривозможныххода}
for i:=1 to 3 do poisk(mas[d,i],s+1); {рекурсивнаячасть}
end;
BEGIN
assign(input, 'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
readln(n);
poisk(n,1);
writeln(tel);
END.
Примечание по вводу-выводу данных. В данной задаче используются системные файловые переменные input и output. Они позволяют переопределить с какого устройства будет осуществляться ввод-вывод данных по-умолчанию: с консоли (клавиатура/экран) или файла.
Преимущества данного способа работы с файлами:
1) В операторахread и write не нужно указывать файловую переменную.
2) Файловые переменныеinput и output не нужно описывать в разделе var.
3) Не нужно закрывать файлы, поскольку они объявлены в модулеSystem и закроются сами.
4) Просто закомментировав {} две строки с assign получим ввод-вывод на консоль, что удобнее для отладки программы.
Задача №5 «Вавилонская башня» (муниципальный тур олимпиады, 2008г.)
При строительстве Вавилонской башни, как известно, Бог смешал все языки. В результате оказалось, что каждый человек знает некоторое множество языков. Два человека могут передать друг другу информацию, если существует язык, который они оба знают. Руководитель стройки передает команды на известных ему языках. Те, кто эти команды получил, могут их передавать дальше, переводя на известные им языки. Определить количество людей, до которых доходят команды руководителя.
Входные данные:
Для удобства пронумеруем все языки числами от 1 до 50. Во входном файле задано количество людей N (1≤N≤100), а дальше идут описания того, какие языки знают эти люди. Для каждого человека записано сначала число Mi (0≤Mi≤50), определяющее количество языков, известныхi-ому человеку, а затем перечисляются номера самих этих языков в возрастающем порядке (номера языков – числа от 1 до 50). Считается, что руководитель строительства — это человек с номером 1.
Выходные данные:
В выходной файл вывести одно число — количество человек, до которых может «дойти» отданная руководителем команда (включая самого руководителя).
Примеры:
1)
input.txt output.txt
5 3
2 1 2
1 1
2 2 3
0
2 4 5
2)
input.txt output.txt
8 6
3 1 4 8
3 2 4 15
3 12 14 19
2 14 33
2 8 11
4 2 4 18 21
1 15
2 21 23
Решение.Для хранения данных о людях и языках, которые они знают, будем использовать одномерный массив множеств из 100 элементов с возможными значениями 1-50. Также будем использовать дополнительный одномерный массив логического типа znaet, показывающий дошла ли информация до человека (true-дошла,false-нет).
Для подсчета общего количества людей определим глобальную переменную vsego и рекурсивную процедуру poisk. В качестве параметра у этой процедуры будет номер текущего человека p, который узнал информацию.
Условия окончания рекурсивных вызовов (базовая часть):
1) найден человек уже знающий информацию (znaet[p]=true)
2) проверены все люди на совпадение общих языков (цикл от 1 до n)
Алгоритм работы рекурсивной процедуры:
Если человек с номером p еще не узнал информацию, то:
1) помечаем его как «знающего» и увеличиваем счетчик количества людей
2) процесс повторяется для каждого человека знающего общий язык с человеком p
3) так продолжается до тех пор, пока не будет выполнено условие окончания рекурсивных вызовов
var A: array[1..100] of Set of 1..50; {массивсязыками}
znaet: array[1..100] of boolean; {массив «знающих»людей}
i,j,k,n,m,p,vsego: integer;
procedure poisk(p:integer); {рекурсивнаяпроцедура}
var i: Integer;
begin
if not(znaet[p]) then begin {базоваячасть}
znaet[p]:=true; inc(vsego);
for i:=1 to n do
{если есть совпадающие языки у людей с номерами i и p, то запуск рекурсивной части}
if A[i]*A[p]<>[] then poisk(i);
end;
end;
BEGIN
FillChar(A, SizeOf(A), 0); {обнулениемассива A}
FillChar(znaet, SizeOf(znaet), false); {обнулениемассива znaet}
vsego:=0;
assign(input, 'input.txt'); reset(input);
assign(output, 'output.txt'); rewrite(output);
read(n); {ввод данных из файла}
for i:=1 to n do begin
read(m);
for j:=1 to m do begin
read(k);
include(A[i],k); {добавление языка k в множество A[i]}
end;
end;
poisk(1); {руководитель (№1) отдал команду}
writeln(vsego);
END.
Примечание: в данной программе для определения общих языков двух человек используется операция пересечения множеств (результатом является множество с элементами, которые одновременно есть и в первом и во втором множестве).
Пример для людей №1 и №2: [1,2]*[1]=[1] – есть общий язык №1
Пример для людей №1 и №3: [1,2]*[2,3]=[2] – есть общий язык №2
Пример для людей №1 и №5: [1,2]*[4,5]=[] – пустое множество, т.е. общих языков нет
4. Вместо заключения
Использование рекурсии - традиционное преимущество языка Pascal, но корректное использование ее – удел единиц. И дело здесь не только и даже не столько в том, что рекурсия сама по себе (как понятие) сложна для восприятия, сколько в том, что крайне трудно безошибочно определить грань между эффективным решением с помощью рекурсивной и стандартной (операторной) схем. Умение находить эту грань дает возможность учащимся успешно решать многие сложные задачи.
