 |
|
Сортировка посредством выбора
Идея сортировки с помощью выбора не сложнее двух предыдущих. На j-ом этапе выбирается элемент наименьший среди M[j], M[j+1],. . ., M[N](см. процедуру FindMin) и меняется местами с элементом M[j]. В результате после j-го этапа все элементы M[j], M[j+1],. . ., M[N]будут упорядочены.
Сказанное можно описать следующим образом:
нц для j от 1 до N-1
выбрать среди M[j],. . ., M[N] наименьший элемент и
поменять его местами с M[j]
кц
Более точно:
begin
for j:=1 to N-1 do
begin
FindMin(j, i);
swap(M[j],M[i])
end
end;
Правила позволяет определить новые отношения между объектами на основе уже объявленных с помощью фактов. В качестве аргументов в предикатах правила могут использоваться не только константы, но и переменные. Правила используются в том случае, когда необходимо сказать, что некоторый факт зависит от группы других фактов. Например:
знает (мария, английский).
знает (иван, английский).
«Знает Иван то (х), что знает Мария?»
знает (иван, Х) :- знает (мария, Х).
констатирующая часть условная часть
Тело правила может содержать 1, 2 или несколько предикатов, объединенных между собой операцией логического умножения. В этом случае говорят, что тело правила содержит конъюнкцию целей. Например:
«Алисе нравиться кто-то, если кому-то нравятся книги и кому-то нравится музыка»
нравится (алиса, Y) :- нравится (Y, книга), нравится (Y, музыка).
Чем больше аргументов, входящих в правило, являются переменными, тем большей общностью правило обладает.
Истинность правила зависит от некоторых условий (целей). Если все цели в теле правила истинны, то и все правило считается истинным. Из совокупности фактов и правил об объектах и отношениях между ними строится база знаний. Например:
знает (мария, английский).
знает (иван, английский).
«Знает Иван то (х), что знает Мария?»
знает (иван, Х) :- знает (мария, Х).
знает (иван, Х) :- знает (мария, Х).
студент (олег).
студентка (мария).
профессор (петр_петрович).
учится (Х) :- студент (Х).
учится (Х) :- студентка (Х).
преподает (Х) :- профессор (Х).
Вопрос – это отправная точка логического вывода, происходящего при выполнении программ. Вопрос в Прологе называется целью.
Рассмотрим два вида вопросов (целей):
1. сущность вопроса в том, чтобы подтвердить справедливость фактов. В результате получится ответ «ДА», если факт содержится в базе знаний или выводится с использованием фактов и правил базы знаний. В противном случае получается ответ «НЕТ».
? – знает (иван, английский). - ДА
2. сущность вопроса состоит в перечислении всех значений переменной указанной в запросе, удовлетворяющему фактам и правилам базы знаний.
? – знает (иван, Х). – английский, алгебра, информатика, история
? – знает (Х, алгебра), учится (Х). – х – мария
Факт — это сообщение (информация) о конкретном событии, о свойстве конкретного объекта, о его связи с другими объектами. Например, фактами являются следующие утверждения:
сосна — хвойное дерево;
Колумб открыл Америку в 1492 году;
плотность воды равна 1 г/см3;
царь Соломон — сын царя Давида;
Лев Толстой — русский писатель.
Правило — это утверждение, обладающее большей общностью, чем факт. Правила определяют одни понятия через другие, устанавливают взаимосвязь
Вот вопрос первого типа к БЗ «Родственники», сформулированный в разговорной форме:
Является ли Лев отцом Андрею?
На Прологе соответствующая цель пишется так:
? отец («Лев», «Андрей»).
Ответ будет положительный: «да», поскольку такой факт содержится в базе знаний. Ответ на следующий вопрос:
?внук («Алексей», «Лев»)
будет также положительный. При этом система Пролог проанализирует правила и факты базы знаний и, установив искомую связь, выведет ответ «да». На вопрос же
? сын («Дмитрий», «Андрей»),
то есть является ли Дмитрий сыном Андрея, будет получен ответ «нет».
А теперь сформулируем цели второго типа. Пусть, например, нам требуется получить список имен всех детей Петра. Вопрос запишется так:
? отец («Петр», Х).
Пролог выдаст ответ в следующем виде:
X = Михаил;
X= Дмитрий.
Тот же самый вопрос можно сформулировать и иначе:
? сын (Х, «Петр»).
Ответ будет тот же, что и выше.
Поскольку имя переменной может быть многосимвольным (главное, чтобы начиналось с прописной буквы), то этим можно воспользоваться для получения более наглядного ответа. По следующему запросу будут выведены все пары имен отец-сын:
? отец (Отец, Сын).
Результат:
Отец=Лев, Сын=Андрей;
Отец=Лев, Сын=Петр;
Отец=Андрей, Сын=Алексей;
Отец=Петр, Сын=Михаил;
Отец=Петр, Сын=Дмитрий.
Конъюнкция используется не только в формулировке правил, но и при записи целей. Предположим, нужно узнать, действительно ли Лев имеет двух сыновей по имени Андрей и Петр? Это запрос первого типа, дающий ответ «да» или «нет».
? отец («Лев», «Андрей»), отец («Лев», «Петр»).
Ответ будет положительный.
Другой пример. Требуется перечислить имена внуков Льва, которые являются сыновьями Петра:
? внук (Х, «Лев» ), сын (Х, «Петр» ).
Ответ будет:
X = Михаил; X = Дмитрий.
А теперь обратимся к БЗ с запросом:
? брат (X,Y),
то есть мы хотим перечислить все пары братьев. Ответ будет таким:
Х = Андрей, Y = Петр; Х = Петр, Y = Андрей; Х = Дмитрий, Y = Михаил;
Х = Михаил, Y = Дмитрий.
Каждая пара повторяется дважды в разном порядке. Чтобы избавиться от повторений, цель можно сформулировать так:
? брат (X,Y), X<Y.
Ответом будет:
X = Андрей, Y = Петр;
Х = Дмитрий, Y = Михаил.
2) из рекурсивного правила, определяющего операцию над списком, состоящим из головы и хвоста ( в голове правила), через операцию над хвостом (в подцели).
Пример I: определение числа элементов в списке.
сколько ([], 0).
сколько ([А|В], N) :- сколько (В, М), N is M+1.
?- сколько ([саша, игорь, лена]), X).
Ответ: Х=3.
Пример 2: принадлежность элемента списку.
принадлежит (X, [X | Y]).
принадлежит (X, [A |Y ]) : - принадлежит (X,Y).
?-принадлежит (4,(1,3,4,9]).
Ответ:да.
Данная программа имеет очень простой декларативный смысл: элемент принадлежит списку, если он является его головой или принадлежит хвосту списка.
Пример 3: соединение двух списков.
Эту задачу можно описать с помощью следующих предикатов:
а) ограничение рекурсии состоит в том, что если к пустому списку [ ] добавить список Р, то в результате получится Р;
б) рекурсия состоит в том, что можно список Р добавить к концу списка [X|Y], если Р будет добавлен к хвосту Y и затем присоединен к голове Х (при этом получается список [Х|Т]).
присоединить([ ], Р, Р).
присоединить([XIY], Р, [X | Т]):-присоединить(Y, Р, Т).
? присоединить(L,[джим.R],(джек,бил,джим,тим,джим,боб]).
Ответ:
L=[джек,бил]. К=[тим джим,боб]. L=[джек,бил,джим,тим]. R=[бoб].
Существует традиция использовать для обозначения предиката слияния двух списков предикативный символ append (по-английски -добавить).
В некоторых случаях постановки вопросов к такого рода программам приходится использовать отсечение (!).
Программа 125
append([ ], L, L).
append([A I B] , C, [A | D]):- append(B, C, D).
?-append(X,Y,[1,2]).
Ответ:
X=[]
Y=[l,2]
X=[l]
Y=[2]
X=[l,2]
Y=[].
Если же заменить первое предложение на append([ ], 1,1):- !. и задать тот же вопрос, то получится правильный ответ:
Х=[]
Y=[l,2].
Пример 4. удаление элементов из списка.
Программа 126 аналогична проверке принадлежности элемента списку, но требует уже трехарного предиката, один аргумент которого указывает удаляемый элемент, второй аргумент-исходный список и третий - список-результат.
Программа 126
удал (X. [X I Y], Y) : - !.
что достигается, так называемым, поздним связыванием. Это дает возможность строить иерархию объектов с одинаковыми названиями методов, реализуемыми, однако, различными кодами.
Синтаксис виртуального метода:
procedure <Метод> (<Параметр1>, <Параметр2> : integer): virtual;
Кроме обычных процедур и функций, ТурбоПаскаль 6.0 реализует два специальных типа методов: конструктор и деструктор.
Конструктор - это специальный метод, инициализирующий объект, содержащий виртуальные методы, он объявляется специально зарезервированным словом constructor. Конструктор инициализирует объект путем установления связи между объектом и специальной таблицей виртуальных методов, содержащей адреса кодов, реализующих виртуальные методы. Конструктор может также использоваться для инициализации полей данных объекта.
Деструктор - это специальный метод, освобождающий память «кучи» от динамических объектов. Он объявляется с использованием специально зарезервированного слова destructor.
Основными отличительными свойствами объекта являются
• инкапсуляция - объединение записей с процедурами и функциями, работающими с этими записями;
• наследование - задание объекта, затем использование его для построения иерархии порожденных объектов с наследованием доступа каждого из порожденных объектов к коду и данным предка;
• полиморфизм - задание одногоимени действию, которое передается вверх и вниз по иерархии объектов с реализацией этого действия способом, соответствующим каждому объекту в иерархии.
Рассмотрим смысл каждого из перечисленных свойствна примере построения на экране дисплея точек разных цветов (звездного неба).
Инкапсуляция. Основой решения задачи является задание положения (позиции) отдельной точки на экране, описываемого координатами Х и Y. Для задания координат подходит тип «запись»:
Pozition = record
X, Y : integer;
end;
Далее может быть необходимо задать значения координат (такая процедура носит название инициализации). Создадим соответствующую процедуру:
procedure Init(CoordX, CoordY : integer);
begin
X : = CoordX; Y : = CoordY;
end;
Затем потребуется знание фактических значений координат. Для этого вводим две функции:
function GetX : integer;
begin
GetX: = X; end;
function GetY: integer; begin GetY: = Y;end;
По нашему замыслу процедура Init и функции GetX и GetY должны работать только с полями записи Pozition.
Введение объектов позволяет зафиксировать это положение, объявив и поля, и действия над ними в единой конструкции:
Pozition = object
X, Y: integer;
procedure Init(CoordX, CoordY : integer);
function GetX : integer; function GetY : integer; end;
Процедура Init и функции GetX и GetY являются методами объекта Pozition.
Для инициализации экземпляра типа Pozition достаточно вызвать его метод,
Существуют структуры, которые повторяют себя через 1, 2, ...,п временных шагов, их называют циклами «-n» (см. рис. 7.50).
Но наиболее интересны движущиеся структуры - «планеры», «корабли», «паровозы», их столкновения, «аннигиляции» и зарождение новых структур.
Представляет интерес модель игры в одномерном случае. Здесь имеется один ряд клеток. В некоторых нз них задаем «жизнь». Требуется изучить эволюцию клеток, если заданы правила их существования и зарождения.
Определим сумму значений пяти соседних клеток (самой клетки и двух ближайших к ней слева и справа). На следующем шаге в
основном на Си — языке высокого уровня, который специально был создан для написания одной из первых версий UNIX). Аппаратно зависимые участки кода, такие как загрузчик ОС, уровень абстрагирования от аппаратного обеспечения (hardware abstraction layer) и ядро, часто пишутся на языке ассемблера. Фактически, ассемблерного кода в ядрах Windows или Linux совсем немного, поскольку авторы стремятся обеспечить переносимость и надёжность, но, тем не менее, он там присутствует. Некоторые любительские ОС, такие как MenuetOS и KolibriOS, целиком написаны на языке ассемблера. При этом MenuetOS помещается на дискету и содержит графический многооконный интерфейс.
Программирование микроконтроллеров (МК) и других встраиваемых процессоров. По мнению профессора Таненбаума, развитие МК повторяет историческое развитие компьютеров новейшего времени. Сейчас (2013 г.) для программирования МК весьма часто применяют язык ассемблера (хотя и в этой области широкое распространение получают языки вроде Си). В МК приходится перемещать отдельные байты и биты между различными ячейками памяти. Программирование МК весьма важно, так как, по мнению Таненбаума, в автомобиле и квартире современного цивилизованного человека в среднем содержится 50 микроконтроллеров.
Создание драйверов. Драйверы (или их некоторые программные модули) программируют на языке ассемблера. Хотя, в настоящее время, драйверы также стремятся писать на языках высокого уровня (на высокоуровневом языке много проще написать надёжный драйвер), в связи с повышенными требованиями к надёжности, и достаточной производительностью современных процессоров (быстродействие обеспечивает временно́е согласование процессов в устройстве и процессоре) и достаточным совершенством компиляторов с языков высокого уровня (отсутствие ненужных пересылок данных в сгенерированном коде), подавляющая часть современных драйверов пишется на языке ассемблера. Надёжность для драйверов играет особую роль, поскольку в Windows NT и UNIX (в том числе в Linux) драйверы работают в режиме ядра системы. Одна тонкая ошибка в драйвере может привести к краху всей системы.
Создание антивирусов и других защитных программ.
Написание трансляторов языков программирования.
Программирование арифметических выражений в языке Ассемблер происходит через некоторые команды такие, как: mul, div, sub, add. Эти команды называются командами арифметических операций.
Mul – команда умножения. Она умножает регистр axна то, что стоит после нее. Результат заносится в ax.
Div – команда деления. Она делит регистр ax на то, что стоит после нее. Результат заносится в ax.
Add – команда сложения. Слаживает два числа. Результат заносится в первый регистр.
Sub – команда вычитания. Вычитает два числа. Результат заносится в первый регистр.
Пример: Написать программу на ассемблере вычисления выражения: а – e/b – de;
обе составляющие силы сопротивления, но если мы захотим моделировать полет снаряда, выпущенного из орудия, где скорость полета почти на всем его протяжении сотни метров в секунду, то линейной составляющей силы сопротивления можно пренебречь. Проецируя уравнение 
на оси х и у, получаем
Поскольку в каждой точке траектории сила сопротивления направлена по касательной к траектории в сторону, противоположную движению, то
где θ - угол между текущим направлением скорости и осью х. Подставляя это в уравнение и учитывая, что 
, получаем уравнения движения в переменных vx, vy.
(7.12)
Поскольку представляет несомненный интерес и траектория движения, дополним систему (7.12) еще двумя уравнениями
(7.13)
и, решая их совместно с (7.12), будем получать разом четыре функции: vx(t), vy(t), x(t), y(t).
Прежде чем дать пример решения обсуждаемой задачи, покажем очень полезный прием, чрезвычайно популярный в физическом моделировании, называемый обезразмериванием. При решении конкретных задач мы пользуемся определенной системой единиц (СИ), в которой далеко не все числовые значения лежат в удобном диапазоне. Кроме того, абсолютные значения величин дают мало информации для качественного понимания. Скорость 15 м/с - много это или мало? Все дело в том, по сравнению с чем. Именно в сравнении с чем-то привычным и понятным мы обычно и воспринимаем слова «много» и «мало», даже если делаем это бессознательно. Идея обезразмеривания заключается в переходе от абсолютных значений расстояний, скоростей, времен и т.д. к относительным, причем отношения строятся к величинам, типичным для данной ситуации. В рассматриваемой задаче это особенно хорошо просматривается. В самом деле, при отсутствии сопротивления воздуха мы имеем значения l, h, t, определенные выше; сопротивление воздуха изменит характер движения, и если мы введем в качестве переменных величины
программа выдает в графическом режиме семейство траекторий, отличающихся значениями одного из трех безразмерных параметров (в данном случае b).
Программа 148. Реализация модели «Полет тела, брошенного под углом к горизонту»
Program Pod Uglom;
Uses Crt, Graph;
Type G = Array[1..4] Of Real;
Const A = 0; В =0.1; (параметры модели)
Al = Pi / 4; (угол - параметр модели}
Н = 0.001; Нрr = 0.1; (шаг интегрирования и шаг вывода результатов)
Var N, I, J, M, L, К : Integer;
Y0, Y : G; Х0, X, Xpr, A1, B1, Cosinus, Sinus : Real; LS : String;
Function Ff(I : Integer; X : Real; Y : G) : Real;
{описание правых частей дифференциальных уравнений}
Begin
Case I Of
1: Ff:=-A1*Sinus*Y[l]-Bl*Sinus*Sqrt(Sqr(Y(l])+Sqr(Y[2]))*Y[1];
2: Ff:=-Sinus-A1*Sinus*Y[1]-B1*Sinus*Sqrt(Sqr(Y(1])+Sqr(Y[2]))*Y[2];
3: Ff:=Y[1]/(2*Cosinus);
4: Ff:=2*Y[2]/Sinus
End End;
Procedure Runge_Kut (N: Integer; Var X: Real; Y0: G; Var Y: G; Н: Real);
(метод Рунге-Кутта четвертого порядка)
Var I : Integer; Z, K1, K2, КЗ, К4 : G;
Procedure Right(X : Real; Y : G; Var F : G) ;
{вычисление правых частей дифференциальных уравнений}
Var I : Integer;
Begin For I := 1 To N Do F[I] := Ff(I, X, У)
End; Begin Right(X, Y0, K1); X := X + Н / 2;
For I := 1 To N Do Z[I]:=Y0[I]+H*K1[I]/2; Right(X, Z, K2);
For I := 1 To N Do Z[I]:=YO[I]+H*K2[I]/2; Right(X, Z, КЗ); Х:=Х+Н/2;
For I := 1 To N Do Z[I] := Y0[I] + H * КЗ [I]; Right (X, Z, К4);
For I := 1 To N Do
Y[I]:=Y0[I]+H*(K1[I]+2*K2[I]+2*K3[I]+K4[I])/6;
End; {следующий блок - для получения численных результатов при одном наборе параметров}
{Begin
Sinus := Sin(Al); Cosinus := Cos(Al); Al := A; Bl := B; ClrScr;
N:=4; X0:=0; Y0[l]:=Cosinus; Y0[2]:=Sinus; Y0[3]:=0; Y0[4]:=0;
WriteLn(' время скорость координаты');
WriteLn; X := Х0; Xpr := 0; Y[4] := Y0[4];
While Y[4] >= 0 Do
Begin If X >= Xpr Then Begin
WriteLn ('t=', X : 6 : 3, ' Vx='. Y0[l] : 6 : 3, ' Vy=',
Y0[2] : 6 : 3. ' X=', y0[3] : 6 : 3, ' Y=', Y0[4] : б : 3) ;
Xpr := Xpr + Hpr
End; Runge_Kut(N, X, Y0, Y, H); Y0 := Y
End; WriteLn; WriteLn('для продолжения нажмите любую клавишу');
Repeat Until KeyPressed
Если массив был создан с помощью оператора new, то каждый его элемент получает значение по умолчанию. Каким оно будет определяется на основании типа данных (0 для int, 0.0 для double и т. д.).
Объявить имя для массива и создать сам массив можно было на одной строке по следующей схеме:
тип[] имя = new тип[размер]; тип[] имя = {эл0, эл1, …, элN}; Примеры:
int[] mas1 = {10,20,30}; int[] mas2 = new int[3]; Чтобы обратиться к какому-то из элементов массива для того, чтобы прочитать или изменить его значение, нужно указать имя массива и за ним индекс элемента в квадратных скобках. Элемент массива с конкретным индексом ведёт себя также, как переменная. Например, чтобы вывести последний элемент массива mas1 мы должны написать в программе:
System.out.println("Последний элемент массива " + mas1[2]); А вот так мы можем положить в массив mas2 тот же набор значений, что хранится в mas1:
mas2[0] = 10;mas2[1] = 20;mas2[2] = 30; Уже из этого примера видно, что для того, чтоб обратиться ко всем элементам массива, нам приходится повторять однотипные действия. Как вы помните для многократного повторения операций используются циклы. Соответственно, мы могли бы заполнить массив нужными элементами с помощью цикла:
for(int i=0; i<=2; i++) { mas2[i] = (i+1) * 10; } Понятно, что если бы массив у нас был не из 3, а из 100 элементов, до без цикла мы бы просто не справились.
Длину любого созданного массива не обязательно запоминать, потому что имеется свойство, которое его хранит. Обратиться к этому свойству можно дописав .length к имени массива. Например:
int razmer = mas1.length; Это свойство нельзя изменять (т. е. ему нельзя ничего присваивать), можно только читать. Используя это свойство можно писать программный код для обработки массива даже не зная его конкретного размера.
Например, так можно вывести на экран элементы любого массива с именем ar2:
for(int i = 0; i <= ar2.length - 1; i++) { System.out.print(ar2[i] + " "); } Для краткости удобнее менять нестрогое неравенство на строгое, тогда не нужно будет вычитать единицу из размера массива. Давайте заполним массив целыми числами от 0 до 9 и выведем его на экран:
for(int i = 0; i < ar1.length; i++) {ar1[i] = Math.floor(Math.random() * 10); System.out.print(ar1[i] + " ");} Обратите внимание, на каждом шаге цикла мы сначала отправляли случайное значение в элемент массива с i-ым индексом, а потом этот же элемент выводили на экран. Но два процесса (наполнения и вывода) можно было проделать и в разных циклах. Например:
В программе, как уже было сказано, используется процедура FindMin, вычисляющая индекс lowindex элемента, наименьшего среди элементов массива с индексами не меньше, чемstartindex:
procedure FindMin(startindex: integer; var lowindex: integer);
var lowelem: ...;
u: integer;
begin
lowindex := startindex;
lowelem := M[startindex];
for u:=startindex+1 to N do
if M[u] < lowelem then
begin
lowelem := M[u];
lowindex := u
end
end;
между различными свойствами объектов, формулируют законы природы или общества.
База знаний — это совокупность основополагающих фактов и правил в определенной предметной области.
Рассмотренный нами пример очень простой. Здесь нетрудно догадаться о том, какие факты являются основополагающими, и сформулировать полный набор правил. В более сложных предметных областях эта задача много труднее. Часто решить ее по силам оказывается только крупному специалисту (эксперту) или коллективу специалистов, обладающих большими знаниями в данной области.
С недавних пор появилась новая специальность « инженер по знаниям», задача которого – формализация знаний, разработка баз знаний и создание на их основе систем искусственного интеллекта
Теперь познакомимся с представлением правил на Прологе. Сначала запишем правило, определяющее понятие «сын». Его можно сформулировать так:
«А является сыном для В, если В является отцом для А».
Здесь под А и В понимаются любые мужские имена. На Прологе это запишется следующим образом:
сын(А, В) :- отец(В, А).
Простейшее правило на Прологе записывается в виде двух предикатов, соединенных знаком «:-», который читается «если». Предикат, записанный слева от «:-» называется заголовком (головой) правила. Часть правила, стоящая после знака «:-», называется телом правила. Всякое правило обозначает следующее:
если имеет место тело правила, то справедлив заголовок.
В терминологии Пролога А и В называются переменными. Переменная может обозначаться одной прописной (заглавной) буквой или словом, начинающимся с прописной буквы. В данном примере А и В обозначают любое мужское имя. По смыслу переменная может быть заменена на неопределенное местоимение: кто-то, что-то, некто, нечто и т.п.
Правила обладают большей общностью, чем факты, и обычно содержат переменные. Попробуем добавить в базу знаний «Родственники» правило, определяющее, кто есть дедушка. Понятно, что Лев является дедушкой Алексею потому, что Андрей — отец Алексея, а Лев — отец Андрея. Используя понятие переменной, можно сказать иначе: «X является дедушкой для Y, если X является отцом для Z и Z является отцом для Y».
Таким образом, тело правила состоит из двух отношений, соединенных связкой «и». На Прологе это запишется так: дедушка (X,Y) :- отец (X,Z) , отец (Z,Y).
В этой записи роль связки «и» играет запятая «,».Имея определение «дедушка», сформулируем правило, определяющее, кто такой внук:
внук (X,Y) :- дедушка (Y,X).
А теперь дадим определение, кто такой брат. Имея уже достаточный опыт, мы можем сформулировать его так: X является братом для Y, если Z является отцом одновременно для X и для Y.
брат (X,Y) :- отец (Z,X), отец (Z,Y).
Рассмотрим еще один запрос к БЗ «Родственники». Нужно выяснить, кто является одновременно братом и племянником. Если цель поставить следующим образом:
? брат (X,Y), племянник (X,Z),
то в результате получим:
Х = Михаил, Y= Дмитрий, Z = Андрей;
Х = Дмитрий, Y = Михаил, Z = Андрей.
На запросы второго типа Пролог выдает все значения переменных, упомянутых в формулировке цели. В данном случае искомым ответом является значение переменной X. Информация о брате (Y) и дяде (Z) — избыточна. Но если запрос построить в такой форме:
? брат (Х,_), племянник (Х,_),
то ответом будет:
Х = Михаил; Х = Дмитрий.
Здесь дважды использован «пустой» аргумент, отмечаемый символом подчеркивания «_». Пустой аргумент обозначает любое значение. Запрос можно переформулировать так: найти X, который является братом кому угодно и племянником кому угодно. Поскольку в формулировке цели присутствует только одна переменная (X), то ее значение и выводится.
Рассмотрим еще один пример с информацией о родственных отношениях, представленных следующим графом:
Очевидно, в базу знаний войдут два факта:
отец («Андрей», «Алексей»);
мать («Ольга», «Алексей»).
А теперь определим отношение «сын» в форме правила. Человек является сыном как матери, так и отцу. Поэтому формально можно сказать так: «X является сыном для Y, если Y является отцом для X или Y является матерью для X».
Здесь возникает логическая связка «или», которой нет в стандарте Пролога (в Турбо-Прологе она есть). Тем не менее из положения можно выйти, дважды сформулировав правило, определяющее отношение сын:
сын(Х,Y ):-отец(Y,Х); сын(Х,Y):-мать(Y,Х).
Теперь на вопрос к этой базе знаний ?сын(Х, «Ольга») получим ответ: Х=Алексей. А на вопрос ?сын(Х, «Андрей» ) ответ будет Х=Алексей. На вопрос
?сын(Х,Y)
получим ответ
Х=Алексей, Y=Андрей; Х=Алексей, Y=Ольга.
Алгоритм, по которому система Пролог ищет в базе знаний ответы на поставленные вопросы, называется механизмом вывода Пролога.
удал (X. [Z I Y], [Z I W]) : - удал (X, Y, W) .
Декларативный смысл: если удаляемый элемент совпадает с головой списка, то результатом программы является хвост списка, иначе удаления производятся из хвоста списка.
Данная программа удаляет первое вхождение в список элемента, связанного с переменной X. Знак отсечения "!"в конце правила предотвращает последующий поиск и вывод лишних вариантов ответов после выполнения ограничительного факта.
Для удаления всех вхождений элемента Х программу надо дополнить:
удал (Х,[ ],[]).
удал (X, [X | Y], W) :- удал (X, Y, W).
удал (X, [Z I Y], W):- удал (X, Y, W).
Декларативный смысл программы таков: пока список не пуст, удалить элемент, если он совпадает с головой списка, значит, отбросить голову списка, а затем удалять его из оставшегося хвоста, иначе надо сразу удалять элемент из хвоста.
Пример 5: индексация элементов списка.
Смысл программы 127 состоит в том, чтобы получить элемент под номером N или узнать номер элемента X.
получить ([X | Y], 1, X).
получить ([W | Y], N, X) :- N is M+l, получить (Y, M, X).
Пример 6: поиск максимального элемента.
max ([X], X).
max ([X | Y], X) :- шах (Y, W), X>W, !.
max ([X | Y], W) :-max (Y, W).
Декларативный смысл программы: если в списке один элемент - он и является максимальным, если более одного, то это голова списка, если она больше максимального элемента хвоста, или максимальный элемент хвоста.
Пример 7: обращение списка.
Данная задача - самая сложная из рассмотренных. Для ее решения важно сообразить, что обратить список из одного элемента - означает оставить список без изменения. Обратить более длинный список - обратить его хвост, а потом сзади приставить к нему голову исходного списка.
обр ([X], [X]) .
обр ([X I Y], Z) :- обр (Y, W), присоединить (W, [X], Z).
В этой программе используется процедура слияния списков, описанная выше.
Arity-Prolog располагает значительным числом встроенных предикатов для обработки списков, так что приведенные программы имеют, в основном, учебный характер.
как если бы он был полем записи:
var
FirstPozition : Pozition;
…
FirstPozition.Init(10,15);
Метод задается так же, как и процедура в модуле: внутри объекта записывается заголовок (как в секции Interface модуля); при этом все поля, используемые мето-дом, должны предшествовать его объявлению. Определение метода (расшифровка действий) происходит вне объявления объекта. Имя метода должно предваряться названием типа объекта, которому метод принадлежит, сопровождаемым точкой. Например,
procedure Pozition. Init(CoordX, CoordY: integer);
begin
X: = CoordX: Y: = CoordY; end;
Заметим, что имена формальных параметров метода не могут совпадать с именами полей данных объекта.
Также как модуль скрывает детали реализации процедур от пользователя, объект может скрывать свои поля и методы. Для этого используется ключевое слово private (личный). Личные поля и методы доступны только внутри метода. Объявление выглядит следующим образом:
type
ObjectName=object
поле; … поле; метод; метод; private поле; … поле; метод; … метод; end;
Наследование. Рассмотрим точку с координатами Х и Y. Ее можно сделать видимой или невидимой, ей можно задать цвет, ее можно переместить. Создадим объект с такими возможностями:
Point=object
X,Y : integer; "
procedure Init(CoordX, CoordY : integer);
function GetX : integer;
function GetY . integer;
Visible: Boolean;
Color: Word;
procedure Init(CoordX, CoordY : integer; InitCoIor : Word);
function Is Visible : Boolean;
procedure Show;{показывает точку}
procedure Blind; {стирает точку}
procedure Jump(NextX, NextY : integer);{nepeMeiuaer точку} end;
Заметим, однако, что поля X.Y и методы GetX, GetY практически совпадают с соответствующими полями и методами объекта Pozition.
Турбо-Паскаль предоставляет возможность учесть эту ситуацию. Следует считать тип объекта Point порожденным типом Pozition, записав это следующим образом:
Point=object(Pozition)
Visible : Boolean; Color : Word;
procedure Init(CoordX, CoordY : integer; InitColor : Word);
function Is Visible . Boolean;
procedure Show; procedure Blind:
procedure Jump(NextX, NextY : integer); end;
Объект Point теперь наследует свойства объекта Pozition. Поля X,Y явно не заданы в Point, но Point ими обладает благодаря наследованию, т.е. можно написать Point.X:=17;