Рекурсия

Лабораторная работа № 1

Динамические структуры данных

Структуры данных:

1. односвязный список;

2. двусвязный список однонаправленный;

3. двусвязный список двунаправленный;

Каждый элемент содержит поля данных из следующего набора:

1.int

2.int *

3.double

4.double *

5.char

6.char *

7.float

8.float *

Над данными могут быть выполнены следующие операции:

1.Добавление элемента в начало.

2.Добавление элемента в конец.

3.Добавление элемента после заданного.

4.Удаление элемента в начале.

5.Удаление элемента в конце.

6.Удаление элемента с определенными данными.

7.Поиск элемента по полю данных.

8.Контроль размера выделенной памяти.

9.Изменение данных в указанном элементе.

10.Удаление элемента после заданного.

11.Выборочная распечатка (K элементов с начала).

12.Выборочная распечатка (K элементов с конца).

13.Выборочная распечатка (все элементы с заданным значением поля).

14.Удаление.

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

Лабораторная работа № 2

Динамические структуры данных

Аналогично лаб. работе № 1. Формулировку задания, перечень структур данных, полей данных и операций над ними см. в лаб. работе № 1. Таблица вариантов заданий приведена ниже.

Структуры данных:

1. кольцевой односвязный список;

2. двусвязный кольцевой список однонаправленный;

3. двусвязный кольцевой список двунаправленный;

Лабораторная работа № 3

Динамические структуры данных

Аналогично лаб. работе № 1. Формулировку задания, перечень структур данных, полей данных и операций над ними см. в лаб. работе № 1. Таблица вариантов заданий приведена ниже.

Структуры данных:

1. стек;

2. очередь;

3. дек.

Лабораторная работа № 4

Рекурсия

В этих задачах нельзя использовать ни циклы, ни массивы, ни строки!

Также могут быть и другие ограничения в каких-то конкретных задачах.

Вариант 1. От 1 до n.

Дано натуральное число n. Выведите все числа от 1 до n.

Например:

Ввод: 5

Вывод: 1 2 3 4 5

Вариант 2. От A до B.

Даны два целых числа A и В. Выведите все числа от A до B включительно, в порядке возрастания, если A < B, или в порядке убывания в противном случае.

Например:

Ввод: 5 1

Вывод: 5 4 3 2 1

Вариант 3. Точная степень двойки.

Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае.

Операцией возведения в степень пользоваться нельзя!

Например:

Ввод: 3 8

Вывод: NO YES

Вариант 4. Сумма цифр числа.

Дано натуральное число N. Вычислите сумму его цифр.

При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется).

Например:

Ввод: 179

Вывод: 17

Вариант 5. Цифры числа справа налево.

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

При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика.

Например:

Ввод: 179

Вывод: 9 7 1

Вариант 6. Цифры числа слева направо.

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

При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика.

Например:

Ввод: 179

Вывод: 1 7 9

Вариант 7. Разворот числа.

Дано число n, десятичная запись которого не содержит нулей. Получите число, записанное теми же цифрами, но в противоположном порядке. При решении этой задачи нельзя использовать циклы, строки, списки, массивы, разрешается только рекурсия и целочисленная арифметика. Метод должен возвращать целое число, являющееся результатом работы программы, выводить число по одной цифре нельзя.

Например:

Ввод: 179

Вывод: 971

Вариант 8. Палиндром.

Дано слово, состоящее только из строчных латинских букв. Проверьте, является ли это слово палиндромом. Выведите YES или NO.

При решении этой задачи нельзя пользоваться циклами.

Например:

Ввод: radar yes

Вывод: YES NO

Вариант 9. Фибоначчи.

Определить функцию для вычисления элементов ряда чисел Фибоначчи, исходя из рекуррентного выражения F(n) = F(n-1) + F(n-2).

Функция принимает индекс числа, возвращает значение числа.

Вариант 10. Степень числа.

Вычислить степень числа, используя рекурсию. В функцию передаётся 2 параметра - число и степень.

Вариант 11. Сумма чисел в диапазоне.

Вычислить сумму чисел в определённом диапазоне. Начало и конец диапазона задаётся параметрами.

Вариант 12. НОД.

Написать рекурсивную функцию нахождения наибольшего общего делителя двух целых чисел.

Вариант 13. Ход конём.

Дана шахматная доска размером 8х8, и шахматный конь. Программа должна запросить у пользователя координаты клетки поля и поставить туда коня. Задача программы найти и вывести путь коня, при котором он обойдет все клетки доски, становясь в каждую клетку только один раз. В программе необходимо использовать рекурсию.

Вариант 14. 8 ферзей.

Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого.

Информацию см. по ссылке:

https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%B2%D0%BE%D1%81%D1%8C%D0%BC%D0%B8_%D1%84%D0%B5%D1%80%D0%B7%D1%8F%D1%85

Вариант 15. Черепашка.

На квадратной доске размером NxN расставлены случайные целые положительные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу (не наискосок) и хочет, чтобы сумма всех чисел, оказавшихся у неё на пути, была максимально возможной. Показать на экране консоли эту сумму. Также, программа должна показать путь следования черепашки.