Студопедия
МОТОСАФАРИ и МОТОТУРЫ АФРИКА !!!

Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

II. Задачи, из постановки которых




Можно извлечь рекурсию

В формулировках некоторых задач рекурсия не присутствует в явном виде, но их можно свети к рекурсивным.

Пример 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)

Это есть рекурсивное определение операций сложения двух чисел.

FunctionSum(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).

FunctionNOD(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.Перевести натуральное число из десятичной системы счисления в двоичную.

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

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-21; просмотров: 1025; Опубликованный материал нарушает авторские права? | Защита персональных данных


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Как то на паре, один преподаватель сказал, когда лекция заканчивалась - это был конец пары: "Что-то тут концом пахнет". 8838 - | 8364 - или читать все...

Читайте также:

  1. EXERCISE 5. Найдите пять предложений, в которых содержится сложное подле­жащее
  2. I. Из данных предложений выпишите те, сказуемое которых стоит в пассиве. Подчеркните в них сказуемое и переведите эти предложения
  3. I. Из данных предложений выпишите те, сказуемое которых стоит в пассиве. Подчеркните в них сказуемое и переведите эти предложения
  4. I. Краткие теоретические сведения. Вещества, растворы которых в воде и некоторых других диэлектрических жидкостях проводит электрический ток
  5. II. Постановка учебной задачи, сообщение темы урока
  6. IV. Найдите предложения, в которых нет грамматической ошибки. Исправьте ошибки в остальных предложениях
  7. IV. Найдите предложения, в которых нет грамматической ошибки. Исправьте ошибки в остальных предложениях
  8. PR в политике. Понятие, цели, задачи, основные направления деятельности, методы и функции PR в политике. Понятие политической корректности. Политический имидж
  9. V.19 О некоторых исторических загадках
  10. А) Алгоритм постановки холодного компресса
  11. Алгоритм постановки газоотводной трубки


 

18.232.51.69 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.002 сек.