Рекурсивные методы решения задач (С) - метод. указания к ЛР
.pdf11
Третий шаг
Поменяем элементы A[i] и A[j] местами, после чего увеличим i на 1 и уменьшим j на 1. Продолжим эти действия до тех пор, пока i не окажется больше j.
Теперь применим наш алгоритм рекурсивно к отдельным частям массива A[1]..A[j] и A[i]..A[n]. Процесс рекурсивных вызовов прекращается, если подмассив состоит из одного элемента.
Рассмотрим конкретный пример.
Пусть массив A размера n = 9 имеет вид:
i |
|
|
|
|
|
|
|
j |
2 |
7 |
6 |
9 |
4 |
5 |
8 |
3 |
1 |
Выберем в качестве x средний элемент A[4] = 4 и положим i = 0, j = n-1. Увеличивая i, найдем элемент A[i] >= x (это элемент A[1] = 7) и, уменьшая j, найдем элемент A[j] <= x (это элемент A[8] = 1).
|
i |
|
|
|
|
|
|
j |
2 |
7 |
6 |
9 |
4 |
5 |
8 |
3 |
1 |
Поменяем их местами и передвинем индексы i и j соответственно вперед и назад:
|
|
i |
|
|
|
|
j |
|
2 |
1 |
6 |
9 |
4 |
5 |
8 |
3 |
7 |
Аналогично поменяем местами элементы 6 и 3, затем 9 и 4. В |
||||||||
результате индекс i станет больше индекса j: |
|
|||||||
|
|
|
j |
i |
|
|
|
|
2 |
1 |
3 |
4 |
9 |
5 |
8 |
6 |
7 |
Следует обратить внимание на то, что i может быть больше j на 1 или на 2, а также на то, что опорный элемент в преобразованном массиве может поменять свое место.
Итак, мы разделили массив на две части. Часть элементов с номерами от 0 до i меньше или равна x, а часть элементов с номерами от j до n-1 – больше или равна x. Осталось рекурсивно применить алгоритм быстрой сортировки к обеим частям.
Ниже приводится код алгоритма:
static void QuickSort(int[] A, int low, int high)
{
int i = low; int j = high;
12
int x = A[(low + high) / 2]; do {
while (A[i] < x) i++; while (A[j] > x) j--; if (i <= j)
{
int temp = A[i]; A[i] = A[j]; A[j] = temp; i++; j--;
}
} while (i < j);
if (low < j) QuickSort(A, low, j); if (i < high) QuickSort(A, i, high);
}
В приведенном алгоритме low и high – левая и правая границы сортируемой части массива, (low + high) / 2 – индекс среднего элемента. При вызове функции QuickSort передают указатель на сортируемый массив, крайний левый индекс массива – 0 и крайний правый индекс массива – n-1.
4. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
Для выполнения лабораторной работы необходимо первоначально ознакомиться с теоретической частью. В случае если материала представленного в теоретической части недостаточно для выполнения задания необходимо воспользоваться лекциями и книгами по данной тематике.
Затем требуется написать программу на языке C# выполняющую задачу, представленную в списке заданий.
5.СПИСОК ЗАДАНИЙ
1.Необходимо написать программу вычисления функции:
|
2 |
, |
если n<5; |
(n+4) |
|||
p(n) = |
|
|
|
n!, |
|
|
если n³5, |
где n – заданное натуральное число.
2. Дано натуральное число n. Найти (2·n)! и 2·n!. Необходимо использовать рекурсивную функцию вычисления факториала.
13
3. Даны натуральные числа n, m. Найти наименьший общий делитель (n, m). Использовать рекурсивную функцию вычисления наименьшего общего делителя.
4. Числа Фибоначчи u0, u1, |
u2, … |
|
определяются следующим |
||||
образом: |
|
|
|
|
|
|
|
u |
|
= 0, u |
|
=1; |
|
|
|
f (u) = |
0 |
|
|
1 |
+ u |
|
, n = 2, 3, 4... |
un = u |
n-1 |
n-2 |
|||||
|
|
|
|
|
|||
Необходимо с помощью рекурсивного алгоритма выводить на экран только те члены ряда, которые делятся на 5 без остатка.
5. Даны неотрицательные целые числа n и m. Необходимо вычислить функцию Аккермана:
n + 1, |
если m = 0; |
A(m, n) = A(m −1, 1), |
если m > 0, n = 0; |
A(m −1, A(m, n −1)), |
если m > 0, n > 0; |
6. Необходимо описать рекурсивную функцию Stepen(x, n), вычисляющую степенную функцию (xn), где х – вещественная переменная и n – натуральная переменная. Необходимо величину xn вычислять по формуле:
1, |
|
|
|
если n = 0; |
xn = |
× x |
n-1 |
|
если n ¹ 0; |
|
, |
|||
x |
|
7. Необходимо описать рекурсивную функцию, которая выводит указанное количество членов ряда:
n |
1 |
|
|
F (x) = ∑ |
, |
||
|
|||
x=1 |
2 × x -1 |
||
где x – номер текущего члена ряда; n – количество членов ряда.
8.Необходимо написать рекурсивную функцию, при выполнении которой на экран будет выводиться отрезок натурального ряда чисел.
9.Необходимо написать программу, которая строит треугольник Серпинского.
|
|
|
14 |
|
|
|
|
10. Числа Фибоначчи |
u0, u1, |
u2, |
… определяются следующим |
||||
образом: |
|
|
|
|
|
|
|
u |
|
= 0, u |
|
=1; |
|
|
|
f (u) = |
0 |
= u |
|
1 |
+ u |
|
, n = 2, 3, 4... |
u |
n |
|
|
|
|||
|
|
n−1 |
|
n−2 |
|
||
|
|
|
|
|
|||
Необходимо написать программу вывода ряда Фиббоначи до числа m (число вводится с клавиатуры), где m>1.
11. Необходимо описать рекурсивную функцию, позволяющую вычислить:
F (n) = |
n −1, |
если n > 23; |
F (n +1), если n £ 23, |
||
где n – заданное натуральное число.
12. Числа Фибоначчи второго порядка u0, u1, u2, … определяются следующим образом:
u |
= 0, u |
= 1, u |
|
= 3; |
|
|
||
f (u) = |
0 |
1 |
+ u |
2 |
|
+ u |
|
, n = 3, 4, 5... |
u |
= u |
|
|
|
||||
|
n |
n−1 |
n−2 |
|
n − 3 |
|
||
|
|
|
|
|||||
Необходимо написать программу вычисления un для данного неотрицательного целого n.
13. Пусть дана система:
|
x |
= a; |
|
|
|
|
|
|
|
F (x) = |
x0 |
= q × x |
k -1 |
+ b, k =1, 2,... . |
|
k |
|
|
Необходимо вычислить систему для заданного натурального числа
n.
14. Необходимо найти количество элементов среди первых n+1 элементов последовательности:
|
x |
= a; |
|
|
|
|
|
|
+ b, k =1, 2,... , |
F (x) = |
x0 |
= q × x |
k -1 |
|
|
k |
|
|
которые принадлежат интервалу (с, d). Предполагается, что q ¹ 0. 15. Задана рекуррентная последовательность:
15
x |
|
= c, x |
|
= d; |
|
|
|
|
|
|
|
||||||
F (x) = |
0 |
|
|
|
|
1 |
|
|
+ r × x |
|
|
+ b, k = 2, 3,... |
|||||
x |
k |
= q × x |
k -1 |
k - |
2 |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Необходимо вычислить |
xn (x ³ 0) . Считать r ¹ 0. |
|
|||||||||||||||
16. Числа Фибоначчи |
|
|
u0, |
u1, u2, |
… |
определяются следующим |
|||||||||||
образом: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f (u) = |
u |
|
= 1, u |
|
= 1; |
|
|
|
|
|
|||||||
|
1 |
= u |
|
2 |
|
+ u |
|
, n = 3, 4... |
. |
||||||||
|
|
|
|
u |
n |
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
n−1 |
|
n−2 |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
Необходимо найти номер первого числа Фибоначчи, которое больше h (вводится с клавиатуры).
17. Пусть |
x |
k |
= (-1)k+1 |
× k!, k = 1, 2,... . Необходимо вычислить |
|
|
|
|
данное выражение для заданного натурального k.
18. Необходимо описать рекурсивную функцию, позволяющую вычислить:
F (n) = |
n − 3, |
если n > 7; |
n × F (n +1), |
если n £ 7, |
где n – заданное натуральное число.
19.Необходимо описать рекурсивную функцию MaxElem(A, n) целого типа, которая находит максимальный элемент целочисленного массива A размера n. С помощью этой функции найти наименьшее значение из максимальных элементов массивов A, B.
20.Необходимо создать рекурсивную функцию,
которая строит изображение «спираль», указанное на рисунке.
21.Дано дерево глубины n, каждая вершина (кроме висячих) которого имеет k (не более 10) непосредственных потомков (нумеруют от 1 до k). Корень дерева имеет номер 0. Необходимо вывести на экран все возможные пути, ведущие от корня к листьям. Перебирать пути, начиная с «самого левого» и заканчивая «самым правым» (при этом первыми заменять конечные элементы пути).
22.Дано дерево глубины N, каждая вершина (кроме висячих) которого имеет K (не более 10) непосредственных потомков (нумеруют от 1 до K). Корень дерева имеет номер 0. Необходимо
16
вывести на экран все возможные пути, ведущие от корня к листьям удовлетворяющие следующему условию: никакие соседние элементы пути не нумеруются одной и той же цифрой. Перебирать пути, начиная с «самого левого» и заканчивая «самым правым» (при этом первыми заменять конечные элементы пути).
23. Необходимо описать рекурсивную функцию, которая выводит указанное количество членов ряда:
|
n |
5 |
|
|
F (x) = ∑ |
|
, |
||
|
|
|||
|
x=1 |
x2 + x |
||
где x – номер текущего члена ряда; n – |
количество членов ряда. |
|||
24. Необходимо написать программу вычисления функции: |
||||
|
2, если n<12; |
|||
p(n) = (n+4) |
||||
n!, |
если n³12, |
|||
|
|
|
|
|
где n – заданное натуральное число.
25.Необходимо написать программу, которая обеспечивает рисование снежинки, количество звеньев и ветвей, коэффициент уменьшения каждого звена ветви задаются пользователем. На рисунке изображена снежинка, состоящая из 3 звеньев и 6 ветвей.
26.Напишите программу построения изображения, представленного на рисунке. Глубина рекурсии задается пользователем программы.
27.Необходимо написать программу, которая создает бинарное дерево, состоящее из целых чисел, вводимых с клавиатуры, и находит число, ближайшее к среднему арифметическому минимального и максимального чисел в бинарном дереве. Все числа бинарного дерева (исходного и преобразованного) должны выводится на экран.
28.Необходимо вычислить, используя рекурсию:
X = 1− |
1 |
2 + |
1 |
3 − |
1 |
4 − |
1 |
|
|
, |
|
|
n + ... |
||||||||||
|
|
|
n |
||||||||
2 |
3 |
4 |
|
|
|
|
|||||
17
где знаки под корнями периодически повторяются группами по три: "-", "+", "-". Коэффициент n – задается с клавиатуры.
29. Необходимо вычислить, используя рекурсию:
X = 
1 + 2
1 + 3
1 + 4
1 + ... .
Максимальный коэффициент перед корнем задается пользователем программы с клавиатуры.
30. Необходимо описать рекурсивную функцию, позволяющую вычислить:
F (n) = n − 10, |
если n > 100; |
F (F (n + 4)), |
если n ≤ 100, |
где n – заданное натуральное число. |
|
6.КОНТРОЛЬНЫЕ ВОПРОСЫ
1.Что такое рекурсия?
2.Что такое прямая и косвенная рекурсия?
3.Что такое глубина рекурсии, текущий уровень рекурсии?
4.Перечислите формы рекурсивных подпрограмм. Дайте определение каждой форме.
5.Что называют рекурсивным спуском и возвратом?
6.Когда может произойти рекурсивное зацикливание?
7.Назовите пример некорректного использования рекурсии и объясните, почему данный алгоритм неэффективен.
8.Расскажите алгоритм быстрой сортировки и приведите пример.
9.Расскажите алгоритм ханойские башни.
10.Чем отличаются рекурсивные алгоритмы от итерационных?
7.СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ
Основная
1.Павловская, Т.А. C#. Программирование на языке высокого уровня. – Изд.: Питер, 2009. – 432 с.
2.Эндрю Троелсен. Язык программирования C# 2010 и платформа
.NET 4. – Изд.: Вильямс, 2011. – 1392 с.
3.Кристиан Нейгел, Билл Ивьен, Джей Глинн, Карли Уотсон, Морган Скиннер. C# 4.0 и платформа .NET 4 для профессионалов.
– Изд.: Питер, 2011. – 1440 с.
18
Дополнительная
4.Головешкин, В.А., Ульянов, М.В. Теория рекурсии для программистов. – Изд.: ФИЗМАТЛИТ, 2006. – 296 с.
5.Марченков, С.С. Рекурсивные функции. – Изд.: ФИЗМАТЛИТ, 2007. –64 с.
6.Джесс Либерти. Программирование на С#. – Изд.: КноРус, 2003. – 688с.
7.Харви Дейтел. C# в подлиннике. Наиболее полное руководство. – Изд.: БХВ-Петербург, 2006. – 1056 с.
19
Языки программирования. Рекурсивные методы решения задач: методические указания к выполнению лабораторной работы для студентов очной формы обучения специальностей 090303 – «Информационная безопасность автоматизированных систем», 090900
– « Информационная безопасность». – Брянск: БГТУ, 2013. – 19 с.
ЮРИЙ АЛЕКСЕЕВИЧ ЛЕОНОВ ЕВГЕНИЙ АЛЕКСЕЕВИЧ ЛЕОНОВ
Научный редактор: Ю.М. Казаков Редактор издательства: Л.И. Афонина Компьютерный набор: Ю.А. Леонов
|
|
Темплан 2013г., п. |
|
|
|
|
|
Подписано в печать |
Формат 60х84 1/16. Бумага офсетная. |
||
Офсетная печать. |
|
|
|
Усл. печ. л. 1,1 Уч. – |
изд. л. 1,1 Тираж 20 экз. Заказ |
Бесплатно |
|
Издательство брянского государственного технического университета, 241035, Брянск, бульвар 50-летия Октября, 7, БГТУ. 58-82-49 Лаборатория оперативной полиграфии БГТУ, ул. Харьковская, 9