Будь умным!

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

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

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

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

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

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

от 25%

Подписываем

договор

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

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

 К. Поляков, 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.

Ещё пример задания:

Процедура F(n), где n – натуральное число, задана следующим образом (язык Паскаль):

procedure F(n: integer);

begin

 if n < 3 then

   write('*')

 else begin

   F(n-1);

   F(n-2);

   F(n-2)

 end;

end;

Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только натуральное число.

Решение:

  1.  эта задача по сути такая же, как и предыдущая, но «завёрнута» в другой фантик: для n < 3 (то есть, для 1 и 2) функция выводит одну звездочку

F(1) = F(2) = 1

а для бóльших n имеем рекуррентную формулу

 F(n) = F(n-1) + F(n-2) + F(n-2)

        = F(n-1) + 2*F(n-2)

  1.  запишем в таблицу базовые случаи

n

1

2

3

4

5

6

F(n)

1

1

3

5

11

21
  1.  заполняем таблицу, используя рекуррентную формулу:

n

1

2

3

4

5

6

F(n)

1

1

3

5

11

21

F(3) = F(2) + 2*F(1) = 3

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

F(5) = F(4) + 2*F(3) = 11

F(6) = F(5) + 2*F(4) = 21

  1.  ответ: 21.


Задачи для тренировки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 гг.


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

 6 http://kpolyakov.spb.ru




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

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