1. Напечатать слово
это столбик :слово
если пусто? :слово [стоп]
покажи :слово
столбик кпрв :слово
конец
это обратный_столбик :слово
если пусто? :слово [стоп]
обратный_столбик кпрв :слово
покажи :слово
конец
2. (а) Пузырьковая сортировка
;Программа использует 3 текстовых окна. В окне "исходный" находится
;не отсортированная часть списка, в окне "результат" - отсортированная,
;в окне "текущее" - очередной кандидат на звание максимального
;в окне "исходный".
это сортировка
если пусто? исходный [стоп]
исходный, внт
установи "текущее "текст текущая_строка
удали_строку
спуск
результат, внт пиши текущее
сортировка
конец
это спуск
если кт? [стоп]
положим [строка текущая_строка]
если текущее < :строка
[замени_строку текущее
установи "текущее "текст :строка]
кнз
спуск
конец
;Служебные процедуры
это замени_строку :что
удали_строку
пиши :что квх
конец
это текущая_строка
выделяй вкст
положим [строка выделен]
не_выделяй внст
вых :строка
конец
это удали_строку
выделяй кнз сотри_букву не_выделяй
конец
2(б) Быстрая сортировка
это быстрая_сортировка :список
если пусто? :список [вых :список]
положим [голова_хвост голова_хвост прв :список кпрв :список]
вых (пред быстрая_сортировка прв :голова_хвост
прв :список
быстрая_сортировка псл :голова_хвост)
конец
;Датчик голова_хвост получает на вход число (границу) и список чисел,
;он возвращает пару списков. Первый список состоит из элементов входного
;списка, не больших границы, второй - остальные элементы входного списка.
это голова_хвост :граница :список
положим [голова []
хвост []]
перебор [а :список]
[если_иначе :а > :граница
[пусть "хвост внсп :а :хвост]
[пусть "голова внсп :а :голова]]
вых список :голова :хвост
конец
3(а) Двоичный поиск
;Датчик поиск получает на вход дерево и код,
;он возвращает соответствующее значение, если оно есть, иначе - пустое слово.
;Листья дерева пустые, в корне дерева записаны
;код и соответствующее значение, коды в левом дереве меньше кода в корне,
;в правом - больше.
это поиск :дерево :код
если лист? :дерево [выход "]
если :код = код_корня :дерево
[выход значение_корня :дерево]
выход если_иначе :код > код_корня :дерево
[поиск правое_дерево :дерево :код]
[поиск левое_дерево :дерево :код]
конец
;Реализация дерева. Листья - пустые списки, дерево, не являющееся листом
;реализуется как список из 3-х элементов: первый - пара [значение код],
;второй - левое поддерево, третий - правое поддерево.
это лист? :дерево
вых пусто? :дерево
конец
это код_корня :дерево
вых псл прв :дерево
конец
это значение_корня :дерево
вых прв прв :дерево
конец
это правое_дерево :дерево
вых псл :дерево
конец
это левое_дерево :дерево
вых прв кпрв :дерево
конец
;Создание дерева из списка. У нас имеется список пар [значение код],
;упорядоченных по возрастанию кода.
это дерево :список
если пусто? :список [вых []]
положим [голова_хвост голова_хвост :список ;делим список примерно пополам
целое (сколько :список) / 2]
вых (список прв псл :голова_хвост
дерево прв :голова_хвост
дерево кпрв псл :голова_хвост)
конец
;Датчик голова_хвост получает список и число N, он возвращает пару списков:
;первый список содержит первые N элементов исходного списка,
;второй - остальные элементы исходного списка.
это голова_хвост :список :число
положим [голова []
хвост :список]
повтори :число
[пусть "голова вксп прв :хвост :голова
пусть "хвост кпрв :хвост]
вых список :голова :хвост
конец
3(б) Задача о рюкзаке
;Процедура паковка получает число (размер рюкзака) и список имеющихся грузов.
;Она возвращает подсписок грузов, сумма весов которых равна размеру рюкзака
;или слово "невозможно", если такого подсписка нет.
это паковка :рюкзак :набор
если :рюкзак = 0 [вых []]
если или пусто? :набор :рюкзак < 0 [вых "невозможно]
положим [попытка паковка :рюкзак - прв :набор кпрв :набор]
если список? :попытка [вых внсп прв :набор :попытка]
выход паковка :рюкзак кпрв :набор
конец
4(а) Простые множители [2 3 5]
;Мы поддерживаем три очереди: "очередь2", "очередь3" и "очередь5".
;Очередь реализуется как список чисел.
;На очередном шаге мы сравниваем первые элементы всех очередей,
;берем из них минимальный, печатаем его, удаляем из соответствующих очередей и
;ставим в каждую очередь по новому числу.
это очередное_число
положим [текущее мин прв :очередь2
мин прв :очередь3
прв :очередь5]
пиши :текущее
пусть "очередь2 вксп :текущее * 2
если_иначе :текущее = прв :очередь2 [кпрв :очередь2] [:очередь2]
пусть "очередь3 вксп :текущее * 3
если_иначе :текущее = прв :очередь3 [кпрв :очередь3] [:очередь3]
пусть "очередь5 вксп :текущее * 5
если_иначе :текущее = прв :очередь5 [кпрв :очередь5] [:очередь5]
конец
это мин :а :б
выход если_иначе :а < :б [:а][:б]
конец
;начальная установка очередей
это пуск
пусть "очередь2 [2]
пусть "очередь3 [3]
пусть "очередь5 [5]
конец
4(б) Простые множители: произвольный список простых чисел
;Мы используем набор очередей, набор очередей поддерживает
;функцию очередной индекс, сообщающую значение очередного элемента
;в указанной очереди, и команды
;удалить индекс (удаляющую очередной элемент в указанной очереди)
;и добавить индекс значение (ставящую указанное значение в указанную очередь).
;Команда очередное_число получает на вход список индексов.
это очередное_число :список
положим [текущее очередной прв :список]
перебор [номер :список]
[пусть "текущее мин очередной :номер :текущее]
пиши :текущее
перебор [номер :список]
[если :текущее = очередной :номер [удалить :номер]
добавить :номер :текущее * :номер]
конец
;Реализация набора очередей. Каждая очередь - список,
;этот список хранится в переменной с именем "очередьN",
;где N - индекс очереди
это очередной :индекс
выход прв значение слово "очередь :индекс
конец
это удалить :индекс
положим [имя слово "очередь :индекс]
пусть :имя кпрв значение :имя
конец
это добавить :индекс :элемент
положим [имя слово "очередь :индекс]
пусть :имя вксп :элемент значение :имя
конец
;Начальная установка
это пуск :список
перебор [номер :список]
[пусть слово "очередь :номер (список :номер)]
конец
это мин :а :б
выход если_иначе :а < :б [:а][:б]
конец
5. Угадай животное
;Процедура игра получает на вход базу данных. Она возвращает обновленную базу,
;если в процессе игры были получены новые данные, в противном случае процедура
;возвращает пустое слово. Листья обслуживаются процедурой проверь_лист, в прочих
;вершинах мы можем узнать вопрос, который следует задать пользователю,
;а также поддеревья, которые следует использовать при ответе "да"
;и при ответе "нет"
это игра :дерево
если лист? :дерево [выход проверь_лист :дерево]
спроси вопрос :дерево
положим [ветвь ответ
новое_дерево игра если_иначе :ветвь = "да
[да_дерево :дерево]
[нет_дерево :дерево]]
если пусто? :новое_дерево [вых " ]
;если новое дерево непустое, то нам надо заменить
;соответствующую ветвь в нашей базе
выход внсп вопрос :дерево
если_иначе :ветвь = "да
[список :новое_дерево нет_дерево :дерево]
[список да_дерево :дерево :новое_дерево]
конец
;Реализация базы данных. Лист - одноэлементный список, содержащий название
;некоторого животного, прочие вершины - списки из трех элементов:
;первый элемент - текст вопроса, второй - да_поддерево,
;третий - нет_поддерево
это лист? :дерево
выход 1 = сколько :дерево
конец
это да_дерево :дерево
выход элемент 2 :дерево
конец
это нет_дерево :дерево
выход элемент 3 :дерево
конец
это вопрос :дерево
выход прв :дерево
конец
это проверь_лист :лист
положим [животное прв :лист]
спроси (слово "|Я полагаю, что это - | :животное
"|. Правильно?|)
если ответ = "да [сообщи "Ура! выход " ]
спроси [А что же это за животное?]
положим [новое_животное ответ]
спроси (слово "|Введите, пожалуйста, вопрос, чтобы для |
:животное "| ответ был бы "да", а для |
:новое_животное "| - "нет".|)
сообщи "Спасибо!
;мы заменяем лист на соответствующее дерево
выход (список ответ (список :животное)
(список :новое_животное))
конец
6. Реализация стандартных конструкций
;Команда while получает на вход два списка, первый - инструкция
;условия цикла, второй - инструкция тела цикла.
это while :условие :тело
если не делай :условие [стоп]
делай :тело
while :условие :тело
конец