Упражнения. 1. Почему рекурсию нельзя рассматривать как универсальный метод решения задач?

Вопросы

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

1. Почему рекурсию нельзя рассматривать как универсальный метод решения задач?

2. Почему опорные схемы решения задач рекурсивными способами не являются жестко привязанными к отдельным классам задач?

3. Каким образом анализ решения обратной задачи может привести к решению поставленной задачи?

4. По каким признакам «находится родственник» в одноименной опорной схеме?

5. Всегда ли отбрасывание условий и переход к подзадаче могут привести к эквивалентной задаче? Обоснуйте ответ примерами.

6. Какие свойства объектов выступают в роли характеристических в соответствующей опорной схеме?

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

2. Найдите сумму факториалов первых n натуральных чисел. Решите двумя способами: через непосредственное вычисление факториалов и с помощью преобразования декомпозиционных отношений. Оцените трудоемкость функции в каждом случае.

3. Для данных натуральных n и m найдите цепную дробь, соответствующую отношению n / m.

4. Вычислите значение функции Аккермана двумя способами: непосредственно из определения и снизив трудоемкость алгоритма. Найдите каждым способом Akkerman(3, 7) и Akkerman(8, 20). Функция Аккермана определяется рекурсивно для неотрицательных целых чисел m и n следующим образом:

5. Первый член последовательности равен натуральному числу, сравнимому с 2 по модулю 3. Каждый следующий член последовательности равен сумме кубов цифр предыдущего члена. Исследуйте последовательности на сходимость для конкретного первого члена.

Литература

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

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

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

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

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

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

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