Столкнулся с такой проблемой, что молодым программистам, которые только начинают изучение языков, алгоритмы вызывают больше трудностей, чем синтаксис языка. Если сам синтаксис и концепцию объяснит преподаватель по конкретному языку, то алгоритмы вам придется придумывать самим. Исключением из правил могут быть только специализированные технические специальности в ВУЗах, где преподают именно алгоритмы.
При том, что алгоритм решения может быт очень простым многие не знают как подойти к решению задачи. Я рассмотрю пример проверки победы в игре крестики-нолики, но на поле 6х6 и блоком подряд заполненных значений равному 4-м.
На самом деле, здесь представлен универсальный алгоритм, только вместо переменных я использовал константы. И это практически не зависит от языка, котором эта проверка осуществляется. Я предлагаю начинающим программистам сначала решить задачу графически, а затем уже перевести ее на тот или иной язык. Для создания этого алгоритма подойдет листок в клетку и ручка.
Итак, у нас есть поле 6х6.
Блок последовательно заполненных элементов, который достаточен, чтобы выиграть, равен 4-м.
Думаю, что теперь (всего лишь поле двух рисунков) стало намного понятнее, как решить эту задачу.
Фактически мы должны решить 2 независимые задачи:
- Найти все заполненные последовательности в блоке 4х4.
- Найти все квадраты 4х4 в квадрате 6х6.
1. Найти все заполненные последовательности в блоке 4х4
Почему проверяем блок 4х4? Все просто в нем возможно только 2 диагонали такой размерности, которая нам нужна.
Используя двоичную логику (1&1=1 и 1&0=0) мы можем легко сделать проверку циклами. Для этого нам нужна 1 переменная для каждой диагонали. Пусть toright – логическая переменная в которую пишем результат проверки диагонали сверху слева вниз направо. И toleft для проверки диагонали сверху справа вниз налево.
Первоначально выставим значение true для этих переменных. Дальше мы сравниваем каждую клетку в диагонали с символом «Х» или «О». Конечно, мы делаем это 2-мя вызовами либо все сравниваем с «Х», либо все с «О».
Каждую клеточку диагонали мы сравниваем с нашим символом и получаем результат (true) или (false). Затем делам логическую операцию (&) между полученным результатом и нашей toright. Результат этой операции пишем опять в toright. Если на каком-то этапе мы получим результат (false), то все дальнейшие toright всегда будут равны (false). Это следует из правила логических операций (1&0=0).
Напишем это на Jave:
boolean checkDiagonal(char symb) {
boolean toright = true; // установили логическое значение 1
for (int i=0; i<4; i++) { // Блок от 0 до 3
toright = toright & (map[i][i] == symb);
}
// Дальше мы вернули (true), если во всех клетках нам встретились символы symb
if (toright) return true;
// или вернули (false), если встретился хоть один символ, отличный от symb
return false;
}Собственно вот в этой строчке
toright = toright & (map[i][i] == symb))и есть вся логика.
Краткая запись выглядит так:
toright &= (map[i][i] == symb))Получаются только 2 результата работы условия:
toright = toright & 0
или
toright = toright & 1Для 2-х диагоналей, полный код функции будет выглядеть так:
/** Проверяем диагонали */
boolean checkDiagonal(char symb) {
boolean toright, toleft;
toright = true;
toleft = true;
for (int i=0; i<4; i++) {
toright &= (map[i][i] == symb);
toleft &= (map[4-i-1][i] == symb);
}
if (toright || toleft) return true;
return false;
}Полный аналог делается для проверки вертикалей и горизонталей, только циклы меняются.
/** Проверяем горизонтальные и вертикальные линии */
boolean checkLanes(char symb) {
boolean cols, rows;
for (int col=0; col<4; col++) {
cols = true;
rows = true;
for (int row=0; row<4; row++) {
cols &= (map[col][row] == symb);
rows &= (map[row][col] == symb);
}
// Это условие после каждой проверки колонки и столбца
// позволяет остановить дальнейшее выполнение, без проверки
// всех остальных столбцов и строк.
if (cols || rows) return true;
}
return false;
}Собственно это и есть решение для блока 4х4. Как видно из кода, для другого блока нужно только поменять 4 в цикле на другое число, или написать вместо числа имя переменной. Причем эту переменную вы можете сделать как глобальной видимости, так и передать в функцию, например так:
boolean checkLanes(char symb, int block)…..2. Найти все квадраты 4х4 в квадрате 6х6
Собственно, их не так много. Начиная с позиции [0,0], [1,0] и [2,0] для первой строки квадрата, [0,1], [1,1] и [2,1] для второй, [0,2], [1,2] и [2,2] для третьей. Дальше квадрат 4х4 выйдет за границы квадрата 6х6.
Такой перебор координат вполне можем сделать циклами:
boolean checkWin(char symb) {
for (int col=0; col<3; col++) {
for (int row=0; row<3; row++) {
// Вызываем методы проверки и если хоть один блок заполнен,
// то игрок, который проставляет это символ, выиграл
// иначе продолжаем для другого смещения
if (checkDiagonal(symb, col, row) || checkLanes(symb, col, row)) return true;
}
}
// Все подквадраты в квадрате проверены. 4-х последовательностей
// подряд не выявлено. Значит еще не победа.
return false;
}Тут нам придется немного модифицировать методы checkDiagonal и checkLanes, поскольку мы должны проверять квадрат 4х4 с соответствующим смещением.
int size = 6; // размер квадратного поля
int block = 4; // размер блока
boolean checkLanes(char symb, int offsetX, int offsetY) {
boolean cols, rows;
for (int col=offsetX; col<block+offsetX; col++) {
cols = true;
rows = true;
for (int row=offsetY; row<block+offsetY; row++) {
cols &= (map[col][row] == symb);
rows &= (map[row][col] == symb);
}
if (cols || rows) return true;
}
return false;
}Начинающим программистам я бы рекомендовал самим модифицировать код checkDiagonal, т.к. это позволит лучше понять принцип работы.
И еще один совет. В настоящий момент имеется огромное количество реализаций различных алгоритмов в сети на разных языках. Если вы хотите научиться думать, то смотрите именно принципы решений (алгоритмы), не привязанные к языкам. Готовые решения не позволят вам быстро научиться выбирать наиболее оптимальный вариант решения. Очень часто, переписать готовое решение с одного языка на другой, можно не понимая принципа решения задачи. Где-то это вам поможет, а где-то может сделать дальнейшее развитие программы невозможным без изменения ее логики.
Сначала я рекомендую попробовать написать проверку самостоятельно. Шаблон игры можно забрать здесь. Там уже есть заголовки функций, которые я описал в статье. Осталось скопировать в шаблон часть моего кода и чуть-чуть его модифицировать. А вот здесь можно скачать полный рабочий код на Java. Рекомендую смотреть его уже после того, как вы написали свои функции на основе этой статьи.
Автор: SecondUniverse
