Будь умным!

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

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

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

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

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

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

от 25%

Подписываем

договор

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

Скидка 25% при заказе до 27.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.  Наприклад нормальне співвідношення білків жирів та вуглеводів має бути 1 - 11 -41 для молодих чоловіків та
4. ФОРМИРОВАНИЕ МАРКЕТИНГОВОЙ СТРАТЕГИИ 2
5. менеджмент трактуется как манера общения с людьми искусство управления административная единица
6. Октябрьская средняя общеобразовательная школа Курского района Курской области.html
7. 12 УЧЕБНЫЕ ЦЕЛИ - изучить комплекты ЗИП назначение отдельных элементов изучить смазки применя
8. ЯРМАРОК ОСВІТИ 79 листопада 2013 р.
9. УТВЕРЖДАЮ СОГЛАСОВАНО Председатель МУ Комит
10. Истории западной философии 1945 изложение основных философских концепций с античности и до времени напис
11. Понятийный аппарат научного исследования
12. тема занятий реализация которой позволяет сформировать ответственное отношение к своему здоровью у детей д
13. Бiология Спеціальність 6
14. Капитальный ремонт звеньевого пути на деревянных шпалах с постановкой на щебень и укладкой рельсовых плетей бесстыкового пути
15. тема крайних с точки зрения общества взглядов и действий направленных на удовлетворение политических инте
16. Мораль и её функции
17. ЯГМЦ Е.html
18.  Чистые активы экономики определяются- а как разность между нефинансовыми и финансовыми активами включая
19. психологии в контексте общественного развития и в ее взаимосвязи с другими отраслями знания
20. if b 3 5 then b 3 5 2 if 3 b 4 2 0 then

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