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

Эта цепочка возвращается в 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 : x ≠ 0; u : sin(1/ x ) > 0. — Примеч. ред. . Тогда, пока условия 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; 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 остается постоянной, равной этому элементу, на протяжении всего цикла.

Второй цикл изменяет i до тех пор, пока не обнаружится пара элементов, отстоящих на р + 1.

Уточним ситуацию выхода из первого внутреннего цикла. Мы собираемся найти конец равнины, которая лучше всех предыдущих, мы фиксируем ее длину р и ее значение х , a i обозначает первый элемент после этой равнины. Мы можем надеяться найти пару j , j − р с

a [ j ] = a [ j − р ]

только пока j − р остается на равнине, которую мы собираемся пройти. Наименьшее соответствующее i значение j удовлетворяет условию j − р = i , или j = i + р .

Следовательно, можно увеличивать i от р в обоих циклах, не меняя действия программы, что ускоряет ее работу.