Программирование игр и головоломок - [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;
![Изучаем Java EE 7](/storage/book-covers/e0/e0ee9b7e3e4f168a93df98d7e47d66089eac3652.jpg)
Java Enterprise Edition (Java EE) остается одной из ведущих технологий и платформ на основе Java. Данная книга представляет собой логичное пошаговое руководство, в котором подробно описаны многие спецификации и эталонные реализации Java EE 7. Работа с ними продемонстрирована на практических примерах. В этом фундаментальном издании также используется новейшая версия инструмента GlassFish, предназначенного для развертывания и администрирования примеров кода. Книга написана ведущим специалистом по обработке запросов на спецификацию Java EE, членом наблюдательного совета организации Java Community Process (JCP)
![Геймдизайн. Рецепты успеха лучших компьютерных игр от Super Mario и Doom до Assassin’s Creed и дальше](/storage/book-covers/d0/d0fc13172d4310c9da7b10ba57a3fcb2e3d9f10d.jpg)
Что такое ГЕЙМДИЗАЙН? Это не код, графика или звук. Это не создание персонажей или раскрашивание игрового поля. Геймдизайн – это симулятор мечты, набор правил, благодаря которым игра оживает. Как создать игру, которую полюбят, от которой не смогут оторваться? Знаменитый геймдизайнер Тайнан Сильвестр на примере кейсов из самых популярных игр рассказывает как объединить эмоции и впечатления, игровую механику и мотивацию игроков. Познакомитесь с принципами дизайна, которыми пользуются ведущие студии мира! Создайте игровую механику, вызывающую эмоции и обеспечивающую разнообразие.
![Обработка событий в С++](/build/oblozhka.dc6e36b8.jpg)
В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.
![MFC и OpenGL](/build/oblozhka.dc6e36b8.jpg)
В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.
![Симуляция частичной специализации](/storage/book-covers/7e/7e33d937f206a76edb7f45006e896cc191605df5.jpg)
В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.
![Питон — модули, пакеты, классы, экземпляры](/build/oblozhka.dc6e36b8.jpg)
Python - объектно-ориентированный язык сверхвысокого уровня. Python, в отличии от Java, не требует исключительно объектной ориентированности, но классы в Python так просто изучить и так удобно использовать, что даже новые и неискушенные пользователи быстро переходят на ОО-подход.