Эти сложные крестики-нолики
Или как проверить победу в десять строк
Аннотация
Каждый раз, преподавая первый уровень основ Java Core я сталкиваюсь с одной и той же проблемой: невозможно на третьем уроке написать логику проверки победы крестика (или нолика), используя только изученные инструменты. Это не совсем верно. И однажды у меня хватило красноречия объяснить логику происходящего одному из студентов, поэтому приведу часть нашей беседы, чтобы другим тоже стало немножко понятнее. И, да, тут используются только те инструменты, которые были изучены на первых двух уроках (переменные, массивы, циклы и условия).
Действующие лица: студент(С) и преподаватель(П).
Пролог:
С: Доброе утро! Чувствую, что без Вас мне крестики-нолики не сдадутся... буду рассуждать вслух…
П: Доброе.
С: Итак…. нужно сделать проверку одной линии, одна линия состоит из 3 клеточек (но может варьироваться), нужно проверить каждую из них....
П: Давайте без кода пока что. Что мы делаем в жизни, когда хотим проверить линию?
С: Смотрим что там… Сравниваем свой знак со знаками, которые находятся в соседних клеточках
П: Мы же не можем посмотреть "всю линию целиком сразу", если она, например, длиной в сто символов, физически, глазами, на реальном бумажном поле
С: Ну нет... у нас есть условие, что 3 клеточки соседние дают выигрыш… значит смотрим только соседние 3....
П: Сразу подумаем чуть вперёд, выигрышная длина может быть не 3 клеточки, и поставить выигрышный крестик мы можем не только в самую середину последовательности. Поэтому надо немного универсализировать. Давайте думать про сто крестиков подряд для победы... для трёх алгоритм будет такой же.
С: Если у нас сто клеточек и нам надо знать сколько клеточек дадут выигрыш... Ставим крестик и проверяем вправо и влево есть ли там крестики так чтобы набралась выигрышное количество....
П: Сто и дадут. Сто крестиков подряд для победы. Поле тысяча на тысячу)
С: Тогда надо чтобы посчиталось количество крестиков в соседних клеточках...
П: А если последний, выигрышный, поставился на самый край последовательности, и с одной из сторон у него ничего нет?
С: Надо в обе стороны считать...
П: То есть стоп, погодите, Вы хотите сказать, что поставив сотый крестик, вы глазами пойдёте считать в обе стороны от него? Запомните где его поставили, посчитаете в одну сторону, потом от крестика пойдёте в другую, и сложите?
С: Нет, игра должна посчитать....
П: Мы не говорим об игре) мы говорим о крестиках-ноликах на бумаге, об алгоритме, который Вы используете у себя в голове)
С: Если там ряд крестиков, без ноликов, тогда ясно что ход правильный, но как посчитать их количество не считая в уме?
П: Почему не считая в уме-то? Как раз про подсчёт в уме мне и интересно. Мы же программируем, то есть говорим компьютеру, что делать, а самый простой способ - повторить то, что у нас в голове, поэтому я и хочу для начала выудить у Вас информацию о том, что именно находится у Вас в голове)))
С: Тогда получается, что надо посчитать каждый крестик до ближайшего нолика...
П: Итак) как мы считаем в уме сто крестиков подряд?
С: Я бы взяла карандаш и каждый посчитала тыкая в него, чтобы не сбиться...
П: Вот! И это абсолютно логичное поведение, теперь давайте скажем программе, что ей надо тоже так сделать.
С: Ей надо пройти по строке, проверить и посчитать количество символов....
П: Дадим ей (программе) в руки (в код) карандаш (цикл) и заставим посчитать подряд все клетки на какой нибудь горизонтали, на предмет наличия там трёх, к примеру, крестиков
С: Ей нужно условие... если она видит 3 клетки подяд с крестиками, тогда комбинация выигрышная....
П: Да, то есть она идёт по клеткам. если вдруг видит не крест - говорит «всё плохо», а если досчитала до сотого креста - говорит, что всё хорошо
С: Я не знаю, как записать в if, что количество должно равняться переменной winLength
П: Бежать циклом до этого количества? Пока что - проверяем линию. одну
С: Ставим крестик и считаем - есть рядом крест +1, еще есть - еще +1, вместе с моим крестом будет три, а это выигрыш! Что если do (+1) while не достигнет 3 клеток?
П: Это и есть цикл for, Просто внутри него надо подумать получше. Если дошли до конца for - это выигрыш, то есть после for мы возвращаем true
С: <здесь некоторые творческие муки>
П: Вернулись к карандашику и бумажке. Как Вы понимаете, что не получилось сложить из крестиков линию нужного размера?
С: Когда посчитала все 100 крестиков и среди них нет нолика
П: То есть Вы всегда строго считаете до ста крестиков, и встретив где то на середине нолик перестаёте считать?
С: Перестаю
П: Давайте программе тоже скажем переставать. Должно получиться «иди по линии, если встретила не крестик - скажи что не получилось, если же дошла до конца линии - скажи что линия собралась». жду код проверки одной линии)
С: <здесь некоторые творческие муки>
П: Вы уже достаточно в отчаянии, чтобы я дал правильный ответ?
С: Давайте…
Основное действие:
П: Возвращаемся к самому началу: что мы тут делать должны? Проверять одну линию, так? Цикл идущий до 3 нас устраивает, потому что это выигрышная длина. Внутри цикла мы перебираем каждый символ на нашем пути, и это тоже верно, значит после цикла, если мы нигде не вывалились, нам надо вернуть тру
private boolean checkLine(winLen) {
fori (< winlen) {
}
return true;
}Пока что, получилось вот так. Теперь думаем что у нас внутри цикла, по каждой клеточке? И приходим к выводу, что если мы встретили не крестик, то надо сказать - линия не удалась
private boolean checkLine(sym, winLen) {
for (i = 0; i < winlen; i++) {
if (field[0][i] != sym)
return false;
}
return true;
}Получается так, да? Это мы научились проверять горизонталь, одну, которая на 0-й координате по игреку лежит. Теперь расширим нашу проверку линии чтобы она умела ещё и вертикальные, например, проверять… Получается, что нам надо вводить понятие "куда считать". так?
С: четыре стороны...
П: верно
private boolean checkLine(sym, winLen, shiftY, shiftX) {
for (i = 0; i < winlen; i++) {
if (field[i][i] != sym)
return false;
}
return true;
}
}Получается так. мы считаем i, и надо как-то к нему применить значение - в какую сторону идти... снаружи, вызов будет туда передавать например (по y не смещаемся, то есть * 0, по х смещаемся, то есть * 1, или по у смещаемся не вниз, а в обратную сторону, то есть * -1). Думаем, как в получившийся цикл вложить shiftX и shiftY, и там будет if (field[i * shiftY][i * shiftX] != sym) return false;
В разные (любые, в двухмерной системе координат) стороны гулять по одной линии научились, теперь надо подумать о том, что проверка может начинаться не только в координате 0,0 а в любой другой клетке, поэтому у нас добавляется понятие "точка старта проверки", верно?
С: Да, которая будет считываться с того места в которое поставили символ...
П: Не обязательно. Если начинаем проверку от последнего поставленного символа - сразу становится сложнее, потому что считать надо в 8 сторон, да ещё и учитывать, не был ли последний Х в середине линии, поэтому я сразу в условии задачи и сказал, что проверку надо осуществлять только в 4 стороны, но из КАЖДОЙ клетки поля. Получили сигнатуру проверки линии. из каких координат, какой символ, в каком направлении смотрим
private boolean checkLine(x, y, sym, winLen, shiftY, shiftX)
И отсюда получается, что вот сюда эти координаты и положили
if (field[y + i * shiftY][x + i * shiftX] != sym) return false;
Таким образом метод проверки одной линии у нас готов. Остаётся только запустить этот метод для каждой клетки поля, во всех 4-х нужных направлениях, предварительно проверив, не выйдет ли проверка (выигрышная длина) за пределы этого самого поля (fieldSizeX, fieldSizeY)
Эпилог:
С: Это очень сложно для меня сейчас... у меня впечатление, что эту игру ставят в начале курса как проверку на крепость мотивации изучать программирование…
П: На самом деле это задание дано только лишь для того, чтобы проверить, насколько детально Вы можете рассуждать. Для новичка очень сложно реально осознать, что 80% программирования происходит не в IDEA или другом редакторе кода, а в анализе проблемы, составлении алгоритма, формулировании решения
С: Вот детальность рассуждения наверное самое трудное, мы многое делаем на автомате, не задумываясь почему и зачем... даже не выделяя это в своем внимании...
П: А программе такие вещи надо объяснять, она же ничего не умеет, и опыта игры в крестики-нолики у неё нет
С: Ну, да. Спасибо вам большое!
П: Не за что.