Чтобы научиться мыслить как программист, надо научиться мыслить как не программист

Это как бы ответ на статью lxsmkv «Задача о переправе». Наиболее запоминающаяся часть той статьи — это огромная (в сопоставлении с сложностью задачи) таблица, в которой выражена модель задачи.

Попробуем придумать что-то попроще.

1. Условие

У нас есть волк, коза и капуста. Их надо переправить на другой берег. Переправляет человек (перевозчик). Сложность в том, что волк съедает козу, а коза — капусту, если рядом нет человека. Кроме того, переправлять можно только по одному (в лодке только одно место для груза).

2. Идея решения

Теперь оцифруем задачу, то есть представим её в виде чисел и операций с ними. Мы должны описать распределения волка, козы и капусты по берегам (конфигурации) и действия с ними. Итак, у нас есть словесная формулировка условия задачи. Я хочу в модели совместить наглядность картинки с абстрактностью числа. То есть модель должна быть наглядна, чтобы быть понятной человеку, и абстрактной, чтобы быть понятной машине.

Я хочу её представить в таком виде, чтобы она была легко понятна мне и чтобы она была легко программируема.

Легче всего воспринимаются изображения (с одного взгляда). Легче всего программируются действия с числами. Таким образом, я хочу, чтобы моя модель совмещала в себе свойства как изображения, так и числа. Причём первично число, так как в перспективе предполагается программирование. То есть нам нужно не просто какое-то число, а такое, визуальный образ которого будет отражать задачу (и ход её решения). Изобразим условие задачи в виде картинки. Действие «съедает» изобразим стрелкой.

Кто-то увидит в этой картинке пищевую цепочку, кто-то ориентированный граф. Но всё это не имеет значения. Для нас важно, что некоторые пары запрещены. И какие именно пары, определяется их положением на картинке.

А раз так, то становится совершенно безразличным, кто из них кто и кто кого ест. Важно, как легко заметить, что запрещены соседние пары. Следовательно, рисунок можно сделать схематичным, изобразив и волка, и козу, и капусту одинаковыми значками.

Теперь нам надо показать распределение участников по берегам.

Нетрудно заметить, что информация, содержащаяся в правой части схемы, дублируется в левой части. Действительно, участники не исчезают из задачи и не появляются вновь. Каждый из них находится или на левом, или на правом берегу. Следовательно, достаточно одной правой части схемы.

В такой схеме содержится вся информация о любом распределении объектов, возникающем в ходе решения задачи. Что это за объект определяется местом (позицией), занимаемым им на схеме, а на каком он берегу определяется тем, занято место или пусто.

Теперь возьмёмся за числа. Все современные системы счисления позиционные, то есть функция цифры в числе определяется её положением в этом числе. То есть разрядом. И каждый разряд может иметь несколько значений.

Теперь с каждым разрядом свяжем объект задачи. А значений каждого разряда нам понадобится два. Пусть первый разряд – это капуста, второй – коза, а третий – волк. В каждом разряде нам понадобятся два значения: 1 – стартовый берег, 0 – финишный берег.

Получается, что для описания любой конфигуации нам нужно трёхзначное двоичное число. Например, 111 – стартовая конфигуация, 000 – финишная.

То же самое можно сказать и о кодировании хода числом. Тоже необходимо трёхзначное двоичное число, в котором разряд – это участник, а значение разряда кодирует действие (1 – перевезти, 0 – нет).

Остаётся описать переход от одной конфигурации к другой. Для этого надо найти математическую операцию о. Тогда этот переход можно описать так:

К1 о Д = К2

Что же это за операция? Рассмотрим один из разрядов конфигурации и тот же разряд действия. Если в этом разряде действия единица, то в разряде конфигурации единица должна смениться на нуль и наоборот. Если в разряде действия нуль, то разряд конфигурации остаётся без изменения.

Можно составить такую таблицу:

Очевидно, что это xor. То есть разряды конфигурации К инвертируются по маске Д.

В конечном итоге мы должны конфигурацию 111 инвертировать по маске 111:

111 xor 111 = 000

Ну вот, собственно темообразующая часть статьи на этом закончена – идея найдена. Остальное – следствия.

3. Правила

В предыдущей части сформулирована идея, на которой может быть построена цифровая модель задачи. Однако в задаче есть ещё и правила ходов. Сформулировав их с использованнием найденной идеи, мы и получим модель задачи и её решения.

Правила – это запреты, то есть они определяют, что нельзя делать. В нашем случае запреты можно преобразовать в разрешения. Действительно, для кодирования позиций (конфигуаций) и ходов мы можем использовать трёхзначные двоичные числа:

