Условия всех задач из категории B6

Проверяемые элементы содержания: умение исполнить рекурсивный алгоритм
 
 
 
 

Историческая справка и теоретические сведения

Треугольники СерпинскогоРеку́рсия - процесс повторения элементов самоподобным образом. Например, если два зеркала установить друг напротив друга, то возникающие в них вложенные отражения суть одна из форм бесконечной рекурсии.

Термин «рекурсия» используется в различных специальных областях знаний - от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций: рекурсивно заданная функция в своём определении содержит себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.

С рекурсией тесно связана математическая индукция: она является естественным способом доказательства свойств функций на натуральных числах, рекурсивно заданных через свои меньшие значения.

Содержание и мощность рекурсивного определения, а также его главное назначение, состоит в том, что оно позволяет с помощью конечного выражения определить бесконечное множество объектов.

Для создания рекурсивных алгоритмов необходимо и достаточно наличие понятия процедуры или функции. Программы, в которых используются рекурсивные процедуры отличаются простотой, наглядностью и компактностью текста.

 

Смежные определения, имеющие отношение к рекурсии:

  • максимальное число рекурсивных вызовов процедуры без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии;

  • число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии.

 

Методические указания

Для успешного решения задач из данной категории вы должны:

  1. знать наизусть определение рекурсии;

  2. глубоко понимать формы записи рекурсии (на спуске, на возврате, смешанный вариант);

  3. уметь исследовать предложенный алгоритм, записанный в математической форме и переводить его на "рельсы" алгоритмического языка или языка программирования;

  4. знать, хотя бы один из современных и востребованных языков программирования (например, Pascal, Basic, C, C++, Java, C#);

  5. уметь проводить графическую интерпретацию условия задачи и делать правильные логические умозаключения.

 
 
 
 

Задача №1

Дано:

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

F(1) = F(2) = 1

F(n) = F(n - 1) + F(n - 2), при n > 2.

 

Вопрос:

чему равно значение функции F(6)?

 
 
 
 
 
 

Задача №2

Информации нет

 
 
 
 
 
 

Задача №3

Информации нет

 
 
 
 
 
 

Задача №4

Информации нет

 
 
 
 
 
 
© 2011-2018 ООО "СтадиМен". Все права сохранены.
Перепечатка и использование материалов с данного сайта, разрешена только по согласию с владельцем.
Владелец оставляет за собой право воспользоваться 146 статьей УК РФ при нарушении авторских и смежных прав.
 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?