Тема- рекурсивные алгоритмы

Работа добавлена на сайт samzan.net:

 К. Поляков, 2012-2013

B6 (базовый уровень, время – 2 мин)

Тема:  рекурсивные алгоритмы.

Что нужно знать:

•  рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа
•  чтобы определить рекурсию, нужно задать
  •  условие остановки рекурсии (базовый случай или несколько базовых случаев)
  •  рекуррентную формулу
•  любую рекурсивную процедуру можно запрограммировать с помощью цикла
•  рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным
•  существуют языки программирования, в которых рекурсия используется как один из основных приемов обработки данных (Lisp, Haskell)

Пример задания:

Алгоритм вычисления значения функции F(n), где n – натуральное число,

задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * n, при n > 1

Чему равно значение функции F(5)?

В ответе запишите только натуральное число.

Решение:

1.  используя заданную рекуррентную формулу, находим, что

F(5) = F(4) * 5

1.  применив формулу еще несколько раз, получаем

F(5) = F(3) * 4 * 5 = F(2) * 3 * 4 * 5 = F(1) * 2 * 3 * 4 * 5

1.  мы дошли до базового случая, который останавливает рекурсию, так как определяет значение F(1) = 1
2.  окончательно F(5) = 1 * 2 * 3 * 4 * 5 = 120
3.  ответ: 120.

Задачи для тренировки1:

1.   Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * (n + 1), при n > 1

Чему равно значение функции F(5)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * (n + 2), при n > 1

Чему равно значение функции F(5)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * (2*n + 1), при n > 1

Чему равно значение функции F(4)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * (2*n - 1), при n > 1

Чему равно значение функции F(5)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * (3*n - 2), при n > 1

Чему равно значение функции F(4)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(0) = 1, F(1) = 1

F(n) = F(n–1) + F(n-2), при n > 1

Чему равно значение функции F(7)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(0) = 1, F(1) = 1

F(n) = 2*F(n–1) + F(n-2), при n > 1

Чему равно значение функции F(6)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(0) = 1, F(1) = 1

F(n) = F(n–1) + 2*F(n-2), при n > 1

Чему равно значение функции F(6)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(0) = 1, F(1) = 1

F(n) = 3*F(n–1) - F(n-2), при n > 1

Чему равно значение функции F(6)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(0) = 1, F(1) = 1

F(n) = F(n–1)*F(n-2)+1, при n > 1

Чему равно значение функции F(6)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(0) = 1, F(1) = 1

F(n) = F(n–1)*F(n-2)+2, при n > 1

Чему равно значение функции F(5)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1, F(2) = 1

F(n) = F(n-2)*n, при n > 2

Чему равно значение функции F(7)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1, F(2) = 1

F(n) = F(n-2)*n + 2, при n > 2

Чему равно значение функции F(8)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1, F(2) = 1

F(n) = F(n-2)*(n-1), при n > 2

Чему равно значение функции F(7)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1, F(2) = 1

F(n) = F(n-2)*(n-1) + 2, при n > 2

Чему равно значение функции F(8)? В ответе запишите только натуральное число.

1.  Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:

F(1) = 3; F(2) = 3;

F(w) = 5*F(w-l)- 4*F(w-2) при w > 2.

Чему равно значение функции F(15)?

1.  Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:

F(1) = 4; F(2) = 5;

F(w) = 4*F(w-l)- 3*F(w-2) при w > 2.

Чему равно значение функции F(8)?

1.  (http://ege.yandex.ru) Алгоритм вычисления значений функций F(w) и Q(w), где w - натуральное число, задан следующими соотношениями:

F(1) = 1; Q(1) = 1;

F(w) = F(w-l) + 2*Q(w-1) при w > 1

Q(w) = Q(w-l) - 2*F(w-1) при w > 1.

Чему равно значение функции F(5)+Q(5)?

1.  Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:

F(1) = 1; F(2) = 2;

F(w) = 3*F(w-l)- 2*F(w-2) при w > 2.

Чему равно значение функции F(7)?

1.  Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:

F(1) = 2; F(2) = 4;

F(w) = 4*F(w-l)- 3*F(w-2) при w > 2.

Чему равно значение функции F(7)?

1.  (http://ege.yandex.ru) Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:

F(1) = 1; F(2) = 2;

F(n) = 5*F(n-l)- 6*F(n-2) при n > 2.

Чему равно значение функции F(7)?

1.  (http://ege.yandex.ru) Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:

F(1) = 1; F(2) = 2; F(3) = 3

F(n) = F(n-3)*(n-1)/3 при n > 3.

Чему равно значение функции F(16)?

1 Источники заданий:

Демонстрационные варианты ЕГЭ 2013 гг.

Проверочные работы МИОО.

 5 http://kpolyakov.narod.ru

1. на тему Художня культура періоду Реформації У художній культурі період
2. тема 5 Древнеиндийская философия как социокультурный феномен
3. 1 Утверждена постановлением Государственного комитета РФ по статистике от 06
4. раздавленная капля цель последовательность используемые материалы
5. Для просмотра документа в том виде в котором он будет выведен на печать необходимо нажать кнопку Ка
6. Вариант 3 Задача 1 Для 10 различных семей получены следующие статистические данные величин их нак
7. Использование материального стимулирования в задании векторов поляризации корпоративной культуры.html
8.  Предмет трудового права
9. по теме исследования п
10. то момент оказывается переполненным
11. Маркетинговые коммуникации ~ понятие и сущность В последние годы одновременно с возрастанием роли маркет.html
12. Виды доспехов
13. Реферат- Оптимизация химического состава сплава
14. Блок питания (БП)
15. СанктПетербург Недельный график- ежедневно Время работы-
16. Понятие и теоретические аспекты развития финансовопромышленных групп в Росси
17. на тему- Технопарки в России
18. эксплуатационной практики ~ закрепить и расширить полученные студентами в академии знания по ремонту и обс
19. рівень життя населення
20. Найдите слово игра и замените на слово мечта

Материалы собраны группой SamZan и находятся в свободном доступе