2015-01-21
1232
Можно извлечь рекурсию
В формулировках некоторых задач рекурсия не присутствует в явном виде, но их можно свети к рекурсивным.
Пример 1. Сложение двух чисел. Пусть надо сложить два целых числа a и b, а можно только прибавлять или вычитать 1. Тогда:
если b=0, то a+b=a
если b>0, то a+b=(a+1)+(b-1)
если b<0, то a+b=(a-1)+(b-1)
Это есть рекурсивное определение операций сложения двух чисел.
Function Sum(a, b: integer): integer;
Begin
if b=0 Then Sum:=a
else if b>0 Then Sum:=Sum(a+1, b-1)
else Sum:=Sum(a-1, b+1);
end;
Пример 2. Найти НОД двух натуральных чисел.(2 способ)
Имеются два натуральных числа a и b.
Если a=b, то НОД(a,b)=a.
Если a>b, то НОД(a,b)=НОД(a-b,b).
Если a<b, то НОД(a,b)=НОД(a,b-a).
Function NOD(a,b: integer): integer;
Begin
if a=b Then NOD:=a
else if a>b Then NOD:=NOD(a-b,b)
else NOD:=NOD(a,b-a);
end;
| a | b | Примечание |
| Так как a>b, a:=a-b | ||
| a:=a-b | ||
| a:=a-b | ||
| Так как b>a, b:=b-a | ||
| b:=b-a | ||
| a:=a-b | ||
| a:=a-b | ||
| b:=b-a | ||
| Так как a=b, НОД:=a |
Пример 3. Перевести натуральное число из десятичной системы счисления в двоичную.
Function Rec(n: integer);
|
|
|
Begin
if n>1 Then Rec(n div 2);
Write(n Mod 2);
end;
III.Задачи, которые можно решить
Как частный случай обобщенной
Если нельзя извлечь рекурсию из постановки задачи, то можно расширить задачу, обобщить ее (например, введя дополнительный параметр). Удачное обобщение может помочь увидеть рекурсию. После этого возвращаемся к частному случаю и решаем исходную задачу.
Пример 1 Определить, является ли заданное натуральное число простым.
Данную задачу можно обобщить, например, так: определить, верно ли, что заданное натуральное число N не делится ни на одно число, большее или равное М (2£M£N), но меньше N.
Соответствующая функция должна принимать значение «истина» в двух случаях:
· если M=N;
· если N не делится на М и функция принимает значение «истина» для чисел М+1 и N.
Function Simple(m,n: integer): boolean;
Begin
if m=n Then Simple:=True
else Simple:=(n Mod m <> 0) And Simple(m+1,n);
end;
IV. Задачи, в которых можно использовать характеристику или свойство функции
Пример 1. Для заданного натурального числа N³1 определить натуральное число a, для которого выполняется неравенство:
2а-1 £ N < 2a.
a(N) = 1, если N=1
a(N)=a(N div 2) + 1, если N>1
Рассмотрим пример. Пусть N=34.
2a-1£34<2a, прибавим 1 и переходим к 34 div 2
2a-1£17<2a +1
2a-1£ 8<2a +1
2a-1£ 4<2a +1
2a-1£ 2<2a +1
2a-1£ 1<2a ; получим а=1
А теперь возвращаемся назад, к последней единице прибавляем все предыдущие. Таким образом, получается 6.
Function A(N: integer): integer;
Begin
if N=1 then a:=1 else a:=a (N div 2) +1;
end;
