Программирование игр и головоломок - [41]
Головоломка 14.
Изучаемое число имеет вид 1000a + 100b + 10c + d при a ≥ b ≥ c ≥ d. И, так как не все цифры одинаковы, то непременно a > d.
Вы можете доказать, что результат первого вычитания кратен девяти, так что, переходя к первой разности, вы кое-что знаете о сумме a + b + c + d.
Каково бы ни было исходное число, первая из полученных разностей имеет вид 999u + 90v с v < u, 0 ≤ v, 0 < u ≤ 9. Так что-не так уж много чисел нужно испытывать…
Головоломка 15.
Эта головоломка намного труднее. Используйте все данные задачи, хотя и кажется, что их не слишком много.
Господин P не может найти искомые числа. Следовательно, число р не является произведением двух простых чисел — в противном случае их разложение на множители было бы однозначным.
Господин S это знает. Но их сумма s может быть многими способами представлена в виде суммы двух чисел. Ни одна из этих пар не является парой простых чисел. Это условие гораздо более ограничительно: нужно вычеркнуть из списка возможных значений s все такие значения, которые являются суммами двух простых чисел — таковы 12 (так как 12 = 7 + 5), 13 (11 + 2). Компьютер позволит вам составить оставшийся список.
Господин P не может найти решение, так как его произведение может быть многими разными способами разложено в произведение двух чисел. Учитывая, что именно знает S, он исключает все пары, сумма которых вычеркнута. У него остается в точности одна пара. Каковы произведения, обладающие этим свойством?
Наконец, господин S получает решение. Следовательно, среди всех пар с суммой s есть только одна пара, дающая произведение с упомянутым выше свойством.
Компьютер нужен, чтобы порождать списки и вычеркивать в них. В конце должна оставаться одна и только одна пара.
Головоломка 16.
Я предлагаю вам решить эту задачу в два приема.
1. Составьте сначала программу по методу Полларда-Брента о «маленькими» числами, иначе говоря, такими, что машина представляет их бее округления или усечения, Это зависит от машины. Я на своей машине могу получить около 8·10>6, что немного. Возникают еще некоторые сомнения, как только принимаются во внимание деления…
Чтобы узнать, становится ли последовательность периодической, вы можете ограничиться рассмотрением разностей a>i − a>j, где i и j меняются в соответствии с вполне определенными законами, Вам следует рассматривать н. о. д. этих разностей и n. Это невыполнимо для каждой разности и потребует много времени.
Идея в том, чтобы образовать произведение на некоторое число этих разностей по модулю n, а затем брать н. о. д. этих разностей и n. Если одна из этих разностей имеет с n н. о. д., отличный от 1, то для произведения будет выполняться то же самое. Выбор числа членов для участия в произведении предоставляется вашему усмотрению. Если членов слишком мало, то вы вычисляете много н о. д. и замедляете метод. Если членов много, то вы делаете ненужные операции! вы долго ждете перед тем, как обнаружить делитель…
2. Если эта первая программа уже готова, переходите к гораздо большим числам. Нужно выполнить следующие операции:
произведение двух чисел по модулю n,
н. о. д. двух чисел, числа n и числа, меньшего n.
Настоящая трудность — это произведение по модулю n. Так как к ней часто обращаются, то она должна быть оптимальной…
Может оказаться опасным пускаться в этот метод Полларда, не зная, является ли исследуемое число составным. Используйте для этого тест Ферма.
В этом единственную трудность представляет возведение x в степень n − 1 по модулю n.
Следовательно, пусть нужно вычислить y = x>p.
Примем следующую индуктивную гипотезу: искомый результат имеет вид y = u>kw.
Если k есть нуль, то u>k = 1 и потому у = w, и все закончено.
Если k не нуль и если k четно, то u>k = u>2(k/2) = (u>2)>k/2.
Заменяя u на u * u и k на k/2 возвращаемся к общей ситуации.
Если k нечетно, то u>k = u * u>2((k−1)/2)
w * u>k = (w * u) * (u>2)>(k−1)/2
Заменим w на w * u, u на u * u и k на целую часть от k/2.
Все это должно проделываться по модулю n. Операции над k не содержат трудностей. Если числа достаточно малы, то вы действуете обычными умножениями или делениями.
Если же числа не являются достаточно малыми, то все сводится к предыдущему случаю. Но у вас здесь есть элемент ответа. Я уже говорил вам, как можно вычислить y = x>p с помощью бинарного разложения p, выполняя умножения только по модулю n. Переделайте то же рассуждение для y = p * x, заменяя возведение в степень умножением, а умножение — сложением. Предположите, что результат имеет вид
y = k * u + w.
Если k четно, то k * u (k/2) * (u + u), и т. д.
Сложения нужно делать по модулю n, что не требует, впрочем, операции деления…
Я на своем компьютере получил отличные результаты для теста Ферма. А метод Полларда-Брента еще остается очень медленным. Работайте надежно. Можно ли пользоваться программой, в правильности которой вы не уверены?
Головоломка 17.
Подсказка: эта программа сообщает, делится ли n на b.
Головоломка 18.
Снова подсказка: эта программа выводит НЕТ, если n не является точным квадратом; в противном случае она выводит квадратный корень из n. Но это из области бесполезных подсказок. Как вы сможете показать, что эта программа действительно делает то, что я анонсировал? Испытав ее? Вы можете испытать все целые?
![Изучаем 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 так просто изучить и так удобно использовать, что даже новые и неискушенные пользователи быстро переходят на ОО-подход.