Study & DevО программировании и не только

Структуры данных и алгоритмы. Практика. Основы рекурсии

Задания к практической работе. Данная работа будет посвящена рекурсии и ее применению.

1. Вам необходимо написать программную реализацию алгоритма ханойских башен. Результатом работы должен быть список операций (текстовых сообщений с пояснением, что, откуда и куда необходимо перемещать) . В качестве исходных данных должно быть число N – количество дисков. Внимание: программная реализация должна быть рекурсивной.

2. На лекционном занятии я пугал вас, что для ханойских башен существует и не рекурсивное решение, но оно достаточно сложное, к счастью, кроме Арсака решение искали и нашли П.Бьюнеман и Л.Леви. Алгоритм последовательно выполняет следующие действия:

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

Попробуйте создать данную программную реализацию.

3. Эта задача развивает предыдущую Вам уже необходимо создать не рекурсивную по реализации, но не ”по духу” программу, которая использовала стек с хранимыми заданиями. Каждый элемент стека должен представлять собой некоторую структуру описывающую задание: сколько дисков откуда и куда необходимо переместить. Результатом работы программы должен также быть журнал (просто как и в предыдущих заданиях выводите на экран комментарии что и куда перемещается).

4. Функция Аккермана определяется для всех неотрицательных целых аргументов M и N следующим образом:

	A (0, N) = N+1;
	A (M , 0) = A (M-1, 1) (в случае M > 0);
	A (M, N) = A ( M –1  , A (M, N-1)) (в случае M, N > 0).

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

5. После того как вы выполнили предыдущее задание давайте подумаем над тем насколько оно хорошо. Прежде всего, следует сказать, что глубина рекурсии примерно равна значению самой функции, которое растет очень быстро. Таким образом, сделанное вами ранее решение не будет работать для больших чисел (у меня лично на A(4, 10) программа исчерпала ресурсы и зависла). Следовательно, нам необходимо найти решение и замену рекурсии. Прежде всего, я рекомендую вам воспользоваться стандартным приемом в виде стека отложенных заданий. Затем для того, чтобы сократить объем вычислений я посоветую вам воспользоваться некоторым журналом, в котором бы записывались результаты вычислений. Так если вы один раз путем “неимоверных усилий” узнали чему равно значение A (3, 2) то если в будущем при вычислении значения A(X,Y) как подзадача станет необходимость найти значение A (3, 2), то вы извлечете из журнала это предвычисленное значение.

6. В предыдущем задании вы выполнили сортировку файла с помощью метода слияния. Сейчас мы пойдем дальше и попробуем комбинировать методы внешней и внутренней сортировки. Предположим, что у нас есть текстовый файл содержащий множество чисел для сортировки. Размер файла согласно правилам многократно превышает размер доступной оперативной памяти. Мы будем действовать так: разобъем файл на несколько фрагментов (их должно быть кратное двум число), так чтобы каждый из блоков гарантированно умещался в оперативной памяти. Для упрощения предполжим что размер файла >= 100000 элементов, а максимальный размер в памяти порядка 1000 элементов. Каждый из этих блоков вам необходимо будет прочитать в память и отсортировать с помощью пирамидной сортировки. Затем для сформированных файлов-блоков следует применить метод слияния, постепенно объединяя два блока в третий результирующий. Покуда мы не дойдем до одного фрагмента.

7. (одновременно требуется найти не рекурсивное решение): Дана матрица размером N*N, в которой заданы соотношения между различными видами валют, например:
Определенные соотношения между валютами неизвестны. Пользователь вводит два названия валюты. Программа находит курс, который их связывает. Если курс непосредственно не задан - он ищется через косвенные отношения.

8. Быстрая сортировка. В методическом пособии приведена программная реализация функции быстрой сортировки в виде рекурсивного алгоритма. Перед Вами стоит задача выполнить ее оптимизацию путем остановки рекурсивного обращения для небольших последовательностей. Там если размер массива (или его фрагмента, подлежащего сортировке) не превышает 5 элементов то мы будем сортировать этот фрагмент с помощью любого из простейших алгоритмов, например методом шейкера. В качестве еще одного шага для оптимизации работы сортировки мы изменим правила выбора медианного элемента. Теперь мы будем брать не просто любой центральный элемент, а возьмем центральный, первый и последний элемент в отрезке и найдем из них средний. И именно относительно этого элемента должна быть выполнена разброска остальных значений массива.

« Структуры данных и алгоритмы. Практика. Усовершенствованные сортировки

Структуры данных и алгоритмы. Практика. Рекурсия и исключения »