Повторящиеся вычисления, списки

Рекурсия РЕКУРСИЯ - механизм, который позволяет перевызывать на сог-ласование с базой данных предикат, который в качестве предика-та-подцели ссылается на самого себя. Обычная стратегия решения задач состоит в том, чтобы разбитьисходную задачу на более мелкие подзадачи, решить их, а затемобъединить подзадачи с тем, чтобы получить решение исходной зада-чи. Может потребоваться разбиение подзадачи на еще более мелкие ирешение их по частям. Если подзадача есть уменьшенный вариант исходной задачи, тоспособ ее разбиения и решения идентичен примененному в исходнойзадаче. Такой процесс называется рекурсией. Для того чтобы описанныйметод решения был результативным, он должен в конце концов приво-дить к задаче, решаемой непосредственно. Решить ее позволяют ут-верждения, называемые граничными условиями. - 15 - Механизм рекурсии - один из наиболее традиционных механизмовпрограммирования. +------------------------------------------------------+ ¦ Турбо-Пролог - это последовательный язык. ¦ ¦ Несмотря на то, что он вышел из математической ¦ ¦ логики, он последовательно сопоставляет с базой ¦ ¦ данных предикаты (или выражения для одного ¦ ¦ предиката) в порядке их нахождения в теле ¦ ¦ программы. ¦ +------------------------------------------------------+ Для увеличения производительности программ и экономии стекаследует применять остаточную рекурсию (или итерационное определе-ние предиката). Пример 1: Вычисление факториала методом рекурсии.PREDICATES factorial(INTEGER,INTEGER) factorial_it(INTEGER,INTEGER,INTEGER)CLAUSES factorial(1,1):-!. factorial(N,X):- M = N-1, factorial(M,Y), X = Y*N. СПИСКИ - это структура данных Турбо-Пролога для формированиясоставных объектов. Список состоит из элементов (термов), заклю-ченных в квадратные скобки и разделенных запятыми. Список целыхчисел представляется как [1,2,3,9,-3,-2]. Он принадлежит к опре-деляемому домену ilist, объявляемому как: domains ilist = integer * Если элементы в списке смешанного типа, например, список,содержащий как символы, так и целые числа, он должен быть выраженсимволами в соответствующем описании: domains element = c(char); i(integer) list = element *представляет, например, такой список [i(12), i(34), i(-567), c('x'), c('y'), c('z'), i(987)].

Пример. Напишем предикат, позволяющий получать элемент списка по его номеру так же, как по номеру можно получать элемент массива в императивных языках программирования. Предикат будет трехаргументный: первый аргумент — исходный список, второй аргумент — номер элемента и третий — элемент списка, указанного в качестве первого аргумента предиката, имеющий номер, указанный в качестве второго аргумента.

Решение проведем рекурсией по номеру элемента. В качестве базиса возьмем очевидный факт, что первым элементом списка является его голова. Шаг рекурсии позволит нам сделать предположение, что N-й элемент списка является (N–1)-м элементом хвоста. Данному определению будет соответствовать следующее предложение:

n_element([X|_],1,X).n_element([_|L],N,Y):– N1=N–1, n_element(L,N1,Y).Работа со строками ( STRING HANDLING ) frontchar(String,FrontChar,RestString) (string,char,string) - (i,o,o) (i,i,o) (i,o,i) (i,i,i) (o,i,i) Разделяет строку String на две части: первый символFrontChar и оставшаяся часть строки RestString. fronttoken(String,Token,RestString) (string,string,string) - (i,o,o) (i,i,o) (i,o,i)(i,i,i)(o,i,i) Разделяет строку String на лексему Token и остатокRestString (выполняется только для строк, состоящих из латинскихбукв). Лексема - это последовательность символов, определяемаякак: а) имя в соответствии с синтаксисом Турбо-Пролога, б) строчное представление числа, в) отдельный символ (может быть пустым - пробел). frontstr(Lenght,InpString,StartString,RestString) (integer,string,string,string) - (i,i,o,o) Отрезает от заданной строки InpString строку StartString из символов, количество которых определяется параметром Lenght. Вы-дает также оставшуюся часть строки RestString. concat(String1,String2,String3) (string,string,string) - (i,i,o) (i,o,i) (o,i,i) (i,i,i) Конкатенация двух строк: String3 = String1 + String2. str_len(String,Length) (string,integer) - (i,i) (i,o) (o,i) Определяет длину строки. isname(StringParam) (string) - (i) Истинен, если StringParam представляет собой имя, доступноев Турбо-Прологе. Выполняется только для последовательности симво-лов, состоящей из латинских букв. format(OutputVariable,FormatString,Variable|Constant*) - (o,i,i) Выводит по формату FormatString список выводаVariable|Constant* в строковую переменную OutputVariable.

