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

Практическое задание № 1

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

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

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

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

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

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

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

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

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

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

Практическое задание № 2

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

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

Практическое задание № 3

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

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

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

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

- включение;

- выбор;

- обмен;

- Шелла;

- Хоара;

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

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

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

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

- линейный;

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

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

- быстрый;

- бинарный;

- блочный.

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

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

Практическое задание № 4

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

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

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

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

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

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

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