Для самостоятельного решения
Можно предложить следующие задачи на применение функционалов:
1) Напишите определение функционала F-ALL, выясняющего, все ли элементы множества Set удовлетворяют заданному предикату Pred.
(defun f-all (Pred Set ) . . . )
2) Напишите определение функционала F-ex, выясняющего, найдется ли в множестве Set элемент, удовлетворяющий заданному предикату Pred.
(defun f-ex (Pred Set ) . . . )
3) Пусть программа представляет собой набор списков, содержащих имя команды и произвольное число операндов. Имя расположено первым в списке. Напишите определение функционала, удобного для выдачи списка операндов, встречающихся в программе, а также для выдачи отдельных интегральных характеристик, таких как суммарное число всех операндов, максимальное число операндов в команде и т.п.
4) Напишите универсальный фильтр, позволяющий из произвольного списка выделять при необходимости атомы, числа, строки или списки, начинающиеся с заданного атома, и т.д.
5) Пусть клетки доски типа шахматной пронумерованы по горизонтали символами, а по вертикали числами. И то, и другое перечислено в отдельных списках по порядку. Напишите функцию перечисления координат всех клеток доски, соответствующей размерам списков.
6) При анализе труднодоступных данных требуется всю потенциально полезную информацию выяснять сразу, <в одно касание>. Напишите модель такого стиля работы на примере покомпонетной обработки двух списков чисел. Роль полезной информации могут играть значения любых бинарных операций, таких как +, *, -, /, max, min и т.п.
7) Пусть программа представляет собой набор списков, содержащих имя команды и не более двух операндов. Имя расположено в списке первым. Напишите определение функционала, удобного для выдачи по мере необходимости перечня команд, или перечня первых операндов, или вторых операндов и т.п.
Подготовьте определения вспомогательных функций на все эти случаи.
8) Список содержит ежедневные сведения о количестве осадков, выпавших за весьма длительный период. Напишите функционал, позволяющий по этому списку оперативно выяснять различные сведения, наподобие:
- суммарный объем осадков;
- максимальное количество осадков в день;
- минимальное количество осадков в день;
- максимальная разница в количестве осадков в соседние дни.
9) Задача повышенной сложности (с решением).
Лексикон ***)
Условие задачи: Группа специалистов договорилась подготовить лексикон программирования для электронной публикации. Было решено, что надо добиться <правильности> определения понятий программирования, а именно не допускать цепочек понятий прямо или косвенно определяемых через себя. Кроме того, следует обеспечить полноту комплекта определений, т.е. всякое включенное в лексикон понятие должно иметь определение.
Напишите программу, помогающую по ходу разработки лексикона отслеживать его <правильность> и полноту.
Входные данные:
(( имя_понятия объяснение ) ... ) - двухуровневый список, в котором имя_понятия - атом, обозначающий определяемое понятие, объяснение - последовательность строк и/или атомов, строки не требуют определения, а атомы должны получить определения в процессе разработки, но, возможно, еще не все слова удалось объяснить.
Выходные данные:
Словарь правилен или Есть неправильные цепочки имя_понятия1 ... имя_понятияN |___________________|______ начала неправильных цепочек и/или Есть неопределенные понятия имя_понятия1 ... имя понятияN |___________________|_______ имена неопределенных понятий (слова перечисляются в порядке включения в словарь.)
Пример ввода:
(( автокод язык_программирования <используется для создания> операционная_система <и> транслятор) ( язык_программирования <задается множеством правил для написания> программ) ( операционная_система <комплекс> программа <управляющих решением задач на имеющемся оборудовании>) ( транслятор <компилирующая> программа) ( программа <описание> алгоритм <решения задачи на соответствующем языке>) ( алгоритм <точно определенное правило действий>) )
Уточнения:
- Может ли объяснение быть пустым? - Да.
- Может ли быть много объяснений для одного имени? - Да.
- Могут ли быть идентичные объяснения? - Да.
- Может ли одно слово входить в объяснение неоднократно? - Да.
- Предполагается ли одновременная диагностика и циклов, и неопределенностей? - Да.
- При выводе результата неопределенные имена надо вывести все.
Пример теста:
(( а-к яп <используется для создания> ос <и> сп) ( яп <задается множеством правил для написания> пр) ( ос <комплекс> пр <управляющих решением задач на имеющемся оборудовании>) ( сп <компилирующая> пр) ( пр <описание> алг <решения задачи на соответствующем языке>) ( алг <точно определенное правило действий>) )
'(( а-к яп ос сп) ( яп пр) ( ос пр) ( сп пр) ( пр алг) ( алг ))
;;=== Лексикон****) - проверка корректности == ;; Предполагается, что из теста уже ;; отфильтрованы строки, ;; т.к. они не влияют на логику анализа корректности
(defun names (vac) (mapcar 'car vac)) ;; определяемые имена - список левых частей
(defun words (vac) (cond ;; используемые имена - список правых частей ((null vac) NIL) (T (union (cdar vac) (words (cdr vac)))) )) (defun undef (vac) (set-difference (words vac) (names vac))) ;; неопределенные имена - список висячих ссылок (defun circle (v) ;; проверка термина на явный цикл (cond ((null (cdr v)) NIL)
((member (car v) (cdr v)) (car v)) (T NIL) ))
(defun circ-v (vac) (mapcar 'circle vac)) ;; список явных циклов с NIL-ами на нециклах
(defun maska (arg xxx) (cond (xxx NIL) (T arg))) ;; выбор, если NIL
(defun del-cir (al xl) (delete NIL (mapcar 'maska al xl))) ;; стирание непомеченных определений, т.е. циклов
(defun skobki (ll) (cond((null ll)nil) ((null (car ll)) (skobki (cdr ll)) ) ((atom (car ll))(cons(car ll) (skobki(cdr ll))) ) (T (union (car ll) (skobki (cdr ll)) )) )) ;; раскрыть скобки на один уровень
(defun onestp (vc)(setq vac vc) ;; однократная постановка всего словаря
(mapcar '(lambda (x) (cons (car x) (skobki (sublis vac (cdr x))) )) vc ))
(defun clean-s (line xl) (cond ((null xl) line) (T (clean-s (delete (car xl) line)(cdr xl) )) ))
(defun clean-u (vc xl) (setq wl xl)
;; стирание заданного списка слов => висячих ссылок
(mapcar '(lambda (xx) (setq x xx) (cons (car x) (clean-s (cdr x) wl) )) vc ))
(defun cvr (vac)(delete NIL (cvr-d (del-cir vac (circ-v vac)) (delete NIL(union (circ-v vac) NIL))))) ;; список всех циклов полного словаря - без ;; висячих ссылок
(defun cvr-d (vc ccl) (prog (vac cl cv dcv cleanv) (setq vac (clean-u vc ccl)) (setq cl ccl)
;; пополнение списка циклов со второго шага LAB (cond ((words vac) (setq cv (circ-v vac)) (setq dcv (delete NIL cv)) (setq cleanv (clean-u (del-cir vac cv) dcv)) (setq vac (onestp cleanv)) (setq cl (append dcv cl)) (go lab) )) (return cl) ))
(defun vac-ok (vac) (prog (vc ul cl) ;; проверка словаря на корректность (setq vc vac) (setq ul (undef vc)) (setq cl (cvr (clean-u vac ul)))
(cond ((eq ul cl) (return(print 'OK)) ) ; = лишь если пусты <> корректность словаря ( CL (print (list 'CIRCLES cl))) )
(cond (UL (return (print (list 'UNDEFINED ul))) ) (T (return (list 'circle cl))) ) ))
*) Символ ";" - начало комментария.
**) На Lisp 1.5 это определение выглядит изящнее, не требует встроенной функции funcall, при отладке примеров на Clisp-е [7]:
(defun map-el (fn xl) (cond (xl (cons (fn (car xl) ) ; применяем первый аргумент как функцию ; к первому элементу второго аргумента (map-el fn (cdr xl) ) ) ) ) )
***) Эта задача была предложена участникам Открытой Всесибирской студеческой олимпиады в 2000 году и оказалась в числе никем не решенных. Многих смутило отсутствие численных ограничений на допустимые данные. При решении задач на Паскале и Си такие ограничения обычно подсказывают выбор структур данных, поэтому отсутствие ограничений было воспринято как риск. Немногочисленные попытки решить задачу привели к отбраковке на минимальных тестах, вызванной тем, что программы не допускали пустой словарь или словарь, выглядящий как перечень терминов без определений. (Впрочем, возможно, это ошибка разработчика тестов. Видимо, первыми должны располагаться тесты на наиболее типичные, естественные случаи.)
****) Решение этой задачи может быть сведено к задаче <Проверка ацикличности графа>.
