Как частный случай обобщенной

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

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

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

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

· если M=N;

· если N не делится на М и функция принимает значение «истина» для чисел М+1 и N.

FunctionSimple(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.

FunctionA(N : integer) : integer;

Begin

if N=1 then a:=1 else a:=a (N div 2) +1;

End;








Дата добавления: 2015-01-15; просмотров: 713; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию, введите в поисковое поле ключевые слова и изучайте нужную вам информацию.

Поделитесь с друзьями:

Если вам понравился данный ресурс вы можете рассказать о нем друзьям. Сделать это можно через соц. кнопки выше.
helpiks.org - Хелпикс.Орг - 2014-2021 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.