(Практические задания) Алгоритмы и структуры данных. Росдистант

Тема 2.2. Решение задач с использованием рекурсивных алгоритмов

Цель работы: изучить основные понятия, связанные с рекурсией и рекурсивными алгоритмами; научится применять их при решении задач.

Формулировка задания № 1

Выполнить задачи с использованием рекурсивных функций, исходя из следующих условий:

1) дано натуральное число n. Необходимо:

1. вывести на экран все его цифры;

2. найти сумму цифр данного числа;

3. записать его в обратном порядке;

2) дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Необходимо:

1. вывести все нечетные числа из этой последовательности, сохраняя их порядок.

Тема 4.1. Хеширование. Основные методы вычисления хеш-функций: метод деления, метод умножения, динамическое хеширование, расширяемое хеширование. Разрешение коллизий

Цель работы: изучить построение функции хеширования и алгоритмов хеширования данных и научиться разрабатывать алгоритмы открытого и закрытого хеширования при решении задач на языке C++ .

Тема 5.1. Алгоритмы сортировки. Анализ алгоритмов

 Цель работы: изучить основные алгоритмы поиска и сортировки; провести сравнительный анализ различных алгоритмов поиска и сортировки.

Формулировка задания № 3

1.               Изучить следующие методы сортировки:

-                  включение;

-                  выбор;

-                  обмен;

-                  Шелла;

-                  Хоара;

-                  пирамидальную.

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

3.               Изучить алгоритмы  поиска:

·                  в неупорядоченном массиве:

-                  линейный;

-                  быстрый линейный;

·                   в упорядоченном массиве:

-                  быстрый;

-                  бинарный;

-                  блочный.

4. Реализовать данные алгоритмы в одном файле в виде отдельных подпрограмм (функций).

5. Проанализировать, на какой итерации при разных алгоритмах поиска было найдено искомое число.

Тема 6.2. Основные алгоритмы на графах: выделение компонент сильной связности в ориентированном графе; кратчайшие пути, остовные деревья

Формулировка задания № 4

1. Реализуйте программу, в которой выполняется алгоритм обхода графа на основе поиска в глубину.

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

3. Используйте обход графа в ширину для определения всех вершин графа, находящихся на фиксированном расстоянии d от данной вершины.

4. Реализуйте программы, в которых выполняются алгоритм Дейкстры и алгоритм Флойда.

5. Реализуйте программу, в которой определяется минимальное остовное дерево графа.