Теория алгоритмов

2020-2021 учебный год

Практические занятия

Практика 12
Разработка рекурсивных алгоритмов 

По учебнику выполнить примеры:

• Перейти. Глава 2. Массивы. Файлы: текстовые и бинарные. Строки. Матрицы. Указатели. Рекурсия. Структуры.
• Перейти. Графическая библиотека TXLib.
• kpolyakov.spb.ru. Язык C++.
• Перейти. Рекурсия, с. 63.
• kpolyakov.spb.ru. Материалы для изучения языка программирования C++ к новому учебнику «Информатика. Базовый и углублённый уровни» для 10-11 классов.
• Перейти. Рекурсия, с. 59-71.
• kpolyakov.spb.ru. Материалы для изучения рограммирования на языках C и C++ на основе учебника «Информатика. Углублённый уровень» для 10-11 классов.
• Перейти. Рекурсия, с. 28-34.

1. Вычислить факториал с помощью 
1) рекурсивной функции, с. 52;
2) рекурсивной процедуры, с. 52;
3) итеративной функции, с. 53.

2. Вычислить числа Фибоначчи с помощью 
1) рекурсивной функции, с. 53;
2) итеративной функции, с. 54.

3. Определить, сколько раз встречается заданное слово в предложении 
с помощью рекурсивной функции, с. 54.

4. Изобразить рекурсивную фигуру из окружностей 
с помощью рекурсивной функции и графической библиотеки TXLib, 
с. 55.

5. Изобразить фрактал в виде пифагорова дерева 
с помощью рекурсивной функции и графической библиотеки TXLib, 
с. 56. 

6. Получить всевозможные сочетания чисел, с. 56-57.

7. Получить всевозможные перестановки чисел, с. 57-58.

8. Получить всевозможные различные способы представления 
целого числа в виде суммы натуральных чисел, с. 58-59. 

9. Применить для сортировки одномерного массива алгоритм 
быстрой сортировки Ч. Хоара, с. 59-61.

10. Запишите рекурсивную процедуру вывода двоичного представления 
целого числа, с. 63-65.
http://kpolyakov.spb.ru/download/9-4_cpp.pdf

11. Составьте рекурсивную функцию для решения задачи 
о ханойских башнях, с. 60-63.
http://kpolyakov.spb.ru/download/ch10-8bu_cpp.pdf

12. Найти сумму цифр числа с помощью рекурсивной функции, с. 64.
http://kpolyakov.spb.ru/download/ch10-8bu_cpp.pdf

13. Реализовать алгоритм Евклида поиска наибольшего 
общего делителя двух чисел с помощью рекурсивной функции, с. 64-66.
http://kpolyakov.spb.ru/download/ch10-8bu_cpp.pdf

Разработка рекурсивных алгоритмов. 
Простые типы данных: переменные и константы.