1. Исходный список конфигураций (ходов): 000, 100, 010, 001, 110, 101, 011, 111.
2. Исходный список масок (действий) такой же: 000, 100, 010, 001, 110, 101, 011, 111.

Запреты означают, что часть из этих чисел использовать нельзя. Следовательно, можно использовать только какие-то подмножества чисел из этих списков. Выясним, какие.
Для этого сначала надо понять роль перевозчика в нашей модели.

Пока он на берегу, всё спокойно, никто никого не ест. Но как только он уплывает на другой берег, волк съедает козу или коза капусту. Следовательно, допусимость пары проверяется в конце хода (или после хода) на том берегу, с которого делается ход.

Следовательно, нам в числах, кодирующих конфигуации и ходы, надо закодировать ещё и перевозчика. Для этого добавим ещё один разряд. Пусть единица в этом разряде кодирует перевозчика на стартовом берегу, а нуль – на финишном. Причём очевидно, что у числа, кодирующего ход, в старшем (четвёртом) разряде всегда 1. То есть не бывает ходов без участия перевозчика. Тогда исходые списки чисел станут такими:

1. Исходный список конфигураций: 1000, 1100, 1010, 1001, 1110, 1101, 1011, 1111, 0000, 0100, 0010, 0001, 0110, 0101, 0011, 0111.
2. Исходный список масок: 1000, 1100, 1010, 1001, 1110, 1101, 1011, 1111.

Теперь используем этот же принцип для кодирования разрешённости/запрещённости хода или конфигурации (позиции). Добавим ещё один разряд, пятый – 1 ход или конфигуация разрешены, 0 – запрещены.

Сформируем теперь списки разрешённых ходов.

Инвертировать можно только или один разряд, или ни одного (перевозить можно только одного пассажира или плыть порожняком). Следовательно, маски могут быть только 1000, 1100, 1010, 1001 (это список разрешённых ходов).

Сформируем теперь списки разрешённых позиций.
Запрещена исходная конфигурация 1111 (первый ход не может быть порожняком).
Запрещаются единицы или нули в соседних разрядах (на берегу не могут быть пары волк–коза и коза–капуста).
То есть запрещаются конфигурации 1111, 1110, 1011, 1001, 1100. Следовательно, разрешаются 1000, 1101 и 1010.

После нечётного хода проверяется конфигурация единиц, а после чётного — нулей (единицы – это объекты на этом берегу, нули – на том; нечётный ход – переезд с этого берега на тот, чётный – с того на этот).

Если мы хотим, чтобы игра заканчивалась и быстро, то надо ограничить количество ходов. Поэтому запретим повторение позиций.

Это правило требует, чтобы позиция, из которой делается очередной ход, становилась запрещённой. То есть одна и та же позиция может быть разрешена, а может быть и запрещена. Следовательно, надо кодировать запрещённость/разрешённость позиции. Снова вводим дополнительный разряд – пятый: позиция разрешена – 1, позиция запрещена – 0.
Очевидно, что код хода в этом разряде должен всегда содержать 0, потому что разрешённая позиция не запрещается автоматически, а только если в результате хода получается тоже допустимая позиция.

Код исходной позиции сначала, естественно, содержит в пятом разряде единицу – она, раз мы в ней находимся, разрешена.

Окончательно получается список допустимых позиций 11000, 11101, 11010 и список допустимых ходов 01000, 01100, 01010, 01001.

4. Вычисление ходов.

Теперь попробуем представить себе, что должна делать функция, вычисляющая ход (вычислХод).

Аргументы этой функции:

 исхПоз – исходная позиция,
 списЗапрещПоз – список запрещённых позиций,
 списДопустХод – список допустимых ходов.

Вернуть функция должна резПоз – рузультирующую позицию.

Итак, функция вычислХод должна:

для каждого элемента Х списка допустимых ходов списДопустХод
 вычислить резПоз = исхПоз xor Х
  для каждой позиции П из списЗапрещПоз
  если резПоз and П ≠ 0
   добавить резПоз xor 10000 к списЗапрещПоз
   вернуть резПоз

5. Конец

Ну вот, осталось спроектировать главную функцию, которая будет вызывать функцию вычислХод с нужными аргументами и складывать полученные результаты в какую-нибудь удобную структуру данных, из которой в конце концов можно будет вывести результат на экран в удобном для восприятия человеком виде. Ну и собственно написать код.

На этом месте можно начинать мыслить, как программист. Желающие могут заняться этим в качестве домашнего задания.

Автор: andyudol

Источник