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

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

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

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

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

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

от 25%

Подписываем

договор

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

Скидка 25% при заказе до 6.4.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. Центр развития ребенка ~ детский сад 49 Сценарий новогоднего праздника в подготовитель
2. логическая операция перехода от родового понятия к видовому например ldquo;поэтrdquo; ldquo;великий поэтrdquo; ldq
3. тема распределённого отображения информации Литера 0
4. Художественное творчество как средство самовыражения и развития ребенка
5. важнейшая продовольственная техническая и кормовая культура условия посадки уход болезни вредители и.html
6. Билеты за курс средней школы (2003г
7. Курсовая работа- Витрины магазина
8. Вступление ~ Rude wkening ~ Нелестное Откровение Начиная просматривать личные письма Шрилы Прабхупады здесь и да
9. Психогенетика как наука
10. РЕФЕРАТ ПОРІВНЯЛЬНА ХАРАКТЕРИСТИКА Сальвадора та Фінляндії

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