Программирование игр и головоломок

  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,

29

Вот пара условий, которая не обладает этим свойством: t: x /= 0; u: sin(1/x) > 0. — Примеч. ред.

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

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

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

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

 i := 1; р : = 0;
 ПОКА i <= n ВЫПОЛНЯТЬ
  ЕСЛИ a[i] = a[i–  р]
  ТО x := a[i]; р := р + 1; i := i + 1
  ИНАЧЕ i := i + 1
  КОНЕЦ_ЕСЛИ
 ВЕРНУТЬСЯ

Мы обнаруживаем, что в нашем случае мы не можем объединить два условия с помощью операции И: если i не удовлетворяет условию, что i не больше n, то нельзя поставить вопрос относительно a[i]. Обрисуем трудность подходящим образом:

— нужно либо добавить в таблицу а поле, которое содержит какую-нибудь несущественную для нас величину (мы к этой величине не обращаемся);

— либо нужно допустить, что операция И не коммутативна. Для вычисления t и u мы вычисляем t, и если результат есть ЛОЖЬ, то все кончено и притом с результатом ЛОЖЬ. В противном случае результат есть значение условия u.

Тогда можно использовать наше преобразование:

 i := 1; р := 0;
 ПОКА i <= n ВЫПОЛНЯТЬ
  ПОКА i <= n И а[i] = a[i–  р] ВЫПОЛНЯТЬ
  x := а[i]; р := р + 1; i := i + 1
  ВЕРНУТЬСЯ
  ПОКА i <= n И а[i] /= a[i–  р] ВЫПОЛНЯТЬ
  i : = i + 1
  ВЕРНУТЬСЯ
 ВЕРНУТЬСЯ

Первый цикл движется по таблице а, пока обнаруживается, что элементы равны между собой. Более точно, р и i изменяются одинаково, так что разность i– р остается постоянной. Все элементы a[i] сравниваются с одним и тем же элементом, и величина x остается постоянной, равной этому элементу, на протяжении всего цикла.