Вспомогательные материалы

Графические файлы формата PPM (Portable PixMap)

Файл формата PPM имеет простую структуру. Первая строка файла всегда содержит «магическое число» P6. Во второй строке содержится размер картинки по горизонтали и вертикали в пикселях (целые числа в текстовом формате). Третья строка практически всегда содержит число 255. Начиная с четвертой строки в файле, кодируется цвет каждого пикселя. Под кодировку цвета отводится три байта (R-, G- и B-байты). Рассмотрим пример (кодировка DOS):

P6
3 4
255
я++я++я++я++я++я++я++я++я++я++я++я++

Это изображение представляет собой небольшой ярко красный прямоугольник размером 3 на 4 пикселя. Все пиксели одного цвета – «я++» ({239,43,43} – интенсивности красной, зеленой и синей компонент цвета в цифровом выражении). Первые три строки файла заканчиваются символами конца строки (ASCII-код 10), а не парой «возврат каретки, конец строки», как это принято на платформе Windows. Для создания файла из описанного примера в среде интерпретатора Пролога можно, например, воспользоваться следующим кодом:

make_test_ppm:-

create(H,’test.ppm’),

concat([’P6’,10,’3 4’,10,’255’,10], S),

write(H, S),

write(H,’я++я++я++я++я++я++я++я++я++я++я++я++’),

close(H).

Кроссворды

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

В качестве удобного способа организации простейшей тестовой базы может служить следующий код, записывающий в радел базы данных существительные русского языка в виде списков из ASCII-кодов:

:- eraseall(verb).

:- recordz(verb,”казак”,_).

:- recordz(verb,”роман”,_).

:- recordz(verb,”бокал”,_).

:- recordz(verb,”короб”,_).

:- recordz(verb,”замок”,_).

:- recordz(verb,”канал”,_).

…

:- recordz(verb,”комок”,_).

:- recordz(verb,”кокон”,_).

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

A	B	C	D	E
P		R		T
F	G	H	I	J
Q		S		U
K	L	M	N	O

Рис. 1. Простейший пример кроссворда

Для представления такого шаблона можно воспользоваться множеством различных вариантов. В качестве одного из возможных решений можно использовать такой код:

form(

[A,B,C,D,E]*[F,G,H,I,J]*[K,L,M,N,O]+

[A,P,F,Q,K]*[C,R,H,S,M]*[E,T,J,U,O]).

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

Матрица инцидентности графа

Для графа G = (X, R), где X – множество вершин, а R – множество ребер, матрица инцидентности – это прямоугольная матрица M={m_ij}. m_ij = 1 тогда и только тогда, когда вершина x_i инцидентна ребру r_j и m_ij = 0 в противном случае. Пример простейшего графа и его матрицы представлен на рис. 2.

r1 r2 r3 r4 x1 x2 x3 x4

Рис. 2. Пример графа и его матрицы инцидентности

Модульная арифметика (арифметика вычетов)

Если оперировать только с целыми числами и приводить результаты по модулю M, то такая арифметическая система называется одномодульной арифметикой вычетов. Целое число M > 1 при этом называется модулем арифметической системы. Для трех основных арифметических операций в этой арифметике (сложения, умножения и вычитания) можно записать простые утверждения:

ü X есть сумма чисел A и B в арифметике вычетов по модулю M, если X = (A + B) mod M;

ü X есть произведение чисел A и B в арифметике вычетов по модулю M, если X = (A * B) mod M;

ü X есть разность чисел A и B в арифметике вычетов по модулю M, если X = (A + M – B mod M) mod M.

Для осуществления деления в арифметике вычетов приходится прибегать к более громодкой процедуре. В обычной арифметике можно записать такое равенство A/B = A*B^-1. Таким образом, для того чтобы поделить A на B, достаточно умножить A на обратное к B число. В арифметике вычетов именно так и поступают. X есть результат деления числа A на число B в арифметике вычетов по модулю M, если X = (A * B^-1 mod M) mod M. Для расчета обратного элемента (числа) к B по модулю M, т.е. B^-1 mod M, используется расширенный алгоритм Евклида. При произвольных значениях модуля для некоторых чисел обратный элемент может и не существовать. Если в качестве модуля арифметики брать простое целое число, то для любого числа в такой арифметике существует обратный элемент.

Расширенный алгоритм Евклида (как и обычный) предназначен для нахождения наибольшего общего делителя двух целых чисел a,b – НОД(a,b) = d. Однако, кроме решения этой «основной задачи» он позволяет находить целые числа x,y, являющиеся решениями уравнения ax + by = d. Псевдокод для этого алгоритма выглядит так.

НА ВХОДЕ: два неотрицательных числа a и b

НА ВЫХОДЕ: d=НОД(a,b) и целые x,y: ax + by = d.

1. Если b=0 положить d:=a, x:=1, y:=0 и возвратить (d,x,y)

2. Положить x₁:=0, x₂:=1, y₁:=1, y₂:=0

3. Пока b>0

3.1 q:=[a/b], r:=a-qb, x:=x₂-qx₁, y:=y₂-qy₁

3.2 a:=b, b:=r, x₂:=x₁, x₁:=x, y₂:=y₁, y₁:=y

4. Положить d:=a, x:=x₂, y:=y₂ и возвратить (d,x,y)

Если с помощью расширенного алгоритма Евклида требуется найти обратное по модулю n число для числа а, то достаточно в расширенном алгоритме Евклида положить b = n. При a < n и если n – простое число, алгоритм возвращает d = 1, а обратное к a целое число – либо x (если x>0), либо n + x (в противном случае).

Символы псевдографики

ASCII-коды символов в кодировке DOS, необходимость использования которых возникает при выполнении ряда задач этого пособия, представлены в таблице.

Таблица 1

ASCII-коды символов псевдографики в кодировке DOS (выборочно)

Код
Знак	│	┤	┐	└	┴	┬	├	─	┼	┘	┌

СОДЕРЖАНИЕ

Предисловие. 3

Списки и строки. 4

Бинарные деревья. 15

Произвольные структуры (деревья) 24

Файлы и разделы базы данных. 33

Литература. 40

Приложение А. Подготовка к работе. 41

Приложение Б. Предикаты Arity/Prolog32. 42

Приложение В. Вспомогательные материалы.. 70

Редактор З.И. Сныкова
Компьютерная верстка Е.Л. Борисенко
ЛР № 020713 от 27.04.1998
Подписано к печати	Формат бумаги 60×84/16
Печать ризограф.	Бумага МВ	Печ. Л. 5,0
Заказ №	Тираж 50 экз.	Цена договорная
Отдел множительной техники ИАТЭ
249035, г. Обнинск, Студгородок, 1