УП.02 - Задачи для практической работы

Задания необходимо выполнить на любом доступном языке программирования а результат необходимо опубликовать в публичном репозитории на Github. Репозиторий должен называться algorithms_practicum, включать файл README.md, содержащий инструкцию для запуска и проверки кода.

1. Задачи по вычислению чисел Фибоначчи

Во всех задачах на вычисления чисел Фибоначчи для простоты первое число Фибоначчи принимаем за $1$ , а $0$ считаем нулевым числом последовательности, таким образом порядковый номер $n$ числа Фибоначчи будет соответствовать индексу массива содержащего числовой ряд.

1.1. Вычисление n-го числа Фибоначчи с использованием рекурсивного алгоритма

Дано целое число $1 ≤ n ≤ 24$ , необходимо написать функцию fib(n) для вычисления $n$ -го числа Фибоначчи с использованием рекурсии. Функция fib(n) должна вызывать сама себя в теле функции для вычисления соответствующих $(n-1)$ и $(n-2)$ .

В результате выполнения, функция должна вывести на экран вычисленное число Фибоначчи, например fib(6) должна вывести число 8, а fib(0) — соответственно 0.

Необходимо замерить время выполнения алгоритма с точностью до миллисекунды любым доступным способом для пяти произвольных $n$ , и на основании произведенных замеров сделать предположение о сложности алгоритма.

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

1.2. Вычисление n-го числа Фибоначчи с использованием цикла

Дано целое число $1 ≤ n ≤ 32$ , необходимо написать функцию fib(n) для вычисления $n$ -го числа Фибоначчи с использованием цикла. Функция fib(n) должна производить расчет от $1$ до $n$ , на каждой последующей итерации используя значение числа(чисел), необходимых для расчета, полученных на предыдущей итерации.

В результате выполнения, функция должна вывести на экран вычисленное число Фибоначчи, например fib(3) должна вывести число 2, а fib(7) — соответственно 13.

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

1.3. Вычисление n-го числа Фибоначчи с записью числового ряда в массив

Дано целое число $1 ≤ n ≤ 40$ , необходимо написать функцию fib(n) для вычисления $n$ -го числа Фибоначчи. Функция fib(n) должна в процессе выполнения записывать вычисленные значения в массив таким образом что индекс записанного числа в массиве должен соответствовать порядковому номеру числа Фибоначчи. При этом уже вычисленные значения должны браться из массива, а вновь вычисляемые должны записываться в массив только в случае если они еще не были вычислены.

В результате выполнения, функция должна вывести на экран массив, содержащий все вычисленные числа Фибоначчи вплоть до заданного, включая его например fib(8) должна вывести массив: [0, 1, 1, 2, 3, 5, 8, 13, 21].

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

1.4. Вычисление n-го числа Фибоначчи при помощи формулы Бине

Дано целое число $1 ≤ n ≤ 64$ , необходимо написать функцию fib(n) для вычисления $n$ -го числа Фибоначчи. Функция fib(n) должна производить вычисление по формуле Бине.

F(n) = \frac{(\frac{1+\sqrt{5}}{2})^{n} -(\frac{1-\sqrt{5}}{2})^{n}}{\sqrt{5}}

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

В результате выполнения, функция должна вывести на экран вычисленное число Фибоначчи, например fib(32) должна вывести число 2178309.

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

1.5. Определение четности n-го большого числа Фибоначчи

Дано целое число $1 ≤ n ≤ 10^{6}$ , необходимо написать функцию fib_eo(n) для определения четности $n$ -го числа Фибоначчи.

Как мы помним, числа Фибоначчи растут очень быстро, поэтому при их вычислении нужно быть аккуратным с переполнением. В данной задаче, впрочем, этой проблемы можно избежать, поскольку нас интересует только последняя цифра числа Фибоначчи: если $0 ≤ a, b ≤ 9$ — последние цифры чисел $F_n$ и $F_{n+1}$ соответственно, то $(a+b) \bmod{10}$ — последняя цифра числа $F_{n+2}$ .

В результате выполнения, функция должна вывести на экран четное ли число или нет (even или odd соответственно), например fib_eo(841645) должна вывести odd, т.к. последняя цифра данного числа — 5.

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

2. Задачи по алгоритмам Хаффмана

2.1. Кодирование строки по алгоритму Хаффмана

По данной строке, состоящей из строчных букв латинского алфавита:

Errare humanum est.

постройте оптимальный беспрефиксный код на основании классического алгоритма кодирования Хаффмана.

В результате выполнения, функция huffman_encode() должна вывести на экран в первой строке — количество уникальных букв, встречающихся в строке и размер получившейся закодированной строки в битах. В следующих строках запишите коды символов в формате "'symbol': code". В последней строке выведите саму закодированную строку.

Пример вывода для данного текста:

12 67
' ': 000
'.': 1011
'E': 0110
'a': 1110
'e': 1111
'h': 0111
'm': 010
'n': 1000
'r': 110
's': 1001
't': 1010
'u': 001
0110110110111011011110000111001010111010000010100001111100110101011

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

2.2. Декодирование строки по алгоритму Хаффмана

Восстановите строку по её коду и беспрефиксному коду символов.

12 60
' ': 1011
'.': 1110
'D': 1000
'c': 000
'd': 001
'e': 1001
'i': 010
'm': 1100
'n': 1010
'o': 1111
's': 011
'u': 1101
100011110001001101000111111011001010011000010110011010111110

В первой строке входного файла заданы два целых числа через пробел: первое число — количество различных букв встречающихся в строке, второе число — размер получившейся закодированной строки, соответственно. В следующих строках записаны коды символов в формате "'symbol': code". Символы могут быть перечислены в любом порядке. Каждый из этих символов встречается в строке хотя бы один раз. В последней строке записана закодированная строка. Заданный код таков, что закодированная строка имеет минимальный возможный размер.

В результате выполнения, функция huffman_decode() должна вывести на экран строку, которая была закодирована изначально.

Пример вывода для данного текста:

Docendo discimus.

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