Бадд Т. Объектно-ориентированное программирование
Подождите немного. Документ загружается.
end
/* не можем двигаться дальше */
/* сдвинем соседа к следующему решению */
if not neighbor.advance then
return false
/* начнем снова с 1-й строки */
row := 1
return self.findSolution
end
Теперь осталось только напечатать решение. Это делается очень просто с помощью
метода print, который рекурсивно повторяется для всех соседей.
procedure print
neighbor.print
write row, column
end
5.3. Задача о восьми ферзях на различных языках программирования
В этом параграфе мы приведем решение задачи о восьми ферзях для каждого
рассматриваемого языка программирования. Сравните тексты программ. Обратите
внимание на то, как свойственные языку черты привносят хитроумные изменения в
решение задачи. В частности, проанализируйте решения на языках Smalltalk и Objective-C,
использующие специальный «караульный» класс, и сравните их с кодом на Object Pascal,
C++ или Java, каждый из которых использует нулевой указатель для самого левого ферзя
и постоянно вынужден проверять значение указателей.
5.3.1. Задача о восьми ферзях: Object Pascal
Определение класса для задачи о восьми ферзях на языке Object Pascal версии Apple
приведено ниже. Тонкой и важной чертой является то, что это определение рекурсивно —
объекты типа Queen содержат поле данных типа Queen. Это достаточно ясно показывает,
что объявление и выделение памяти не обязательно связаны. В противном случае для
каждого объекта Queen потребовалось бы бесконечно много памяти. Мы сравним это с
кодом для C++ и детально рассмотрим связь между объявлением и выделением памяти в
главе 12.
type
Queen = object
(* поля данных *)
row : integer;
column : integer;
neighbor : Queen;
(* инициализация *)
procedure initialize (col : integer; ngh : Queen);
(* операции *)
function canAttack (testRow, testColumn : integer) :
boolean;
function findSolution : boolean;
function advance : boolean;
procedure print;
end;
Для языка Delphi определение класса будет отличаться совсем немного (оно показано
ниже). Вариант языка для фирмы Borland позволяет разбить определение класса на
PDF created with pdfFactory Pro trial version www.pdffactory.com
открытую (public) и закрытую (private) части, а также добавить функцию-конструктор,
используемую вместо программы initialize.
TQueen = class (TObject)
public
constructor Create (initialColumn : integer;
nbr : TQueen);
function findSolution : boolean;
function advance : boolean;
procedure print;
private
function canAttack (testRow, testColumn : integer) :
boolean;
row : integer;
column : integer;
neighbor : TQueen;
end;
Псевдокод, приведенный в предыдущих параграфах, достаточно близок к варианту на
языке Pascal с двумя основными отличиями. Первое: отсутствие в языке Pascal оператора
return. Второе: необходимость сначала проверить, есть ли у ферзя сосед, перед посылкой
сообщения этому соседу. Функции findSolution и advance, приведенные ниже,
демонстрируют эти различия. (Заметим, что язык Delphi Pascal отличается от
стандартного Pascal тем, что допускает «быстрое» выполнение директив and (и) и or (или),
как и C++. Таким образом, код на языке Delphi может в одном выражении объединить
проверку существования ненулевого соседа и посылку сообщения этому соседу.)
function Queen.findSolution : boolean;
var
done : boolean;
begin
done := false;
findsolution := true;
(* проверка позиции *)
if neighbor <> nil then
while not done and neighbor.canAttack(row, column) do
if not self.advance then
begin
findSolution := false;
done := true;
end;
end;
function Queen.advance : boolean:
begin
advance := false;
(* пробуем следующую строку *)
if row < 8 then
begin
row := row + 1;
advance := self.findSolution;
end
else begin
(* не можем двигаться дальше *)
(* сдвинуть соседа к следующему решению *)
if neighbor <> nil then
if not neighbor.advance then
advance := false
else begin
row := 1;
advance := self.findSolution;
end;
PDF created with pdfFactory Pro trial version www.pdffactory.com
end;
end;
Основная программа отводит память для каждого из восьми ферзей и инициализирует их,
определяя столбец и соседа. Поскольку во время инициализации будет найдено первое
(локальное) решение, ферзи должны будут напечатать это решение. Код на языке Apple
Object Pascal, выполняющий эту задачу, показан ниже. Здесь neighbor и i — временные
переменные, используемые во время инициализации, а lastQueen — последний созданный
ферзь.
begin
neighbor := nil;
for i := 1 to 8 do
begin
(* создать и инициализировать нового ферзя *)
new (lastQueen);
lastQueen.initial (i, neighbor);
if not lastQueen.findSolution then
writeln(‘no solution’);
(* самый новый ферзь — сосед предыдущего *)
neighbor := lastQueen;
end;
(* печать решения *)
lastQueen.print;
end;
end.
Предоставляя явные конструкторы, объединяющие создание новых объектов и их
инициализацию, язык Delphi позволяет ликвидировать одну из временных переменных.
Основная программа на Delphi будет такова:
begin
lastQueen := nil;
for i := 1 to 8 do
begin
(* создать и инициализировать нового ферзя *)
lastQueen := Queen.create(i, lastQueen);
lastQueen.findSolution;
end;
// печать решения
lastQueen.print;
end;
5.3.2. Задача о восьми ферзях: C++
Наиболее существенной разницей между приведенным ранее описанием алгоритма на
псевдокоде и типичным кодом для C++ является непосредственное использование
указателей. Ниже приведено описание класса Queen. Каждый представитель класса
содержит в себе указатель на другого ферзя. Заметьте, что в отличие от Object Pascal в
языке C++ это значение должно быть объявлено как указатель на объект, а не как сам
объект.
class Queen
{
public:
// конструктор
Queen (int, Queen *);
// поиск и печать решения
bool findSolution();
PDF created with pdfFactory Pro trial version www.pdffactory.com
bool advance();
void print();
private:
// поля данных
int row;
const int column;
Queen *neighbor;
// внутренний метод
bool canAttack (int, int);
};
Как и в случае программы на языке Delphi Pascal, мы реализовали метод initialize в
конструкторе. Коротко опишем его.
Есть три поля данных. Целочисленное поле column объявлено как const. Это определяет
поле как неизменяемое. Третье поле данных имеет тип указателя; оно либо содержит
нулевое значение (то есть ни на что не указывает), либо ссылается на другого ферзя.
Поскольку инициализация осуществляется конструктором, основная программа может
просто создать восемь объектов-ферзей и потом напечатать решение. Переменная
lastQueen указывает на последнего созданного ферзя. Вначале это значение равно null-
указателю — ни на что не указывает. Затем в цикле конструируются восемь ферзей,
инициализируемых значениями столбца и предыдущего ферзя. Когда цикл закончится,
самый левый ферзь будет содержать нулевой указатель в поле neighbor, а все остальные —
указатели на своих соседей; lastQueen указывает на самого правого ферзя.
void main()
{
Queen *lastQueen = 0;
for (int i = 1; i <= 8; i++)
{
lastQueen = new Queen(i, lastQueen);
if (! lastQueen -> findSolution())
cout << "no solution\n";
}
lastQueen -> print();
}
Мы опишем только методы, иллюстрирующие важные моменты. Полное решение можно
посмотреть в Приложении A.
Конструктор должен использовать в заголовке инициализирующую конструкцию для
присваивания значения константе column, так как запрещается присваивать что-либо
полям, объявленным как const. Инициализирующая конструкция используется и для поля
neighbor, хотя мы не объявляли это поле как константу.
Queen::Queen(int col, Queen *ngh)
: column(col), neighbor(ngh)
{
row = 1;
}
Поскольку значение переменной neighbor может быть либо ссылкой на ферзя, либо
нулевым, необходима проверка, прежде чем сообщение будет послано соседу. Это
показано в методе findSolution. Использование укороченного вычисления логических
выражений и возможность выхода из середины процедуры упрощают код по сравнению с
версией на Object Pascal — в остальном же они очень похожи.
PDF created with pdfFactory Pro trial version www.pdffactory.com
bool Queen::findSolution()
{
while (neighbor && neighbor->canAttack(row, column))
if (! advance())
return false;
return true;
}
Метод advance подобным же образом должен проверять наличие соседа перед тем, как
продвигать его к следующему решению. Посылая сообщение себе, как это делается в
рекурсивном findSolution, не обязательно указывать получателя.
bool Queen::advance()
{
if (row < 8)
{
row++;
return findSolution();
}
if (neighbor && ! neighbor->advance())
return false;
row = 1;
return findSolution();
}
5.3.3. Задача о восьми ферзях: Java
Решение на языке Java во многом напоминает код на C++. Однако в Java тело метода
пишется прямо «на месте», и указания public и private помещаются в определение класса.
Ниже приводится определение класса Queen; некоторые методы опущены.
class Queen
{
// поля данных
private int row;
private int column;
private Queen neighbor;
// конструктор
Queen (int c, Queen n)
{
// инициализировать поля данных
row = 1;
column = c;
neighbor = n;
}
public boolean findSolution()
{
while (neighbor != null &&
neighbor.canAttack(row, column))
if (! advance ())
return false;
return true;
}
public boolean advance()
{
. . .
}
private boolean canAttack(int testRow, int testColumn)
{
. . .
}
PDF created with pdfFactory Pro trial version www.pdffactory.com
public void paint (Graphics g)
{
. . .
}
}
В отличие от языка C++ в Java связь со следующим ферзем определяется как объект типа
Queen, а не как указатель на Queen. Перед посылкой сообщения ферзю, определяемому
переменной neighbor, выполняется явная проверка на ненулевое значение.
Поскольку язык Java предоставляет богатое множество графических подпрограмм,
решение будет отличаться от прочих тем, что окончательная расстановка ферзей будет
нарисована на экране. Метод paint рисует ферзя, потом изображает соседей.
class Queen
{
. . .
public void paint (Graphics g)
{
// x, y — левый верхний угол
int x = (row — 1) * 50;
int y = (column — 1) * 50;
g.drawLine(x+5, y+45, x+45, y+45);
g.drawLine(x+5, y+45, x+5, y+5);
g.drawLine(x+45, y+45, x+45, y+5);
g.drawLine(x+5, y+35, x+45, y+35);
g.drawLine(x+5, y+5, x+15, y+20);
g.drawLine(x+15, y+20, x+25, y+5);
g.drawLine(x+25, y+5, x+35, y+20);
g.drawLine(x+35, y+20, x+45, y+5);
g.drawLine(x+20, y+20, 10, 10);
// затем рисуем соседа
if (neighbor != null)
neighbor.paint(g);
}
}
Графические программы рисуют маленькую корону, выглядящую вот так:
В языке Java нет ни глобальных переменных, ни «безклассовых» функций. Как мы
опишем более детально в главе 8, программа начинается с определения подкласса
системного класса Applet и переопределения некоторых методов. В частности, метод init
используется для инициализации приложения, а метод paint — для перерисовки экрана.
Мы также определим метод mouseDown, вызываемый при нажатии кнопки мыши, чтобы
заставить программу переходить к следующему решению. Назовем класс нашего
приложения QueenSolver и определим его так:
public class QueenSolver extends Applet
{ private Queen lastQueen;
public void init()
{ lastQueen = null;
for (int i = 1; i <= 8; i++)
PDF created with pdfFactory Pro trial version www.pdffactory.com
{ lastQueen = new Queen(i, lastQueen);
lastQueen.findSolution();
}
}
public void paint(Graphics g)
{ // рисуем доску
for (int i = 0; i <= 8; i++)
{
g.drawLine(50 * i, 0, 50 * i, 400);
g.drawLine(0, 50 * i, 400, 50 * i);
}
// рисуем ферзей
lastQueen.paint(g);
}
public boolean mouseDown(java.awt.Event evt, int x,
int y)
{
// найти и напечатать следующее решение
lastQueen.advance();
repaint();
return true;
}
}
Заметьте, что класс приложения должен быть объявлен как public, чтобы быть доступным
в основной программе.
5.3.4. Задача о восьми ферзях: Objective-C
Описание интерфейса нашего класса Queen таково:
@interface Queen : Object
{ /* поля данных */
int row;
int column;
id neighbor;
}
/* методы */
- (void) initialize: (int) c neighbor: ngh;
- (int) advance;
- (void) print;
- (int) canAttack: (int) testRow column:
(int) testColumn;
- (int) findSolution;
@end
Каждый ферзь имеет три поля данных: строку, столбец и ферзя-соседа. Последнее
объявлено с типом id. Это указывает, что значением переменной будет объект, хотя и не
обязательно ферзь.
В действительности мы можем использовать бестиповую сущность переменных в языке
Objective-C себе во благо. Применим технику, которая невозможна или, по крайней мере,
не так проста в языках со строгими ограничениями на тип (такими, как C++ или Object
Pascal). Вспомним, что самый левый ферзь не имеет соседа. В решении на языке C++
признаком этого служило нулевое значение переменной, содержащей указатель на соседа,
для самого левого ферзя. В данном решении мы вместо этого создаем новый класс —
караульное (sentinel) значение. Самый левый ферзь будет указывать на это караульное
значение, тем самым обеспечивая действительного соседа каждому ферзю.
PDF created with pdfFactory Pro trial version www.pdffactory.com
Караульные величины часто используются как маркеры конца; их можно обнаружить в
алгоритмах, работающих со списками, такими как наш список ферзей. Различие между
объектно-ориентированным «караулом» и более традиционными проверками состоит в
том, что первый может быть активным — у него есть поведение, то есть он может
отвечать на запросы.
Каково должно быть поведение караульных величин? Вспомним, что ссылки на соседа в
нашем алгоритме используются двояко. Во-первых, чтобы убедиться, что интересующая
нас позиция не атакована; караульная величина на такой запрос всегда должна отвечать
отрицательно, поскольку она не может ничего бить. Второе использование ссылок на
соседа — в рекурсивном вызове процедуры print. В этом случае караульная величина
просто ничего не делает, так как не имеет никакой информации о решении.
Объединяя вместе все эти рассуждения, приходим к следующей реализации нашего
«караульного ферзя»:
@implementation SentinelQueen : Object
- (int) advance
{
/* ничего не делаем */
return 1;
}
- (int) findSolution
{
/* ничего не делаем */
return 1;
}
- (void) print
{
/* ничего не делаем */
}
- (int) canAttack: (int) testRow column:
(int) testColumn;
{
/* не можем атаковать */
return 0;
}
@end
В полном решении есть часть, реализующая SentinelQueen, но к ней нет интерфейса. Это
допустимо, хотя компилятор выдаст предупреждение, поскольку такая ситуация
несколько необычна.
Использование караульного объекта позволяет методам класса Queen просто посылать
сообщения соседу без предварительного изучения, является ли данный ферзь самым
левым. Например, в методе canAttack:
- (int) canAttack: (int) testRow column:
(int) testColumn
{ int columnDifference;
/* можем бить ту же строку */
if (row == testRow)
return 1;
columnDifference = testColumn — column;
if ((row + columnDifference == testRow) ||
(row — columnDifference == testRow))
return 1;
return [ neighbor canAttack:testRow column:
PDF created with pdfFactory Pro trial version www.pdffactory.com
testColumn ];}
Внутри метода посылка сообщения самому себе осуществляется с помощью
псевдопеременной self:
- (void) initialize: (int) c neighbor: ngh
{
/* установить поля — константы */
column = c;
neighbor = ngh;
row = 1;
}
- (int) findSolution
{
/* цикл, пока не найдем решение */
while ([neighbor canAttack: row and: column ])
if (! [self advance])
return 0; /* возвращаем false */
return 1; /* возвращаем true */
}
Остальные методы аналогичны и здесь не рассматриваются.
5.3.5. Задача о восьми ферзях: Smalltalk
Решение задачи о восьми ферзях на языке Smalltalk во многих отношениях похоже на
Objective-C. Как и последний, язык Smalltalk учитывает тот факт, что самый левый ферзь
не имеет соседа, вводя специальный караульный (sentinel) класс. Его единственная цель в
том, чтобы предоставить получателя сообщений, посланных самым левым ферзем.
Караульная величина является единственным представителем класса SentinelQueen
(подкласс класса Queen), который реализует следующие три метода:
advance
" караульный ферзь не атакует "
false
canAttack: row column: column
" караульный ферзь не может атаковать "
false
result
" возвращаем пустой список в качестве результата "
List new
Единственное различие между версиями на Objective-C и Smalltalk в том, что программа
на языке Smalltalk возвращает результат как список величин, а не выводит их на печать.
Техника вывода на печать довольно хитро устроена в Smalltalk и различается от
реализации к реализации. Возвращая список, мы можем отделить эти различия от
основных методов.
Класс Queen является подклассом класса Object. Представители класса Queen содержат
три внутренние переменные: row (строка), column (столбец) и neighbor (сосед).
Инициализация осуществляется в методе setColumn : neighbor:.
setColumn: aNumber neighbor: aQueen
" инициализация полей данных "
column := aNumber.
neighbor := aQueen.
PDF created with pdfFactory Pro trial version www.pdffactory.com
row := 1.
Метод canAttack отличается от аналогичного метода для языка Objective-C только
синтаксисом:
canAttack: testRow column: testColumn |
columnDifference |
columnDifference := testColumn — column.
((row = testRow) or:
[ row + columnDifference = testRow]) or:
[ row — columnDifference = testRow])
ifTrue: [ true ].
neighbor canAttack: testRow column: testColumn
Вместо того чтобы проверять условие на отрицание, язык Smalltalk предоставляет явный
оператор ifFalse, используемый в методе advance:
advance
" сначала попробуем следующую строку "
(row < 8)
ifTrue: [ row := row + 1. self findSolution].
" не можем двигаться дальше, сдвигаем соседа "
(neighbor advance)
ifFalse: [ false ].
" начнем со строки 1 "
row := 1.
self findSolution
Цикл while в языке Smalltalk должен использовать блок при проверке условия, как в
следующем примере:
findSolution
[ neighbor canAttack: row column: column ]
whileTrue: [ self advance ifFalse: [ false ] ].
true
Для получения списка окончательных позиций используется рекурсивный метод.
Вспомним, что караульная величина создает пустой список в ответ на сообщение result:
result
neighbor result; addLast: row
Решение будет получено с помощью вызова следующего метода, не являющегося частью
класса Queen и относящегося к некоторому другому классу, например, такому как Object:
solvePuzzle | lastQueen |
lastQueen := SentinelQueen new.
1 to: 8 do: [:i | lastQueen := (Queen new)
setColumn: i neighbor: lastQueen.
lastQueen findSolution ].
lastQueen result
Решение задачи о восьми ферзях, построенное без применения караульной величины,
описано в моей более ранней книге по языку Smalltalk [Budd 1987].
Упражнения
PDF created with pdfFactory Pro trial version www.pdffactory.com