Читать «Программирование игр и головоломок» онлайн - страница 126
Жак Арсак
ПОКА t ВЫПОЛНЯТЬ
ЕСЛИ u ТО a ИНАЧЕ b
КОНЕЦ_ЕСЛИ
ВЕРНУТЬСЯ
Последовательность операций следующая:
— проверяется условие t,
— если оно истинно, то проверяется u,
— если u истинно, то выполняется a, и все возобновляется.
Допустим, что условия t и u таковы, что я имею возможность проверить u, даже если проверка условия t дает значение ЛОЖЬ. Тогда, пока условия 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 от р в обоих циклах, не меняя действия программы, что ускоряет ее работу.
Чтобы ускорить и первый внутренний цикл, мы присвоим переменной x ее значение перед циклом и сохраним ее начальное значение в j. Так как i − р остается постоянным, то можно вычислить значение р также и после выхода из цикла. Начальные значения суть i = j и р = р0, а конечные значения i и р удовлетворяют соотношениям i − р = j − р0, откуда р = i + р0 − j: