Домашние задания, весна 2015, 244 группа

В табличке:

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

Студенты 244 группы

Условия задач:

Домашнее задание 1. 13.02.2015

1. Реализовать программу подсчета факториала
2. Реализовать программу подсчета i-го числа Фибоначчи

Домашнее задание 2. 20.02.2015

1. Реализовать функцию обращения списка. Функция должна работать за линейное время (подсказка: конкатенация — это плохо)
2. Реализовать функцию, которая формирует список из n последовательных степений двойки (n — аргумент функции)
3. Реализовать функцию, которая вычисляет сумму цифр данного числа
4. Реализовать функцию, которая выдает первую позицию вхождения заданного числа в список
5. Реализовать функцию, проверяющую, является ли строка палиндромом

Домашнее задание 3. 27.02.2015

1. Записать следующую функцию в point-free стиле: func x l = map (\y -> y*x) l. В комментариях показать все промежуточные шаги преобразований.
2. Реализовать функцию, генерирующую бесконечный список, содержащий все целые положительные числа, состоящие только из цифр 1, 7 и 9 (числа должны идти в порядке возрастания). Например, первые 10 чисел в этом списке должны быть [1,7,9,11,17,19,71,77,79,91]. Функция должна быть реализована с помощью "завязывания в узел".
3. Вывести первую позицию в списке, на которой сумма двух соседних элементов максимальна. Например, для [1, 5, 6, 2] функция должно вернуть значение 2.
4. Посчитать высоту дерева, а также минимальное расстояние в дереве от корня до листьев.
5. Реализовать функцию, которая по произвольной строке проверяет корректность скобочной последовательности в этой строке.
6. [необязательная] Записать следующую функцию в point-free стиле: func f g l = filter f (map g l)

Домашнее задание 4. 06.03.2015

1. Реализовать функцию поиска по некоторому условию в двоичном дереве. Условие передается в качестве параметра.
2. Реализовать функцию свертки для бинарного дерева.
3. Реализовать три варианта функции, подсчитывающей количество четных чисел в списке (с использованием стандартных функций map, filter, foldr). Использование рекурсии не допускается.
4. Проверить, что все элемента списка различны
5. Написать программу, которая в диалоговом режиме позволяет осуществлять следующие операции:
   0 - exit
   1 - add value to sorted list
   2 - remove value from list
   3 - print list
   Все операции должны сохранять сортированность. Начинаем с пустого списка.

Домашнее задание 5. 13.03.2015

1. Реализовать функцию, которая по заданному числу n выводит все его разложения на положительные слагаемые (с точностью до порядка разложения)
2. Проверить, что все элементы списка удовлетворяют некоторому условию (условие передается как параметр)
3. Опишите функцию, которая для данного числа n возвращает список из всех строк длины n, состояших из чисел 1,2,3. Например, при n=2 функция должна вернуть список [[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3], ]
4. С помощью оператора >>= опишите функцию, которая для данного числа n создает список из всех попарных произведений чисел от 1 до n. ( Т.е. что-то такое: [1*1, 1*2, 1*3, …, 1*n, 2*1, 2*2, …, n*n] - всего n*n элементов)
5. Используя монадичесие функции, опишите фунцию, которая ищет в списке первый элемент, больший своих соседей (предыдущего и следующего)
6. Дано выражение, содержащее переменную, константы, арифметические операции. Посчитать производную этого выражения по этой переменной, провести в полученном выражении для производной возможные упрощения (например, 1*x = x). Подходящий тип данных разработать самостоятельно

Домашнее задание 6. 27.03.2015

1. Для двоичного дерева, элементы которого – символы, реализовать две функции: одна по дереву строит его представление в виде строки, а вторая функция по этой строке восстанавливает исходное дерево. Дерево должно храниться в следующем формате: Empty кодируется буквой 'e', Node x left right кодируется так: сначала буква 'n', потом символ x, потом подряд без разделителей представления для left и right
2. Описать тип, позволяющий хранить информацию о многочленах с одной переменной, и реализовать для него сложение, умножение и show
3. Реализовать тип данных BinarySearchTree и соответствующие функции для работы с ним: добавление, удаление, поиск, размер (число элементов), высота
4. Для типа Graph, разбиравшегося на паре, реализовать алгоритм Дейкстры поиска кратчайшего пути. Поиск пути должен производиться с использованием экземпляров класса типов Monad или MonadPlus

Домашнее задание 7. 13.04.2015

1. Написать программу-телефонный справочник. Она должна уметь хранить имена и номера телефонов, в интерактивном режиме осуществлять следующие операции:
   0 - выйти
   1 - добавить запись (имя и телефон)
   2 - найти телефон по имени
   3 - найти имя по телефону
   4 - сохранить текущие данные в файл
   5 - считать данные из файла
   Формат представления данных в файле придумать самостоятельно. Все возникающие исключительные ситуации должны обрабатываться корректно (монада Error или Cont).
2. Реализовать функцию, которая заменяет значение в каждом узле дерева на случайное целое число
3. Описать тип данных HashTable и реализовать основные функции для работы с ним: добавление, удаление, поиск в таблице (монада State).
4. Реализовать map и filter в виде функций в CPS-стиле (монада Cont).

Доклады:

• Модульное тестирование
• GUI