Алгоритмический анализ - 2 2014-2015

МТ-103

1.1
Пусть вектор n-мерного пространства задается списком из n элементов

Реализуйте функцию, которая проверяет коллинеарность двух векторов.

1.2
Пусть вектор n-мерного пространства задается списком из n элементов

Реализуйте функцию, нормирующую заданный на входе вектор n-мерного пространства.

1.3
Пусть вектор n-мерного пространства задается списком из n элементов.
Реализуйте функцию, которая по заданному списку точек n-мерного пространства находит ближайшую к началу координат.

1.4
Пусть задан набор точек (список пар их координат) на плоскости.

Реализуйте функцию, которая построит список из четырех элементов, которые представляют собой список точек соответствующей четверти (включаю границы). Если точка лежит на границе двух четвертей, она должна появиться сразу в двух списках. Если точка является началом координат, то она должна появиться во всех четырёх списках.

1.5
Реализуйте функцию, которая вычисляет сумму векторов n-мерного пространства, заданных в списке из списков своих координат.

2.1
Напишите функцию, которая подсчитывает количество листьев бинарного дерева.

(count-leaf (list->tree '()))
0
(count-leaf (list->tree (list 1 0 2 -1 0.4 3 1.5)))
4
(count-leaf (list->tree (list 0 1 2 3)))
1

2.2
Узел бинарного дерева должен являться списком из трех элементов:
(<данные>, <левое поддерево>, <правое поддерево>),
Проверьте, что заданная на входе структура данных представляет собой корректную запись бинарного дерева.

2.3
Напишите функцию, которая возвращает #t или #f в зависимости от того, выполняется ли следующее свойство: любой узел заданного на входе бинарного дерева, не являющийся листом, имеет ровно два потомка. Другими словами, в дереве нет узлов ровно с одним потомком.

2.4
Напишите функцию, которая по заданному на входе непустому дереву вычисляет расстояние от корня до ближайшего листа.

2.5
Задана последовательность имен каталогов в виде списка строк. Известно, что эти каталоги пользователь посещал последовательно, переходя на один уровень вверх или один уровень вниз. Гарантируется, что имена каталогов, уровни которых отличаются на два, не могут быть одинаковыми. Определить, если это возможно, полный путь финального положения пользователя.

(path '("A" "B" "A" "C" "C:\\" "D" "M" "X" "M" "K"))
"C:\\D\\M\\K"
(path '("A" "B" "A" "C" "D"))
#f

3.1
Напишите функцию, которая по заданному бинарному дереву вернет хотя бы один элемент, который делится на своего ближайшего потомка, либо значение #f, если такой элемент не найдется.

3.2
Напишите функцию, которая по заданному на входе дереву строит симметричное исходному (все левые потомки должны стать правыми и наоборот).

3.3
Напишите функцию, которая вычисляет количество узлов заданного на входе дерева, являющихся левыми потомками.

3.4
Напишите функцию, которая по заданному на входе дереву возвращает минимальное из значений его вершин, являющихся листьями. Если дерево пусто функция должна вернуть значение +inf.0

3.5
Напишите функцию, которая по заданному на входе дереву вернет список списков, где на i-ом месте стоит список всех значений i-го этажа, а внутри каждого списка значения расположены в порядке обхода. В случае, если исходное дерево пусто, функция должна вернуть #f.

> (levels-tree empty-tree)
'()
> (levels-tree (insert-into-tree empty-tree 1))
'((1))
> (levels-tree (list->tree '(2 1 -1 1.5 3 2.5 4)))
'((2) (1 3) (-1 1.5 2.5 4))

4.1
Задана таблица бинарных кодов в виде списка пар: (символ . его код в виде списка нулей и единиц). Напишите функцию, которая определяет, обеспечивает ли эта кодовая таблица однозначное декодирование любого текста, то есть обладает ли она уникальностью префиксов или суффиксов.

(list (cons #\a (list 0)) (cons #\b (list 0 1)) (cons #\c (list 0 1 1)))
#t

(list (cons #\a (list 0)) (cons #\b (list 1 0)) (cons #\c (list 1 0 1)))
#f

10.03.2015 -- 2
17.03.2015 -- 1

4.2
Напишите функцию, которая по заданной кодовой таблице, обеспечивающей однозначное декодирование, возвращает минимальное кодовое слов для кодирования нового ещё незакодированного символа.

4.3
Пусть задана кодовая таблица. Напишите функцию, которая по этой таблице возвращает символ, для которого может быть уменьшена длина кодового слова, или #f, если такого символа нет. Свойство однозначности декодирования у таблицы должно сохраниться.

4.4
Дано дерево кодов Хаффмана в следующем формате: промежуточные узлы — это пары из левого и правого поддерева, а листья — пары вида ('leaf . символ). Определить хоть какое-нибудь частотное распределение, для которого могло быть получено это дерево. Результат должен быть списком пар (символ . частота)

5.1
Напишите аналог функции map для дерева, то есть все элементы дерева должны обрабатываться функцией, заданной первым параметром.

17.03.2015 -- 2
24.03.2015 -- 1

5.2
Напишите аналог функции foldl для дерева при обходе дерева в инфиксном порядке.


17.03.2015 -- 2
24.03.2015 -- 1

5.3
В заданном бинарном дереве ликвидировать (при их наличии) цепочки, то есть удалить все промежуточные узлы, которые имеют только одного потомка.


17.03.2015 -- 2
24.03.2015 -- 1

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


17.03.2015 -- 2
24.03.2015 -- 1

6.1
Реализовать сортировку Хоара на итерации (без использования функции filter). Разбиение списка на части (подготовка к рекурсивному вызову) должно производиться за один проход.

24.03.2015 -- 2
31.03.2015 -- 1

6.2
Есть список из натуральных чисел. Упорядочить этот список по убыванию произведения цифр числа. Использовать сортировку включением.

24.03.2015 -- 2
31.03.2015 -- 1

6.3
Задан список из слов (строк). Упорядочить слова по первой букве, а слова с одинаковой первой буквой должны оказаться упорядочены по длине. Разрешается использовать стандартную функцию sort.


24.03.2015 -- 2
31.03.2015 -- 1

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

24.03.2015 -- 2
31.03.2015 -- 1

6.5
Напишите функцию split, которая принимает два строковых параметра — str и delim, и возвращает список подстрок строки str, ограниченных символами из delim.

24.03.2015
31.03.2015

7.1
Напишите функцию, проверяющую матрицу, заданную на входе, на верхнетреугольность (верхнетреугольной называется квадратная матрица, все элементы которой, расположенные ниже главной диагонали, равны нулю).

31.03.2015 -- 2
07.04.2015 -- 1

7.2
Напишите функцию, которая умножает матрицу на число.

7.3
Напишите функцию, которая вычеркивает из матрицы строку и столбец с заданными номерами.

7.4
Напишите функцию, которая генерирует квадратную матрицу размера (n+1) x (n+1) по следующему правилу:
0 1 ... n-1 n
1 2 ... n 0
2 3 ... 0 1
... ... ... ...
n 0 ... n-2 n-1

8.1
Найти хотя бы один символ, входящий во все слова строки, или указать, что такого нет.

07.04.2015 -- 2
14.04.2015 -- 1

8.2
Каждая строка входного файла имеет формат:

натуральное_число+натуральное_число

Например, 123+4567 или 12+3. Вычислить значение каждой суммы. Выбрать из них те, цифры которых идут в порядке возрастания. Выбранные числа выдать в файл в порядке убывания.

07.04.2015 -- 2
14.04.2015 -- 1

8.3
Задаются имена двух файлов, при этом первый файл существует. Записать во второй файл все строки первого, включающие слово define.

07.04.2015 -- 2
14.04.2015 -- 1

8.4
Назовем форматом следующую функцию. Она принимает имя входного файла, выходного файла и некоторое количество строковых параметров. Во входном файле содержится текст, в котором присутствуют фрагменты вида %<число>%. Каждый такой фрагмент начинается и заканчивается в рамках одной строки. Требуется вывести в выходной файл текст, в котором эти фрагменты заменены содержимым соответствующий строковых параметров. При этом процент задается двойным символом процента и при обработке заменяется на один символ.
Например,

"Здравствуй, %1%! Меня зовут %2%. Даю 10%%." "Коля" "Петя" -> "Здравствуй, Коля! Меня зовут Петя. Даю 10%."

9.1
Напишите функцию, которая по заданному во входном файле матрицей смежности графу возвращает количество изолированных вершин этого графа.

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

Списки смежных вершин для графа на рисунке goo.gl/DEtoJy выглядят так:

6
2 1 2
2 0 4
2 0 4
0
2 1 2
0

Здесь в первой строке записано количество вершин графа. Каждая последующая строка (с номером i) начинается с количества вершин, смежных вершине с номером i. А далее через пробел указываются номера этих вершин.

14.04.2015 -- 2
14.04.2015 -- 1

9.3
Напишите функцию, которая по заданному во входном файле списками смежных вершин графу в выходной файл выдает построчно список его рёбер.

14.04.2015 -- 2
21.04.2015 -- 1

9.4
Напишите функцию, которая по заданной на входе матрице смежности графа строит список его рёбер.

9.5
Напишите функцию, которая по заданному во входном файле списками смежных вершин графу в выходной файл записывает матрицу смежности этого же графа.

14.04.2015 -- 2
21.04.2015 -- 1

10.1
Напишите функцию, которая по заданному во входном файле матрицей смежности связному неориентированному обыкновенному графу проверяет, является ли этот граф эйлеровым.

Эйлеровым называется граф, содержащий эйлеров цикл. Эйлеров цикл — это цикл в графе, проходящий по всем его ребрам, причем в точности один раз.

Теорема Эйлера. Для того, чтобы граф был эйлеровым, необходимо и достаточно, чтобы
* все вершины имели четную степень;
* все компоненты связности кроме, может быть одной, не содержали ребер.

22.04.2015 -- 2
29.04.2015 -- 1

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

22.04 -- 2
29.04 -- 1

10.3
Во входном файле имеется текст, некоторые слова в котором записаны с переносами. Переносом мы считаем ситуацию, кода после символа «-» до конца строки могут встречаться только пробелы.
С помощью конечного автомата удалите переносы из текста.
Слово, в котором удаляется перенос, должно оказаться в той же строке, где оно начинается.
Пробелы могут встречаться в любом количестве в началах и концах строк.
Гарантируется, что слова, пишущиеся через дефис, по этим дефисам не переносятся.
Гарантируется также, что символ переноса не отделяется от буквы пробелом.

Пример входа.
␣␣␣␣␣что-ни-␣␣␣␣
␣␣␣будь␣␣
␣␣␣␣␣пе-␣␣
ре-
␣␣носы␣-␣это круто!
␣␣
Выход для этого примера.
␣␣␣␣␣что-нибудь
␣␣
␣␣␣␣␣переносы
␣-␣это круто!
␣␣

22.04 -- 2
29.04 -- 1

10.4
Во входном файле содержится кроссворд, записанный моноширинным шрифтом. Напишите функцию, которая формирует выходной файл по следующему принципу. В первой строке выходного файла записано «По горизонтали». В последующих строках должны следовать слова, записанные в этом кроссворде по горизонтали (по одному в каждой строке). Пропустив одну строку в выходном файле, запишите туда словосочетание «По вертикали». Во всех последующих строках должны следовать слова, записанные в этом кроссворде по вертикали.
Например, для следующего входного файла:
к о т о м к а ␣
и ␣ и ␣ ␣ о ␣ ␣
т о р ␣ ␣ т и к

выходной файл должен иметь вид:
По горизонтали
котомка
тор
тик
По вертикали
кит
тир
кот

22.04 -- 2
29.04 -- 1

11.1
Граф задан в файле списками смежных вершин. В первой строке записано N — количество вершин графа, каждая из N следующих строк имеет формат:
k-степень очередной вершины, далее номера смежных вершин через пробел.
Требуется в другой файл в таком же формате записать дополнение исходного графа. Дополнением графа называется граф с тем же числом вершин, у которого имеются только те рёбра, которых не было в исходном.

28.04 -- 2
05.05 -- 1

11.2
Граф задан списками смежных вершин как в предыдущей задаче. Сформировать списки вершин, соответствующие разным компонентам связности. Например, если в графе три компоненты связности, то результатом должен быть список из трех списков соответствующих вершин.

28.04 -- 2
05.05 -- 1

11.3
Связанный граф задан списками смежных вершин как в предыдущей задаче. Найти центр графа. Центром графа называется вершина, максимальное расстояние от которой до других вершин является наименьшим. Если в графе несколько вершин являются центрами графа, достаточно выдать любую из них.

28.04 -- 2
05.05 -- 1

11.4
В файле задана информация о лабиринте. Первая строка содержит два натуральных числа — размеры лабиринта. Затем задана указанного размера матрица из нулей и единиц. Ноль означает, что это свободная клетка, единица — что там стена. Затем в файле указаны две пары чисел: номера строки и столбца — начальное и конечное положение робота. Требуется выдать кратчайший путь между указанными позициями в виде списка пар чисел (строка . столбец) или #f, если путь отсутствует.

28.04 -- 2
05.05 -- 1

12.1
Напишите программу, которая по заданному n будет генерировать координаты вершин какого-либо правильного n–угольника

05.05 -- 2
12.05 -- 1

12.2
Напишите программу, которая будет проводить триангуляцию выпуклого многоугольника, заданного координатами своих вершин в порядке обхода. Триангуляцией многоугольника называется совокупность треугольников, имеющих вершины в вершинах многоугольника, пересекающихся, быть может, лишь по границе и дающих в объединении исходный многоугольник.

05.05 -- 2
12.05 -- 1

12.3
Для заданного роя точек постройте параллелотопную оболочку. Параллелотопной оболочкой множества точек в n–мерном пространстве называется минимальный n–мерный прямоугольный параллелограмм с рёбрами, параллельными осям координат (то есть, минимальный параллелотоп), содержащий все точки этого роя.
Например, в случае n = 2 (на плоскости) нужно построить минимальный прямоугольник со сторонами, параллельными осям координат, содержащий все точки.

05.05 -- 2
12.05 -- 1

12.4
На входе даны два многоугольника (перечислены координаты вершин этих многоугольников в порядке их обхода; однако, порядок обхода для разных многоугольников может быть выбран разный).
Можно ли преобразовать один многоугольник в другой, используя только параллельный перенос и пропорциональное масштабирование?

05.05 -- 2
12.05 -- 1

12.5
Найти центр описанной окружности треугольника, заданного на входе координатами своих вершин.

05.05 -- 2
12.05 -- 1

13.1
Напишите функцию, которая в заданном на входе списке из чисел осуществляет перестановку так, что сумма наибольших общих делителей пар последовательно идущих элементов списка окажется максимальной.

12.05 -- 2
19.05 -- 1

13.2
Напишите функцию, вычисляющую определитель квадратной матрицы, заданной списком списков элементов своих строк.

12.05 -- 2
19.05 -- 1

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

12.05 -- 2
19.05 -- 1

13.4
Напишите функцию, которая проверяет, можно ли добавить один элемент в список так, чтобы он стал симметричным.

12.05 -- 2
19.05 -- 1

13.5
На входе задана строка, содержащая символьную запись арифметического выражения без скобок с целыми числами и четырьмя знаками арифметических операций: + − ∗ /. Напишите функцию, которая по этой строке вычислит значение этого выражения.

12.05 -- 2
19.05 -- 1

14.1
Решите задачу «K–ичные числа»:
http://acm.timus.ru/problem.aspx?space=1#=1009

14.2
Даны две последовательности X = (x1, x2, . . . , xn) и Y = (y1, y2, . . . , ym). Необходимо найти одну из общих подпоследовательностей Z этих двух последовательностей наибольшей длинны.

14.3
Решите задачу «Сумма цифр»:
http://acm.timus.ru/problem.aspx?space=1#=1658