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

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

Файл формата 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 1 0 0 1 x2 1 1 0 0 x3 0 1 1 0 x4 0 0 1 1

Рис. 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 (выборочно)

Код	179	180	191	192	193	194	195	196	197	217	218
Знак	│	┤	┐	└	┴	┬	├	─	┼	┘	┌