Программирование игр и головоломок - [73]

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 истинны, в цикле выполняется а.

Вот другая последовательность, которая может встретиться:

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

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

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

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

ПОКА t ВЫПОЛНЯТЬ
  ПОКА t И u ВЫПОЛНЯТЬ а ВЕРНУТЬСЯ
  ПОКА t И НЕ u ВЫПОЛНЯТЬ b ВЕРНУТЬСЯ
ВЕРНУТЬСЯ

Мы перепишем программу для определения равнин, чтобы придать ей форму ПОКА, заключенного в скобки ЕСЛИ:

i := 1; р : = 0;
ПОКА i ≤ n ВЫПОЛНЯТЬ
  ЕСЛИ a[i] = a[i − р]
    ТО x := a[i]; р := р + 1;