Упражнения. 7. Можно ли случай косвенной рекурсии свести к прямой рекурсии?

Вопросы

Набор для практики

7. Можно ли случай косвенной рекурсии свести к прямой рекурсии? Ответ обоснуйте.

8. Может ли рекурсивная база содержать несколько тривиальных случаев? Ответ обоснуйте.

9. Являются ли параметры, база и декомпозиция единственными для конкретной задачи? Ответ обоснуйте.

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

11. Является ли рекурсия универсальным способом решения задач? Ответ обоснуйте.

12. Почему для оценки трудоемкости рекурсивного алгоритма недостаточно одного метода подсчета вершин рекурсивного дерева?

13. Выполните оценку алгоритма из Примера 3 методом подсчета вершин рекурсивного дерева для случая n = 6, k = 6.

6. Наберите коды программ из Примеров 1-4. Выполните компиляцию и запуск программ.

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

8. В Фибоначчиевой системе счисления числа формируются по правилам.

· Используются только символы 0 и 1;

· Каждый разряд соответствует элементу последовательности Фибоначчи 1, 2, 3, 5, 8, …, то есть указывает на наличие или отсутствие такового;

· В соседних разрядах не могут стоять символы 1, так как это автоматически означает формирование следующего за ними разряда. Например, 1710 = 1310 + 310 + 110 = 100101_ф.

Составьте программу перевода числа из десятичной системы в Фибоначчиевую. Считать входные данные введенными корректно.

9. Найдите походящие дроби рационального числа (х – неотрицательно, у – положительно). Например, , то есть для х = 5, у = 6 ответом будет последовательность [0; 1, 5].

10. Вычислите определитель квадратной матрицы размера .

Литература

1. Ахо А., Хопкрофт Дж., Ульман Д. Структуры данных и алгоритмы. Уч. пособие. — М.: Вильямс, 2000. – 384 с.

2. Головешкин, В.В., Ульянов, М.В. Теория рекурсии для программистов /В.А.Головешкин, М.В. Ульянов. – М.: ФИЗМАТЛИТ, 2006. – 296 с.

3. Есаян, А. Р. Рекурсия в информатике: Учеб. пособие для студентов пед. вузов: Ч. 1: Корзина разнообразных задач. / А.Р. Есаян. – Тула: Изд-во ТГПУ им. Л. Н. Толстого, 2000. – 90 с.

4. Есаян, А. Р. Рекурсия в информатике: Учеб. пособие для студентов пед. вузов: Ч. 2: Матрицы... / А.Р. Есаян. – Тула: Изд-во ТГПУ им. Л. Н. Толстого, 2000. – 95 с.

5. Подбельский, В.В. Программирование на языке Си: учеб. пособие / В.В. Подбельский, С.С. Фомин. – М.: Финансы и статистика, 2004. – 600 с.

6. Подбельский, В.В. Язык Си++: учеб. пособие / В.В. Подбельский. – М.: Финансы и статистика, 2005. – 560 с.

Дата добавления: 2014-01-04