2015-05-10
702
Тема: Функция - шаблон. Перегрузка операторов. Перегрузка функций. Рекурсивные функции.
Цель.
· получить навыки по разработке и применению функции – шаблона
· получить навыки по использованию нестандартных типов;
· получить практический опыт по разработке рекурсивных функций.
Задание
1. Разработайте функцию сортировки массива и протестируйте ее.
2. Перегрузите функцию сортировки для каждого из указанных в варианте типов элементов.
3. Разработайте функцию шаблон для сортировки элементов произвольного типа.
4. Перегрузите (операцию) операции сравнения, которые используются в алгоритме сортировки для сравнения значений структуры. В сравнении значений типа структура будут использоваться ключи сортировки, которые в структуре определены курсивом.
5. Реализуйте рекурсии.
· Для первого задания на рекурсии разработайте функцию. Опишите рекурсивную зависимость в виде табличной функции. Определите глубину рекурсии.
· Для второй задачи разработайте рекурсивную функцию для обработки списковой структуры согласно варианту. Информационная часть узла – простого типа – целого. Для создания списка может быть разработана простая или рекурсивная функция по желанию (в тех вариантах, где не требуется рекурсивное создание списка).
|
|
|
6. Разработайте программу, демонстрирующую работу всех функций.
Варианты
| Номер | Сортировка | Перегрузка функции для типов | Рекурсия |
| обменная | Int, double, Struct{int x; int y;} | 1. Найти наибольший общий делитель двух целых чисел 2. Создание и вывод линейного однонаправленного списка из n элементов | |
| вставками | Short, float, Struct{double x; int y;} | 1. Найти n-ое число Фибоначчи. 2. В однонаправленном списке из n элементов найти элемент с заданным значением и вернуть на него указатель. | |
| выбора | Char, int, Struct{short x; int y;} | 1. Определить делится ли число на каждую из своих цифр. 2. Не используя связанный стек проверить баланс скобок в арифметическом выражении, которое передано как строка. | |
| шейкер | Char,double, Struct{int x; char y;} | 1. Определить является ли текст – палиндромом. 2. Удалить из связанного однонаправленного списка все элементы, равные заданному. | |
| Улучшенная обменная сортировка | Int, short, Struct{unsigned x; int y;} | 1. Дан массив из n элементов вещественного типа. Вычислить среднее значение всех элементов массива. 2. Создание связанного стека из n элементов. | |
| Вставками с использованием второго массива. | Unsigned long, double, Struct{char x[20]; doble y; } | 1. Сколько квадратов можно отрезать от прямоугольника со сторонами a и в. 2. Удаление связанного стека. | |
| Сортировка вставками | Int, short, Struct{unsigned x; int y; char z} | 1. Найти максимальный элемент в массиве из n элементов. 2. Создание очереди на однонаправленном списке. | |
| Поразрядная сортировка посредством второго массива | Int, long, Struct{float x; double y; } | 1. Перевести число из 10-системы счисления в систему с основанием В(1<В≤10) 2. Удаление очереди, реализованной на однонаправленном списке | |
| Обменная | Double, char, Struct{long x; char y; } | 1. Бинарный поиск элемента в массиве 2. Создание двунаправленного списка. | |
| Шейкер сортировка | Unsigned short, long, Struct{long x; double y; } | 1. Вычислить значение цифрового корня для некоторого целого числа N. 2. Найти в двухнаправленном списке количество четных элементов. | |
| Сортировать по правилу: положительные, отрицательные, нули | Unsigned long, long, Struct{char x; double y; } | 1. Вычислить x1(x2+x3)(x4+x5+x6)....(x46+x47+...+x55). 2. Удаление двунаправленного списка | |
| Сортировка методом подсчета. | Unsignedint, long, Struct{chsr x[5]; double y; } | 1. Сортировка массива по возрастанию 2. Создать новый однонаправленный список из исходного однонаправленного списка, записав его элементы наоборот. | |
| Вставками | Unsigned short,float, Struct{long x; double y; } | 1. Дана последовательность из N чисел Х1,Х2,....,ХN. Вычислить значение выражения: Хn(Хn+Xn-1)(Хn+Xn-1+Xn-2)(Хn+Xn-1+Xn-3)... (Хn+Xn-1+Xn-3+...+X1). Массив не использовать. 2. Удалить из однонаправленного списка нули. | |
| Шейкер сортировка | Unsigned short, unsigned long, Struct{long x; double y; } | 1. Дана строка. Выполнить переворот строки (записать наоборот) на ее же месте в памяти. 2. Определить количество вхождений: положительных, отрицательных, нулевых значений. | |
| Метод Хоара | short, long, float Struct{char x; int y; } | 1. Ханойская башня. 2. Удалить однонаправленный список. | |
| Обменная | Unsigned short, long, Struct{long x; double y; } | 1. Прохождение лабиринта 2. Определить симметрично ли число, цифры которого последовательно записаны в узлах двунаправленного списка |
|
|
|
