У вас вопросы?
У нас ответы:) SamZan.net

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

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

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 6.3.2025

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

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

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

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

  1. рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа
  2. чтобы определить рекурсию, нужно задать
  3. условие остановки рекурсии (базовый случай или несколько базовых случаев)
  4.  рекуррентную формулу
  5. любую рекурсивную процедуру можно запрограммировать с помощью цикла
  6. рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным
  7. существуют языки программирования, в которых рекурсия используется как один из основных приемов обработки данных (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.


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

  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)? В ответе запишите только натуральное число.

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

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

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

 3 http://kpolyakov.narod.ru




1. .ПР.15.ПЗ Лист Пров Щепина Е
2. Сутність маркетингу
3. 1 Понятие административного правоотношения
4. Именинник Birthdy Boy
5. тематика в Ы С Ш А Я М А Т Е М А Т И К А Методические указания и варианты
6. Терроризм1
7. Модуль аргумент комплексного числа
8. РЕФЕРАТ дисертації на здобуття наукового ступеня кандидата фармацевтичних наук.1
9. .ОБЩИЕ ПОЛОЖЕНИЯ О ТАМОЖЕННЫХ ПРОЦЕДУРАХ
10.  Полночь Сумерки уже сгустились на горизонте

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