Читать «Программирование игр и головоломок» онлайн - страница 125
Жак Арсак
Ваша программа должна сохранять симметричную роль обеих цепочек. Не начинайте проверять результат пробега цепочки а, не пробежав цепочки 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 — две последовательности инструкций. Вот простой цикл: