Задачи, которые можно решить как частный случай обобщенной

Если нельзя извлечь рекурсию из постановки задачи, то можно расширить задачу, обобщить ее (например, введя дополнительный параметр). Удачное обобщение может помочь увидеть рекурсию. После этого возвра­щаемся к частному случаю и решаем исходную задачу.

Пример

Определить, является ли заданное натуральное чис­ло простым.

Решение

Данную задачу можно обобщить, например, так; оп­ределить, верно ли, что заданное натуральное число N не делится ни на одно число, большее или равное M (2≤M≤N), но меньшее N.

Соответствующая функция должна принимать зна­чение "истина" в двух случаях:

Если M=N;

Если N не делится на M и функция принимает значение "истина" для чисел М+1 и N.

ProgramExample_80;

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;

Вернемся к исходной задаче. Она является частным случаем обобщенной, если M положить равным 2. Пер­вое обращение к функции будет таким: Simple(2,N), где N − это данное число.

Задание

Изучить работу функции в пошаговом режиме и нарисовать схему вызовов функций.

Задачи, в которых можно

 использовать характеристику или свойство функции

Пример

Для заданного натурального числа N≥1 определить натуральное число a, для которого выполняется нера­венство: 2^a-1≤N≤2^a.

Решение

Заметим, что значение a зависит от N следующим образом:

1, если N=1;

a(N)=

a(N div 2)+1, если N>1.

Рассмотрим пример. Пусть N=34.

2^a-1≤34<2^a, прибавим 1 и переходим к 34 div 2

2^a-1≤17<2^a +1

2^a-1≤8<2^a +1

2^a-1≤4<2^a      +1

2^a-1≤2<2^a +1

2^a-1≤1<2^a получим a=1

А теперь возвращаемся назад, к последней единице прибавляем все предыдущие. Таким образом, получается 6. Опишем соответствующую функцию:

ProgramExample_81;

Function A(n: Integer): Integer;

Begin

If N=1 Then A:=1

Else A:=A(N div 2)+1;

End;

ФАЙЛОВЫЙ ТИП ДАННЫХ