Задачи для самостоятельного решения. Задачи для активного обучения

Задачи для активного обучения

Задача 3.1.

Исключить рекурсию из следующего рекурсивного определения:

.

Решение. Имеем , ,

, ,

и т. д.

Вероятно, функция имеет вид .

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

Таким образом, функция найдена верно.

Задача 3.2.

Исключить рекурсию из рекурсивного соотношения:

.

Решение. Рассматриваем следующие равенства ,

, ,

,

Можно предположить, что

Проверим выполнение рекурсивных соотношений: ,

.

Задача 3.3.

Для функции найти задающие ее рекурсивные соотношения.

Решение. Вычислим несколько первых значений

, ,

, ,

и т.д.

Можно предположить следующее: .

Для доказательства применим индукцию:

- очевидно, что ;

- допустим и покажем, что . Действительно

1. Найти для приведенных ниже рекурсивных функций:

а) б) в)

г) д) е)

2. Найти для следующих рекурсивных функций:

а) б)

в) г)

3. Найдите явные выражения для , исключив рекурсию из следующих определений:

а) б) в)

г) д) е)

4. Докажите, что удовлетворяет рекурсивному определению:

а) , б) ,

в) , г)

Дата добавления: 2014-12-27