|
© 2018
Легалов А.И.
Исходные тексты рассмотренных программ (1.5 кб)
Пример к заметке о недостатках процедурного подхода демонстрирует случай, когда процедурное решение может оказаться удобнее
Ситуации, когда процедурный подход оказывается предпочтительнее, можно продемонстрировать на простом примере, коим является задача о восьми ферзях, формулировка которой звучит следующим образом: «Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого». Одно из решений данной задачи представлено на рисунке 1.
Рисунок 1 – Одно из решений задачи о восьми ферзях
Однако в данном случае интерес представляет не столько алгоритм решения задачи, сколько те технологические подходы, которые определяют его формирование.
Процедурное решение
Один из вариантов, связанный с пошаговой разработкой программ, был сформулирован Н. Виртом [WirthNiklaus Wirth. Program Development by Stepwise Refinement Источник: Communications of the ACM, Vol. 14, No. 4, April 1971, pp. 221-227.]. Формирование алгоритма он определил как пошаговое решение в котором на первом этапе было приведено следующее описание:
repeat
Generate the next element of A and call it x
until p(x) V (no more elements in A);
if p(x) then x = solution
В ходе написания монографий, которые в том числе неоднократно переводились и на русский язык, данный алгоритм был представлен как для формирования одного, так и множества решений на авторских языках программирования Pascal, Modula-2, Oberon [Вирт1985Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985., Вирт1989Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – М.: Мир, 1989. – 360с., Вирт2016Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона. М.: ДМК Пресс, 2016. 272 с.]. Ниже показан, аналогичный код на C++, написанный для получения одного решения этой задачи.
// Задача о 8 ферзях из книги Н. Вирта.
// Алгоритмы и структуры данных: Пер. с англ. –
// М.: Мир, 1989. – 360с
#include <iostream>
using namespace std;
// массив для отметки занятости горизонталей
bool a[8];
// массив для отметки занятости побочных диагоналей
bool b[15];
// массив для отметки занятости прямых диагоналей
bool c[15];
// массив для фиксации строк
int x[8];
void Try(int i, bool& q) {
int j = -1;
do {
j += 1;
q = false;
if(a[j] && b[i+j] && c[i-j+7]) {
x[i] = j;
// Ферзь бьет горизонталь и диагонали
a[j] = b[i+j] = c[i-j+7] = false;
if(i < 7) {
Try(i+1, q);
if(!q) {
a[j] = b[i+j] = c[i-j+7] = true;
}
} else {
q = true;
}
}
} while(!(q || (j == 7)));
}
int main()
{
int i;
bool q;
for(i = 0; i < 8; i++)
a[i] = true;
for(i = 0; i < 15; i++)
b[i] = c[i] = true;
Try(0, q);
for(i = 0; i < 8; i++)
cout << x[i]+1 << " ";
cout << endl;
return 0;
}
Основной акцент сделан на формировании абстракций, непосредственно не связанных с предметной областью. Простые булевские массивы точно и компактно описывают шахматную доску, никоим образом при этом не воспроизводя ее геометрию. При постановке ферзя не проверяются все возможные бьющиеся клетки, а только те, которые связаны с координатами для его установки. Истинное значение элемента любого массива показывает, что соответствующие диагонали и вертикали не бьются. В этом случае ферзя можно установить, отметив значением false, занятые горизонталь, вертикаль и диагональ.
Рекурсия позволяет постепенно устанавливать новых ферзей, если для данной горизонтали имеется свободная вертикаль (i < 7). В противном случае следует откат к предыдущему ферзю с поиском для него другого свободного места. Весь код занимает 20 строк.
Объектно-ориентированное решение
Заимствовано из книги Тимоти Бадда [Badd1997Бадд Т. Объектно-ориентированное программирование в действии / Перев. с англ. — СПб.: Питер, 1997. ISBN 5-88782-270-8]. В отличие от предшествующего варианта вход в решение начинается с традиционного неформального анализа в терминах предметной области в рамках одного и возможных сценариев поведения объектов, что в конечном счете приводит по сути к прямому моделированию ситуации на доске. Цитирую:
"Как определить поведение каждого ферзя, чтобы группа ферзей, работающих совместно, могла прийти к решению? Первое наблюдение состоит в том, что в любом случае никакие два ферзя не могут занимать один столбец и, следовательно, все столбцы заняты. Поэтому мы можем сразу присвоить каждому ферзю определенный столбец и свести задачу к более простой — найти соответствующие строки.
Чтобы прийти к решению, ферзи должны взаимодействовать друг с другом. Поняв это, мы можем сделать следующее важное наблюдение, которое очень упростит нашу задачу, а именно: каждый ферзь должен знать только о своем соседе слева. Таким образом, данные о ферзе будут состоять из трех значений: столбец, который остается неизменным; строка, меняющаяся в ходе решения; и сосед слева."
В результате написанный код полностью отображает мышление "неопытного ферзя", который интересуется у коллег: а на правильное ли место он пытается встать? А после установки его интеллект резко повышается до уровня, позволяющего подсказать правильность установки на последующих ферзей.
Программа становится отображением модели мышления, включая и обертку в классы, что в целом ведет к получению эмпирического частного решения.
// Задача "Восемь ферзей", язык С++
// Автор: Тимоти Бадд,
// университет штата Орегон, 1996
#include <iostream>
using namespace std;
class queen {
public:
// конструктор
queen (int, queen *);
// найти и напечатать решения
bool findSolution();
bool advance();
void print();
private:
// поля данных
int row;
const int column;
queen * neighbor;
// внутренний метод
bool canAttack (int, int);
};
queen::queen(int col, queen * ngh) : column(col), neighbor(ngh)
{
row = 1;
}
bool queen::canAttack (int testRow, int testColumn)
{
// проверка горизонталей
if (row == testRow)
return true;
// проверка диагоналей
int columnDifference = testColumn - column;
if ((row + columnDifference == testRow)
|| (row - columnDifference == testRow))
return true;
// попробовать соседа
return neighbor &&
neighbor->canAttack(testRow, testColumn);
}
bool queen::findSolution()
{
// проверить позицию, не атакуют ли соседи
while (neighbor && neighbor->canAttack (row, column))
if (! advance ())
// return false;
// решение найдено!
return true;
}
bool queen::advance()
{
if (row < 8) {
row++;
return findSolution();
}
if (neighbor && ! neighbor->advance())
return false;
row = 1;
return findSolution ();
}
void queen::print()
{
if (neighbor)
neighbor->print();
cout << "column " << column <<
" row " << row << '\n';
}
int 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();
return 0;
}
Почему данное решения является частным? Потому, что можно использовать другие сценарии. Например, когда выставляемый на доску ферзь обладает интеллектом и сам проверяет местоположение других ферзей, а уже стоящие на ней его теряют. Можно также в качестве основы взять умную шахматную доску, которая сама манипулирует ферзями. То есть, можно выстраивать разнообразные модели взаимодействия, сопоставляя варианты, к примеру, с жизненными ситуациями.
В данном случает речь не идет о том какой из подходов лучше или хуже. Используя этот пример я хочу показать, что зачастую модели предметной области могут влиять на выбор парадигм, используемых при разработке ПО. Зачастую, при этом (в который раз...) предпочтительнее использовать мультипарадигменный стиль.
Список используемых источников
Niklaus Wirth. Program Development by Stepwise Refinement Источник: Communications of the ACM, Vol. 14, No. 4, April 1971, pp. 221-227. Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – М.: Мир, 1989. – 360с. Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона. М.: ДМК Пресс, 2016. 272 с. Бадд Т. Объектно-ориентированное программирование в действии / Перев. с англ. — СПб.: Питер, 1997. ISBN 5-88782-270-8
|