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

МТ-103

1.1*
Написать функцию, которая принимает список пар, чей первый элемент может принимать значения 0, 1 или 2, а второй элемент может быть любым числом, и выводит на консоль сначала элементы, соответствующие 0, затем 1, затем 2, при этом сохраняя изначальный порядок. (Например, (list (cons 1 2) (cons 2 1) (cons 0 3) (cons 1 1) ) -> 0 3 ; 1 2 ; 1 1; 2 1

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

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

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

2.2
Задано четыре слова из латинских букв.
Можно ли из них составить кроссворд, где каждое слово пересекается с двумя другими?
Например,
  f  o
qwerty
 d  f
 s  g
sdfgfgh
 f  g
Если составить кроссворд нельзя, функция должна возвращать false, если можно — то список четвёрок вида (слово1, слово2, номер-буквы-в-первом-слове, номер-буквы-во-втором-слове2).
Пример 1.("plumb", "ololo", "clam", "umum") -> ((ololo, plumb, 2,2), (ololo, clam, 4, 2), (umum, plumb, 2, 4), (umum, clam, 4, 4))
Пример 2. ("ab", "cd", "ef", "gh") -> #f

2.3
В матрице из символов подсчитать количество слов, имеющихся в ней по горизонтали или вертикали.
Разделитель слов - пробел. Слово - сочетание непробельных символов. Количество символов в слове должно быть больше одного.
Например,
((qw c )
(x  s)
(adhf)
(z )) -> 4

3.1*
Задан файл с текстом на английском языке. Записать всё из него в другой файл, преобразовав символы в верхний регистр.

3.2
Подсчитать количество слов в файле. Перенос в тексте не используется.

3.3
Задано два файла. Выписать в третий файл общие слова без повторений.

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

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

4.3
Напишите функцию, получающую на вход имя файла и неотрицательное целое число n. Функция должна выдать строки треугольника Паскаля с нулевой по n-ю. Строка с номером k содержит k+1 натуральное число; крайние — единицы, каждое внутреннее есть сумма двух чисел предыдущей сроки: стоящего над ним и левее него. Нулевая строка состоит только из единицы. Первые несколько строк треугольника Паскаля:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

4.4
Напишите функцию, которая переводит число из арабской записи в римскую. Например: 1668 -- MDCLXVIII, 46 -- XLVI. (Число не может быть больше 3999)

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

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

5.3
Напишите функцию, которая переводит число из римской записи в арабскую. Например: MDCLXVIII -- 1668. (Гарантируется, что число имеет правильную римскую запись)

6.3
Написать функцию, которая принимает строку и ищет в ней самую встречаемую пару слов, стоящих в строке рядом. При этом не различается регистр букв в словах.
Например (f "A abc qwer, zxcv abc a") -> (list "a" "abc")

6.2
Написать функцию, которая в списке слов ищет такую пару слов слов, у которых суффикс одного слова совпадает с префиксом другого и длина этого префикса максимальна среди всех таких пар. Пример: (f "qwegdf" "asdf" "zxcv" "vcxzqwe") -> ("qwegdf" . "vcxzqwe"). (Суффикс-префикс "qwe", его длина 3)

6.1*
Написать функцию split, принимающую строку и строку, состоящую из разделителей. Пример: (split "this!is;string" "!;") -> '("this" "is" "string")

7.1*
Написать функцию, принимающую неотрицательное целое число n и возвращающую все двоичные последовательности длины n.

7.2
Написать функцию, принимающую неотрицательное целое число n и возвращающую все двоичные последовательности длины n. !!! ВАЖНО !!! Использовать open-output-string и fprintf

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

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

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

8.3
Написать задачу 8.1 без использования рекурсивных функций.

9.1
Написать функцию, которая принимает список символов и возвращает все возможные сочетания без повторений длины N. Реализовать два варианта: с рекурсией и без.

9.2
Написать функцию, которая принимает список символов и возвращает все возможные сочетания с повторениями длины N. Реализовать два варианта: с рекурсией и без.

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

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

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

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

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

МТ-104

МТ-101

МТ-102