LAB 9 (рекурсия) (Задания)

ЛАБОРАТОРНАЯ РАБОТА №9.

ТЕМА: Организация рекурсивных процессов.

ЦЕЛЬ: Получение навыков по созданию рекурсивных подпрограмм

Темы теоретической подготовки.

Теория рекурсивных алгоритмов. Виды рекурсий. Понятие глубины рекурсии. Графы рекурсивных вызовов. Delphi-обработка исключительных ситуаций(класс EXEPTION).

Контрольные вопросы по теории

1. Что такое рекурсия?

2. Что необходимо предусмотреть в рекурсивной подпрограмме?

3. В каком случае может произойти переполнение стека памяти и почему?

4. Приведите граф рекурсивных вызовов для перевода десятичного числа 12 в двоичную систему счисления.

Задание к лабораторной работе.

1. Разработать программу согласно варианта, предусмотрев в ней реализацию алгоритма в виде :а) процедуры б) функции в) рекурсивной процедуры б)рекурсивной функции.

2. Предусмотрите в программе вызовы на выполнение отдельно функции и процедуры.

3. Включите в проект обработку исключительной ситуации по переполнению стека. Обеспечьте тестирование такой ситуации с помощью одной из рекурсивных подпрограмм.

4. Выполните трассировку программы с просмотром выполнения рекурсии в подпрограммах.

5. Рассчитайте глубину рекурсии.

6. Приведите схему выполнения рекурсивных вызовов для одной из подпрограмм.

ВАРИАНТЫ

1. Дано целое число. Вывести его в последовательности цифр: от старшей к младшей.

2. Дана строка. Выполнить переворот строки(записать наоборот) на ее же месте в памяти.

3. Напишите функцию для возведения числа в целую степень.

4. Дан прямоугольник со сторонами А и В (натуральные числа). Сколько максимально можно отсечь от прямоугольника квадратов, если каждый раз отсекать максимальный.

5. Ханойские башни. Имеется 3 стержня А, В, С. На стержень А нанизано N дисков радиуса 1, 2, 3 ... N таким образом, что диск радиуса i является i-ым сверху. Требуется поместить все диски на стержень В, сохраняя их порядок расположения(диск с большим радиусом находится ниже).За один раз можно переместить только один диск с любого стержня на любой другой стержень. При этом должно выполняться следующее условие: на каждом стержне ни в какой момент времени никакой диск не может находиться выше диска с меньшим радиусом.(отобразите на форме процесс перемещения)

6. Из листа клетчатой бумаги размером M*N клеток вырезали образующие некоторые фигуры клетки. Линии разреза совпадают с границами клеток. Определите количество вырезанных фигур.(Подсказка: лист бумаги-матрица, заполненная значением 0, в которой вырезанные фигуры помечены значением 1).

7. Дана последовательность из N чисел Х1,Х2,....,ХN. Вычислить значение выражения: Хn(Хn+Xn-1)(Хn+Xn-1+Xn-2)(Хn+Xn-1+Xn-3)... (Хn+Xn-1+Xn-3+...+X1). Массив не использовать.

8. Найти НОД двух целых чисел.

9. Найти все числа, не превосходящие заданного N и делящиеся на каждую из своих цифр.

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

11. В одномерном числовом массиве из N элементов найти отрезок максимальной длины, в котором первое число равно последнему, второе предпоследнему и т.д. Вывести номер первого элемента этого отрезка и количество элементов в нем.

12. Для заданной матрицы найти минимум среди сумм модулей элементов диагоналей параллельных главной.

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

14. Найти количество сложений для вычисления N-ого числа Фибоначчи.

15. Вычислить x1(x2+x3)(x4+x5+x6)....(x46+x47+...+x55).

16. Вычислить значение цифрового корня для некоторого N.Алгоритм нахождения цифрового корня для числа N=9999999.

1. Найти сумму цифр числа: 9+9+9+9+9+9+9=63

2. Найти сумму цифр получившегося числа: 6+3=9

3. Если сумма – однозначное число то корень найден.

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

2. Вычислить N-ый член геометрической прогрессии и сумму N первых членов, начиная с i по K-ый.

3. Является ли фрагмент строки с i по k – ый символ полиндромом.

4. Определить является ли массив из N элментов упорядоченным по невозростанию.

1. Дано натуральное число N >13. Вывести все пары простых чисел, разность между которыми равна 4, а сами числа меньше N.