Средства графики

Графический интерфейс - BGI-графика. (BGI GRAPHIC) Инициализация. detectgraph(Graphdriver,Graphmode) (integer,integer) - (o,o) Тестирование аппаратуры видеоадаптера и автоматический выборподходящего драйвера и графического режима. Возвращается номерграфического драйвера Graphdriver и номер графического режимаGraphmode.Графические драйверы: DETECT = 0 - автоустановка CGA = 1 MCGA = 2 EGA = 3 EGA64 = 4 EGAMONO = 5 RESERVED = 6 HERCMONO = 7 ATT400 = 8 VGA = 9 PC3270 = 10 С1, С2, С3, С4 - фиксированные палитры, наборы цветов которых оп-ределяются конкретным адаптором и программно не изменяются. initgraph(Graphdriver,Graphmode,NewDriver,NewMode,Pathtodriver) (integer,integer,integer,integer,string) - (i,i,o,o,i) Инициализация графического режима с драйвером Graphdriver, врежиме Graphmode и директорией (путь) Pathtodriver, где находитсяBGI-файл драйвера. При Graphdriver=DETECT значения NewDriver,NewMode устанавливаются по умолчанию (автоматический выбор). - 42 -setgraphbufsize(BufSize) (integer) - (i) Установка желаемого размера BufSize внутреннего графическогобуфера (по умолчанию он выбирается в 4К) getdrivername(DriverName) (string) - (o) Запрос имени DriverName текущего графического драйвера. getmaxmode(MaxMode) (integer) - (o) Запрос максимального значения MaxMode номера графическогорежима. getgraphmode(GraphMode) (integer) - (o) Запрос текущего значения GraphMode номера графического режи-ма для активного драйвера. getmodename(DriverMode,ModeName) (integer,string) - (i,o) Для активного графического драйвера запрос имени ModeNameграфического режима по его номеру DriverMode. getmoderange(Graphdriver,Lomode,Himode) (integer,integer,integer) - (i,o,o) Запрос минимального Lomode и максимального Himode допустимыхзначений номеров графического режима для графического драйвераGraphdriver. setgraphmode(Mode) (integer) - (i) Переход в указанный графический режим Mode. restorecrtmode Временный переход в текстовый режим. graphdefaults Восстановление характеристик графической системы, установ-ленных при ее инициализации. closegraph Прекращение работы графической системы. - 43 - Работа с растром точек. setvisualpage(Pagenum) (integer) - (i) Отображение на экране страницы видеопамяти. Pagenum - номеротображаемой страницы (нумерация страниц начинается с нуля). setactivepage(Page) (integer) - (i) Установка активной страницы видеопамяти. Переотображениястраницы не происходит, но весь последующий графический выводнаправляется на эту страницу. getmaxx(X) (integer) - (o)getmaxy(Y) (integer) - (o) Определение максимальных значений координат точек растра,допустимых в данном графическом режиме. setviewport(Left,Top,Right,Bottom,Clip) (integer,integer,integer,integer,integer) - (i,i,i,i,i) Динамическое управление размером и расположением графическо-го окна. Left,Top,Right,Bottom - координаты левой, верхней, пра-вой и нижней границ окна в системе координат страницы, Clip - оп-ределяет установку режима отсечения: если Clip не нулевой, то лю-бой графический вывод обрезается на границах заданного окна. getviewsettings(Left,Top,Right,Bottom,Clip) (integer,integer,integer,integer,integer) - (o,o,o,o,o) Запрос текущей установки графического окна. moveto(X,Y) (integer,integer) - (i,i) Перемещение текущей графической позиции в указанные коорди-наты графического окна. moverel(Dx,Dy) (integer,integer) - (i,i) Перемещение текущей графической позиции на вектор (Dx,Dy). getx(X) (integer) - (o)gety(Y) (integer) - (o) Запрос координат текущей графической позиции. - 44 - clearviewport Очистка графического окна на активной странице. cleardevice Очистка всей активной страницы. getaspectratio(Xasp,Yasp) (integer,integer) - (o,o) Определение коэффициента пропорциональности растра. Xasp,Yasp - соответствуют визуально одинаковым отрезкам по вертикали игоризонтали в данном растре графического режима. setaspectratio(Xasp,Yasp) (integer,integer) - (i,i) Корректировка коэффициента пропорциональности. Управление цветом. getpalettesize(PaletteSize) (integer) - (o) Определение количества динамически управляемых векторов кар-ты цветов для текущего графического режима. getmaxcolor(MaxColor) (integer) - (o) Максимальное значение атрибута пиксела, которое разрешаетсяиспользовать функциям графических примитивов и генераторов графи-ческих текстов. setpalette(Index,Actual_color) (integer,integer) - (i,i) Изменение одного из цветов внутренней палитры. Переназначае-мый цвет задается номером входа палитры Index, который должен ле-жать в пределах от 0 до Size-1. Actual_color - назначаемый цвет. setallpalette(PaletteList) (bgi_ilist) - (i) Полное изменение внутренней палитры цветов. PaletteList -список целых, описывающий палитру: [Size, перечень из Size цве-тов], где перечень содержит задаваемые цвета палитры. setbkcolor(Color) (integer) - (i) Изменение цвета фона на заданный Color. - 45 -getbkcolor(BkColor) (integer) - (o) Определение установленного текущей палитрой цвета фона. getpalette(PaletteList) (bgi_ilist) - (o) Возвращает список целых PaletteList, определяющий текущуюпалитру цветов. getdefaultpalette(DefaultPalette) (bgi_ilist) - (o) Возвращает список целых DefaultPalette, определяющий уста-новленную по умолчанию при инициализации графики палитру цветов. setcolor(Color) (integer) - (i) Изменение текущего значения рисующего цвета. Color можетпринимать значения от 0 до MaxColor. getcolor(Color) (integer) - (o) Определение текущего значения рисующего цвета. Доступ в видеопамяти. getpixel(X,Y,Color) (integer,integer,integer) - (i,i,o) Чтение точки с координатами (X,Y) в системе координат графи-ческого окна. putpixel(X,Y,Pixelcolor) (integer,integer,integer) - (i,i,i) Запись точки на экран с координатами (X,Y) в системе коорди-нат графического окна. imagesize(Left,Top,Right,Bottom,Size) (integer,integer,integer,integer,integer) - (i,i,i,i,o) Определение необходимого размера Size оперативной памяти длясохранения графического окна с координатами Left, Top, Right,Bottom. getimage(Left,Top,Right,Bottom,BitMap) (integer,integer,integer,integer,string) - (i,i,i,i,o) Сохранение графического окна с координатами Left, Top,Right, Bottom в строке BitMap. - 46 -putimage(X,Y,Bitmap,Op) (integer,integer,string,integer) - (i,i,i,i) Запись сохраненного в строке Bitmap графического окна на ак-тивную страницу, начиная с координат X, Y (левого верхнего угла)в режиме Op. Op принимает значения, определяя соответствующую ло-гическую операцию между атрибутами пиксела видеопамяти и пикселаиз Bitmap: COPY_PUT = 0 /* MOV */ XOR_PUT =1 /* XOR */ OR_PUT =2 /* OR */ AND_PUT = 3 /* AND */ NOT_PUT = 4 /* NOT */ Графические примитивы. line(X0,Y0,X1,Y1) (integer,integer,integer,integer) - (i,i,i,i) Линия, соединяющая две точки с координатами (X0,Y0) и(X1,Y1). linerel(Dx,Dy) (integer,integer) - (i,i) Линия, соединяющая текущую графическую позицию и точку, за-данную через приращение координат. lineto(X,Y) (integer,integer) - (i,i) Линия, соединяющая текущую графическую позицию и точку, за-данную координатами (X,Y). rectangle(Left,Top,Right,Bottom) (integer,integer,integer,integer) - (i,i,i,i) Прямоугольник, заданный координатами левого верхнего и пра-вого нижнего углов. drawpoly(PolyPointsList) (bgi_ilist) - (i) Ломаная линия, состоящая из отрезков прямых, заданных коор-динатами точек из списка целых чисел PolyPointsList. Первый эле-мент списка определяет количество точек, остальные координаты са-мих точек. - 47 -circle(X,Y,Radius) (integer,integer,integer) - (i,i,i) Окружность с радиусом Radius и центром (X,Y). arc(X,Y,StAngle,EndAngle,Radius)(integer,integer,integer,integer,integer) - (i,i,i,i,i) Дуга окружности с радиусом Radius и центром (X,Y), ограни-ченная углами StAngle, EndAngle. Углы выражаются в градусах и от-меряются против часовой стрелки от направления, задаваемого осьюX графической страницы. Дуга проводится от угла StAngle к углуEndAngle против часовой стрелки. ellipse(X,Y,StAngle,EndAngle,Xradius,YRadius)(integer,integer,integer,integer,integer,integer) - (i,i,i,i,i,i) Дуга эллипса с центром в точке (X,Y), радиусами осейXRadius, YRadius, ограниченная углами StAngle, EndAngle. Оси эл-липса параллельны осям координат страницы. getarccoords(X,Y,Xstart,Ystart,Xend,Yend)(integer,integer,integer,integer,integer,integer) - (o,o,o,o,o,o) Определение характеристик дуги окружности, построенной припоследнем использовании предиката arc. Дуга характеризуется тремяточками: (X,Y) - центр окружности, (Xstart,Ystart) - координатыначала дуги и (Xend,Yend) - координаты ее конца. setwritemode(WriteMode) (integer) - (i) Установка режима прорисовки. Число WriteMode определяет ло-гическую операцию между атрибутами пиксела видеопамяти и пикселарисуемого объекта. Допустимы только операции: COPY_PUT = 0 /* MOV */ и XOR_PUT =1 /* XOR */. setlinestyle(Linestyle,Upattern,Thickness) (integer,integer,integer) - (i,i,i) Установка характера и толщины Thickness линий геометрическихобъектов. Тип линии Linestyle определяется следующими значениями: SOLID_LINE = 0 сплошная, DOTTED_LINE = 1 точечная, CENTER_LINE = 2 осевая штрих-пунктирная, DASHED_LINE = 3 пунктирная, - 48 - USERBIT_LINE = 4 определяемая пользователем, через аргумент Upattern. Upattern задает шаблон линии. Это целое число, каждый биткоторого, равный 1, определяет рисование пиксела, равный 0, -нет. Толщина задается двумя значениями: NORM_WIDTH = 1 в один пиксел, THICK_WIDTH = 3 в 3 пиксела. getlinesettings(LineStyle,Upattern,Thickness) (integer,integer,integer) - (o,o,o) Определение текущих характеристик линии. bar(Left,Top,Right,Bottom) (integer,integer,integer,integer) - (i,i,i,i) Построение закрашенного плоского прямоугольника по двум точ-кам. bar3d(Left,Top,Right,Bottom,Depth,Topflag)(integer,integer,integer,integer,integer,integer) - (i,i,i,i,i,i) Построение закрашенного объемного прямоугольника по двумточкам (прямоугольник), Depth - глубина проекции 3-го измерения,Topflag определяет прорисовку (=1) верхних ребер параллелепипеда. fillpoly(PolyPointsList) (bgi_ilist) - (i) Построение закрашенного многоугольника (см. drawpoly). fillellipse(X,Y,Xradius,YRadius) (integer,integer,integer,integer) - (i,i,i,i) Построение закрашенного эллипса. pieslice(X,Y,Stangle,Endangle,Radius) (integer,integer,integer,integer,integer) - (i,i,i,i,i) Построение закрашенного кругового сектора. floodfill(X,Y,Border) (integer,integer,integer) - (i,i,i) Закрашивание области внутри существующего замкнутого конту-ра. Точка (X,Y) должна находится внутри контура. Border определя-ет цвет пикселов ограничивающего область закраски контура. - 49 -setfillstyle(Pattern,Color) (integer,integer) - (i,i) Установка цвета Color и кода заполнения Pattern для закраши-ваемых фигур. Pattern может принимать следующие значения: EMPTY_FILL = 0 заполнить цветом фона SOLID_FILL = 1 заполнить текущим цветом LINE_FILL = 2 --- LTSLASH_FILL = 3 /// SLASH_FILL = 4 /// толстыми линиями BKSLASH_FILL = 5 \\\ толстыми линиями LTBKSLASH_FILL = 6 \\\ HATCH_FILL = 7 light hatch fill XHATCH_FILL = 8 heavy cross hatch fill INTERLEAVE_FILL = 9 interleaving line fill WIDE_DOT_FILL = 10 Widely spaced dot fill CLOSE_DOT_FILL = 11 Closely spaced dot fill USER_FILL = 12 user defined fill setfillpattern(UpatternList,Color) (bgi_ilist,integer) - (i,i) Определение своего шаблона закраски. Шаблон представляет со-бой бинарную матрицу 8х8, состоящую из 8 последовательных целыхчисел, образующих список UpatternList. getfillsettings(FillPattern,FillColor) (integer,integer) - (o,o) Запрос текущей установки шаблона и кода заполнения. getfillpattern(PatternList) (bgi_ilist) - (o) Запрос описания шаблона пользователя. Вывод графических текстов. settextstyle(Font,Direction,Charsize) (integer,integer,integer) - (i,i,i) Инициализация знакогенератора для работы с конкретным графи-ческим шрифтом. Устанавливаются шрифт Font, направление строкDirection и размер символов Charsize. Шрифт задается следующими значениями: DEFAULT_FONT = 0 - матричный шрифт, размер символов 8x8 TRIPLEX_FONT = 1 остальные шрифты векторные - 50 - SMALL_FONT =2 SANS_SERIF_FONT = 3 GOTHIC_FONT =4 Направление строк - HORIZ_DIR = 0 - слева направо VERT_DIR = 1 - снизу вверх Размер символов управляет масштабом выводимых символов, диа-пазон допустимых значений от 1 до 10. setusercharsize(Multx,Divx,Multy,Divy) (integer,integer,integer,integer) - (i,i,i,i) Установка новых размеров символов путем умножения ширины ивысоты базового варианта каждого символа на значения выражений(Multx/Divx) и (Multy/Divy) соответственно. settextjustify(Horiz,Vert) (integer,integer) - (i,i) Управление расположением выводимой строки относительно опор-ной точки (Horiz,Vert). Аргументы могут принимать значения:Расположение по горизонтали Расположение по вертикали LEFT_TEXT = 0 слева BOTTOM_TEXT = 0 внизу CENTER_TEXT = 1 по центру CENTER_TEXT = 1 в центре RIGHT_TEXT = 2 справа TOP_TEXT = 2 вверху gettextsettings(Font,Direction,CharSize,Horiz,Vert) (integer,integer,integer,integer,integer) - (o,o,o,o,o) Определение характеристик текущего режима вывода графическихтекстовых сообщений. textheight(Textstring,Height) (string,integer) - (i,o) Определение высоты Height в пикселах текстовой строкиTextstring. textwidth(Textstring,Width) (string,integer) - (i,o) Определение ширины Width в пикселах текстовой строкиTextstring. outtext(Textstring) (string) - (i) Вывод текста Textstring в текущую графическую позицию. outtextxy(X,Y,Textstring) (integer,integer,string) - (i,i,i) Вывод текста Textstring в позицию с координатами (X,Y). 2.10. Старая графика (OLD GRAPHICS) graphics(ModeParam,Palette,Background) (integer,integer,integer) - (i,i,i) Устанавливает графический режим, где: ModeParam - задает режим (1..5), Palette - задает палитру (0 или 1), Background - задает цвет фона. dot(Row,Column,Color) (integer,integer,integer) - (i,i,i) (i,i,o) Устанавливает или читает цвет Color точки (Row,Column). line(Row1,Col1,Row2,Col2,Color) (integer,integer,integer,integer,integer) - (i,i,i,i,i) Рисует линию заданным цветом. text Устанавливает текстовый режим. 2.11. Черепашья графика (TURTLE GRAPHICS) (работает только вместе со старой графикой) Замечание: Черепашья графика (Turtle Graphics) не совместима с BGI-гра-фикой, поэтому вы должны выбрать одну из двух графических системдля вашей прикладной программы ! pendown Опустить перо. penup Поднять перо. pencolor(Color) (integer) - (i) (o) Установить(определить) цвет пера. - 52 -forward(Step) (integer) - (i) Продвинуться вперед на Step шагов. back(Step) (integer) - (i) Вернуться назад на Step шагов. right(Angle) (integer) - (i) Повернуть перо на угол Angle (в градусах) вправо (по часовойстрелке) left(Angle) (integer) - (i) Повернуть перо на угол Angle (в градусах) влево (против ча-совой стрелки). penpos(RowCoordinate,ColumnCoordinate,Angle) (Integer,Integer,Integer) - (i,i,i) (o,o,o) Установить (или определить) позицию пера и его направление. 8. Имитация управления, предикат звукаsound(Duration,Frequency) (integer,integer) - (i,i) Подача звукового сигнала длительностью Duration (в сотых до-лях секунды) и частотой Frequency (в герцах). beep Произвести стандартный звуковой сигнал. 9. Задачи на сопоставление, работа с деревьями