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

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

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

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

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

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

от 25%

Подписываем

договор

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

Скидка 25% при заказе до 28.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 гг.

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




1. Дзенник польски где поначалу пребывал в качестве редакционного мальчика на посылках занимался текущей
2. Розвиток мовлення молодших школярів
3. Германская модель социальной рыночной экономики
4.  ТЕОРЕТИКОМЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ ФОРМИРОВАНИЯ СИСТЕМЫ УПРАВЛЕНИЯ ЗАПАСАМИ В ТОРГОВОМ ПРЕДПРИЯТИИ
5. Контрольная работа по курсу Управление рисками имеет цель выявить знания по данной дисциплине полученные.html
6. I Trnslte the slides nswer the questions find geogrphicl objects on the mp nd show them to the group
7. Реферат- Общая характеристика Кипра (для развития туризма)
8. .Идеал двигатель ~ыздыр~ыштан ал~ан ~рбір килоджоуль энергияны~ есебінен 350 Дж механикалы~ ж~мыс ат~арады
9. Реферат- Образование и карьера
10. на тему- Развитие силы Выполнил студент 39 гр.