Столкнулся с такой проблемой, что молодым программистам, которые только начинают изучение языков, алгоритмы вызывают больше трудностей, чем синтаксис языка. Если сам синтаксис и концепцию объяснит преподаватель по конкретному языку, то алгоритмы вам придется придумывать самим. Исключением из правил могут быть только специализированные технические специальности в ВУЗах, где преподают именно алгоритмы.
При том, что алгоритм решения может быт очень простым многие не знают как подойти к решению задачи. Я рассмотрю пример проверки победы в игре крестики-нолики, но на поле 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. Рекомендую смотреть его уже после того, как вы написали свои функции на основе этой статьи.
ссылка на оригинал статьи https://habrahabr.ru/post/329300/
Добавить комментарий