hm_dmitryВ данном цикле реализован метод итераций.
Вот этот первый fill_up_down() пишем для проверки первой клетки, верно ?
Метод итераций строится на трёх понятиях: M, P, T.
M - множество элементов цикла
P - предикат выхода из цикла
T - преобразование шага цикла
Тут теория из книжки Кушниренко-Лебедева “Программирование для математиков”
Метод итераций:
M - некоторое множество
P: M -> {да, нет} - предикат на M, отображающий M на да и нет
M \ P = {x прин. M: P(x) = нет} - множество элементов x прин. M, для которых P(x) = нет
Т: M \ P -> M - некоторое преобразование
Начиная с x0 прин. M, x1 = T(x0), x2 = T(x1), ..., xn = T(xn - 1), ...
Требуется найти элемент xi прин. M, такой что P(xi) = да.
То есть можно несколько разных правильных циклов написать для решения одной и той же задачи.
hm_dmitryСначала мы делаем так:
Возможно ли все это дело вписать внутрь while ?
1) В качестве множества M мы берём множество всех клеток в ряде;
2) В качестве предиката P(m) мы берём вопрос о клетке “является ли клетка m закрашенной сверху/снизу и последней в ряде?”;
3) В качестве преобразования T(m) мы берём шаг на следующую от m клетку справа и закрашивания пространства над и под ней.
Дальше мы задаёмся вопросом “что будет, если во множестве M будет одна клетка?”, ответ - будет отказ из-за невозможности выполнить шаг вправо при преобразовании T, так как первая клетка не закрашена и P(m) даст ложь. Если же мы её закрасим, то произойдёт выход из цикла, так как P(m) даст истину.
Поэтому устанавливаем m0 = закрашенная клетка
T(m0) = m1, где m1 - закрашенная клетка
T(m1) = m2, где m2 - закрашенная клетка
…
T(m n-1) = m n, где m n - закрашенная клетка, а P(m n) = да
Мы могли бы выбрать другие M, P и T, где преобразование T(m) сначала бы всё закрашивало для клетки m, а потом переходило вправо, а P(m) проверяло бы не является ли текущая клетка последней в ряде. Но тогда нужно было бы закрашивать последнюю клетку сверху/снизу после цикла, потому что цикл бы заканчивался на незакрашенной клетке.
Что лучше, такой вариант или такой, определяется тем, как можно разные алгоритмы присоединять друг к другу. При тех M, P и T, которые я выбрал, мы в конце цикла получаем возможность делать дальше что угодно (возвращаться влево к началу строки, переходить на следующую строку вниз и так далее). Если же закончить цикл на недокрашенной клетке, то после цикла ты не можешь никуда переходить, а должен сначала всё докрасить и только потом переходить.
Просто представь, что таких рядов, которые нужно обработать, не один, а десяток друг под другом. В таком случае первый вариант выбранных M, P и T предпочтительнее, так как после окончания цикла ты свободен для любых следующих действий.
