Жак Арсак - Программирование игр и головоломок

Вы без труда завершите это доказательство.

6. Комбинаторные задачи

Головоломка 28.

Действительно ли вам что-то еще нужно сообщать? Тогда я немного уточню способ поддержания части от 1 до р в порядке неубывания. Исходим ив упорядоченного по неубыванию вектора a1, a2, …, ар. Вы последовательно заменяете элемент ар элементами аi, где i направлен по убыванию. Вы последовательно получите

a1, a2, …, ар-1, ар,

a1, a2, …, ар, ар-1,

a1, a2, …, ар-3, ар-1, ар, ар-2.

По индукции, предположим, что в некоторый момент вы получили

a1, …, аi-1, аi+1, …, ар, аi

после перемены мест элементов с номерами i, р.

На следующем ходе вы поменяете местами аi-1 и последний член, который равен аi. Эта форма остается неизменной, и первая часть, от 1 до р − 1, остается отсортированной в неубывающем порядке. В конце вы получите

a2, a3, …, ар, a1.

Чтобы восстановить исходный порядок, вы располагаете последний элемент на запасном поле, поднимаете все остальные элементы на одну ступень, а затем размещаете содержимое запасного поля на первом месте.

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

Процедура работает достаточно быстро для того, чтобы в случае неудачи иметь возможность испытать наличие решения для n − 1, а затем для n + 1. Таким образом, по прошествии 45 с для каждого кандидата мы получаем в качестве результата

— решение, если оно существует,

— приближение о точностью до единицы, если это возможно.

Эта программа терпит неудачу крайне редко.

В выпуске от 8 марта 1984 года следующий розыгрыш не был найден ни кандидатами, ни Бертраном, ни кем- либо из присутствующих:

50 10 10 5 4 2 n = 767.

На моем микрокомпьютере нужно 18 с, чтобы обнаружить, что эта задача не имеет решения, а затем еще 5 с, чтобы получить

50 − 10 = 40 , 40 * 5 = 200, 10 − 2 = 8,

200 − 8 = 192, 192 * 4 = 768.

Для задачи

9 7 6 4 3 1 n = 795 через 6 с получается

4 * 9 = 36, 36 + 1 = 37, 37 * 7 = 259,

259 + 6 = 265, 265 * 3 = 795.

Наконец,

100 50 8 5 4 2 n = 631.

За менее чем 2 с получаем

50 − 4 = 46 , 46 * 2 = 92, 92 * 8 = 736,

100 + 5 = 105 , 736 − 105 = 631.

Я уже предлагал вам следующий пример:

100 75 50 25 10 10.

Для n = 370 особой трудности нет, потому что это — кратное десяти.

Компьютер сообщает мне

75/25 = 3,

50 − 3 = 47,

47 * 10 = 470,

470 − 100 = 370.

Это уже интересно, потому что это — совершенно не то решение, которое я собирался искать.

Чтобы найти 369, нужно образовать число, не кратное 5, — чего нельзя сделать с помощью какой-либо из трех операций +, −, *, сохраняющих кратность пяти. Следовательно, нужно использовать деление. Вот решение:

50/10 = 5,

5 * 75 = 375,

375 − 10 = 365,

100/25 = 4,

365 + 4 = 369.

Обе представленные здесь программы не позволяют получить это решение. Действительно, оно записывается в виде

(50/10) * 75 + 100/25 − 10.

А число 368? Вы нашли для него решение? Я не сумел. Но Жак Бейгбеде сообщил мне, что он получил его делением на 25…

10 * 100= 1000,

1000 − 75 = 925,

925 * 10 = 9250,

9250 − 50 = 9200,

9200/25 = 368.

7. Обо всем понемногу

Головоломка 31.

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

В строке 200 мы знаем, что цепочка а пройдена полностью, и исследованы все символы, не являющиеся пробелами. Если в цепочке b содержится еще какой-нибудь символ, не являющийся пробелом, то равенства цепочек нет. Все в порядке.

В строке 300 цепочка а пройдена вплоть до некоторого символа, не являющегося пробелом, и этот символ еще не исследован. Цепочка b пройдена полностью, и в ней не содержится более ни одного символа, не являющегося пробелом. Следовательно, эти две цепочки различны. Можно было бы сказать, что дальнейшее движение по цепочке а бесполезно, но не приводит к ошибке. Но это неверно. Вы остановились на еще не исследованном символе, который не является пробелом. Если вы перейдете к следующему символу, не являющемуся пробелом, то данный символ вы потеряете. Если, как бывает в большинстве случаев, цепочка а совпадает с цепочкой b с точностью до пробелов за исключением единственного дополнительного символа в конце цепочки, то именно по этой-то причине и должен быть остановлен пробег цепочки а. Перемещаясь и не обнаруживая больше символов, не являющихся пробелами, мы получаем сообщение, что цепочки совпадают, а это неверно. Ясно, что программисты не принимали во внимание и не изучали именно этот случай. И никаких оснований поступать так нет. В этом и состоит преимущество логических рассуждений о тексте программы по сравнению с проверкой ее правильности с помощью тестирования.

Ваша программа должна сохранять симметричную роль обеих цепочек. Не начинайте проверять результат пробега цепочки а, не пробежав цепочки b, и изучайте обе цепочки разом.

Возьмем общую ситуацию:

а пройдена вплоть до i включительно;

b пройдена вплоть до j включительно;

обе части совпадают с точностью до пробелов.

ВЫПОЛНЯТЬ

  продвинуть i на следующий символ в а, не являющийся пробелом;

  продвинуть j на следующий символ в b, не являющийся пробелом;

  ЕСЛИ таких нет в а И таких нет в b ТО

  r := ИСТИНА;

    КОНЧЕНО КОНЕЦ_ЕСЛИ;

  ЕСЛИ таких нет в a ИЛИ таких нет в b ТО

  r := ЛОЖЬ;

    КОНЧЕНО КОНЕЦ_ЕСЛИ;

  ЕСЛИ a[i] ≠ b[j] ТО r := ЛОЖЬ;

  КОНЧЕНО КОНЕЦ_ЕСЛИ;

ВЕРНУТЬСЯ

Эта программа совершенно симметрична относительно а и b…

Головоломка 33.

Нужно работать по модулю n. Удобнее всего пронумеровать элементы вектора от 0 до n − 1. Все элементы спускаются вниз на m по модулю n. Элемент, который переходит в 0, имеет номер m; элемент, который переходит в m, имеет номер 2m по модулю n; элемент, который переходит в 2m, имеет номер 3m по модулю n… Таким образом, мы получаем цепочку чисел, кратных m по модулю n. Весь вопрос в том, чтобы узнать, порождает ли последовательность чисел, кратных m по модулю n, последовательность всех целых от 0 до n − 1.

Это так, если m и n взаимно просты. В противном случае пусть с наибольший общий делитель m и n:

m = m'с, n = n'c,

n' * m = n' * m' * с = m' * n = 0 по модулю n.

Эта цепочка возвращается в 0 за n' = n/с операций. При этом пробегается не весь вектор, а только его элементы, сравнимые с 0 по модулю с.

Беря в качестве исходных элементов различных циклов последовательно целые числа от 0 до c − 1, вы разместите все элементы вектора, причем каждый из них будет перемещаться в точности один раз…

Головоломка 34.

Рассмотрите более общую задачу, что заставит вас открыть одно из этих знаменитых «преобразований программы», столь полезных, когда желательно улучшить уже существующие программы. Обозначим через t и u два условия, а через a и b — две последовательности инструкций. Вот простой цикл:

ПОКА t ВЫПОЛНЯТЬ

  ЕСЛИ u ТО a ИНАЧЕ b

КОНЕЦ_ЕСЛИ

ВЕРНУТЬСЯ

Последовательность операций следующая:

— проверяется условие t,

— если оно истинно, то проверяется u,

— если u истинно, то выполняется a, и все возобновляется.

Допустим, что условия t и u таковы, что я имею возможность проверить u, даже если проверка условия t дает значение ЛОЖЬ[29]. Тогда, пока условия t и u истинны, в цикле выполняется а.