Компьютерные науки - 2 2013-2014

МТ-103

1.1
Написать функцию, которая считает количество листьев в бинарном дереве

27.02.14 -- 2
06.03.14 -- 2
13.03.14 -- 1

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

27.02.14 -- 2
06.03.14 -- 2
13.03.14 -- 1

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

27.02.14 -- 2
06.03.14 -- 2
13.03.14 -- 1

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

27.02.14 -- 2
06.03.14 -- 2
13.03.14 -- 1

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

06.03.14 -- 2
13.03.14 -- 2
20.03.14 -- 1

2.2
Написать функцию, которая переводит упорядоченный список в сбалансированное дерево. И наоборот -- дерево в список.

06.03.14 -- 2
13.03.14 -- 2
20.03.14 -- 1

3.1
Huffman coding

Реализуйте функцию, которая принимает список пар "символ — частота, его появления" и возвращает список пар "символ — код". Должно быть реализовано оптимальное префиксное кодирование

13.03.2014 -- 2
20.03.2014 -- 2
27.03.2014 -- 1

4.1
#строки

Найти в строке целые числа и записать их в список.
Например, "qwerty 35 -20 x5 42 lala 0"-> '(35 -20 42 0)

20.03.2014 -- 2
27.03.2014 -- 2
03.04.2014 -- 1

4.2.
#строки

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

20.03.2014 -- 2
27.03.2014 -- 2
03.04.2014 -- 1

4.3
#строки

Напишите функцию, принимающую на вход неотрицательное целое число, не превосходящее10^{9} - 1, и выдающую строку, содержащую запись этого числа на русском языке. Например, 123418 → «сто двадцать три тысячи четыреста восемнадцать».

20.03.2014 -- 2
27.03.2014 -- 2
03.04.2014 -- 1

5.1
#поиск_подстроки_в_строке

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

20.03.2014 -- 2
03.04.2014 -- 2
10.04.2014 -- 1

5.2
#строки

Напишите функцию format2, которая принимает строку-шаблон и список пар для замен. Шаблонные подстроки выглядят следующим образом: %str%, подстрока %% обозначает символ %. Пример: (format2 "Hi, %name%! Wrehe %whose% %%?" (list (cons "whose" "my") (cons "name" "Test")) -> "Hi, Test! Where my %?"

27.03.2014 -- 2
03.04.2014 -- 2
10.04.2014 -- 1

5.3
#строки

Напишите функцию, проверяющую, является ли переданная ей строка корректный числом в римской записи. Например,
(roman-numerals? "XII") -> #t
(roman-numerals? "XIIX") -> #f

27.03.2014 -- 2
03.04.2014 -- 2
10.04.2014 -- 1

6.1
Написать функцию, принимающую строку, в которой записано выражение в постфиксной записи, содержащее однозначные числа и операции +, −, *, и вычисляющую значение этого выражения. (Например, "8 9 + 1 7 − *" -> −102)

03.04.2014 -- 2
10.04.2014 -- 2
17.04.2014 -- 1

6.2
Напишите функцию, которая моделирует игру в пьяницу и определяет, кто выигрывает. В игре участвует 10 карт, имеющих значения от 0 до 9, большая карта побеждает меньшую, карта со значением 0 побеждает карту 9. Игроки вскрывают по одной верхней карте, и тот, чья карта старше, забирает себе обе вскрытые карты, складывая их под низ своей колоды (сначала карту первого игрока, затем карту второго игрока, то есть карта второго игрока оказывается внизу колоды). Оставшийся без карт — проигрывает.
Аргументами являются два списка, первый содержит 5 карт первого игрока, второй — 5 карт второго игрока. Функция должна возвращать пару из слов first или second и количества ходов, сделанных до выигрыша, а если за 1 миллион ходов игра не закончилась, вывести слово "tie". Например, '(1 3 5 7 9) '(2 4 6 8 0) -> ("second" . 5)

03.04.2014 -- 2
10.04.2014 -- 2
17.04.2014 -- 1

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

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

7.3
Дан файл с арабскими числами, нужно в выходной файл записать те же числа в римской записи.

10.04.2014 -- 2
17.04.2014 -- 2
24.04.2014 -- 1

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

17.04.2014 -- 2
24.04.2014 -- 2
08.05.2014 -- 1

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

17.04.2014 -- 2
24.04.2014 -- 2
08.05.2014 -- 1

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

(convex? (list (cons 0 0) (cons 1 0) (cons 0 1))) -> #t
(convex? (list (cons 0 0) (cons 2 3) (cons 1 1) (cons 2 1))) -> #f

24.04.2014 -- 2
08.05.2014 -- 2
15.05.2014 -- 1

9.2
Реализуйте функцию проверки принадлежности точки выпуклому многоугольнику.

(inner-point? (cons 1 1) (list (cons 0 0) (cons 3 0) (cons 0 3))) -> #t
(inner-point? (cons 4 4) (list (cons 0 0) (cons 3 0) (cons 0 3))) -> #f


24.04.2014 -- 2
08.05.2014 -- 2
15.05.2014 -- 1

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

(find-convex-hull (list (cons 0 2) (cons 2 2) (cons 1 0) (cons 3 0) (cons 2 1) (cons 1 2))) -> '((1 . 0) (3 . 0) (2 . 2) (0 . 2))


24.04.2014 -- 2
08.05.2014 -- 2
15.05.2014 -- 1

10.1
Написать функцию, которая вычисляет количество компонент связностей в заданном графе.

08.05.2014 -- 2
15.05.2014 -- 2
22.05.2014 -- 1

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

08.05.2014 -- 2
15.05.2014 -- 2
22.05.2014 -- 1

10.3
Дан граф, проверить является ли он двудольным, и если да, то вернуть его доли.

08.05.2014 -- 2
15.05.2014 -- 2
22.05.2014 -- 1