Брент (Brent R. P.). Fast Multiple-precision Evaluation of Elementary Functions, Stanford University, Technical Report STAN-CS-75-515, August 1975.
Томас (Thomas G. В., Jr.). Calculus and Analytic Geometry, 3rd ed. Addison-Wesley, Reading, MA, 1960. Section 16.3—3, pp. 809–812.
Томас приводит сведения по математическому анализу, необходимые для рассмотренных нами вычислений и подобных им; изложение в его книге простое и классическое. Рейтуиснер, а также Шенкс и Ренч — два примера из ряда работ по вычислению π. В обеих работах дается некоторый исторический обзор, обе они используют подход, предлагаемый Томасом. Брент развивает совершенно новые методы вычисления функций sin, cos, log, arctg и т. д., основанные на эллиптических интегралах. Его алгоритмы работают значительно быстрее описанных нами рядов. Работа Брента пока существует в виде технического доклада.
Кнут (Knuth D. E.). The Art of Computer Programming/Seminumerical Algorithms, Addison-Wesley, Reading, MA, 1969. Section 4.3.3, pp. 258–280. [Имеется перевод: Кнут Д. Искусство программирования для ЭВМ. Т. 2. Получисленные алгоритмы. — М.: Мир, 1977, п. 4.3.3., стр. 314–340[36].]
Рейтуиснер (Reitwiesner G. W.). An ENIAC Determination of π and e to More than 2000 Decimal Places, Mathematical Tables and Aids to Computation, 4, pp. 11–15, 1950.
Шенкс, Ренч (Shanks D., Wrench J. W.). Calculation of π to 100 000 Decimals, Mathematics of Computation, 16, pp. 76–99, 1962.
* Кудрявцев Л. Д. Математический анализ. — М.: Высшая школа, 1973.
23.
Великий комбинатор,
или Оптимальные стратегии для игры с угадыванием
В игре, как и в музыкальном произведении, можно выделить тему и мотивы. Причина успеха самых удачных игр часто состоит в том, что они мастерски соединяют по-новому некоторые из давно известных принципов построения игр. Как и в музыке, старая идея, возрожденная в новом обличье, может выглядеть привлекательней, чем мешанина свежеиспеченных новых веяний. В середине 70-х годов широкую популярность в Англии получила игра великий комбинатор (Mastermind)[37], и она, похоже, станет классикой. Вы и ваш компьютер получите большое удовольствие, сыграв в нее.
Правила великого комбинатора крайне просты. Один из игроков, загадывающий, записывает секретную комбинацию из любых четырех цифр от 1 до 6 (повторения допускаются), называемую кодом. Второй игрок, отгадывающий, пытается раскрыть код, высказывая разумные предположения, называемые пробами. Каждая проба, как и код, представляет собой произвольную комбинацию из четырех цифр в диапазоне от 1 до 6. Отгадывающий игрок сообщает пробу загадывающему, и тот должен ответить, сколько цифр в пробе совпадает с цифрами кода как по положению, так и по величине и сколько из остальных цифр пробы входят в код, но стоят на другом месте. Так, на пробу 1123 при коде 4221 будет получен ответ: «Одна цифра совпадает и стоит на том же месте, и еще одна совпадает, но стоит на другом месте». Тур игры продолжается до тех пор, пока отгадывающий не назовет пробу, в точности совпадающую с кодом, т. е. пока не отгадает код. После этого игроки меняются ролями и проводят еще один тур. Победителем считается тот из игроков, кто определит код противника за меньшее число проб. Хотя здесь не последнюю роль играет везенье, тем не менее игрок, систематически делающий правильные умозаключения из получаемой информации, должен иметь лучшие результаты по итогам нескольких партий. Практически вы должны пытаться выводить из ответов на ваши пробы отрицательные следствия относительно того, какие коды невозможны; психологические тесты показывают, что для многих людей это оказывается совсем не просто. В табл. 23.1 приведен один полный тур.
Таблица 23.1. Великий комбинатор. Пример партии
Код: 4651
Проба 1: 2345. О точных попаданий. 2 совпадения по значению.
Проба 2: 4516. 1 точное попадание. 3 совпадения по значению.
Проба 3: 5461. 1 точное попадание. 3 совладения по значению.
Проба 4: 4165. 1 точное попадание. 3 совпадения по значению.
Проба 5: 4615. 2 точных попадания. 2 совпадения по значению.
Проба 6: 4651. 4 точных попадания. Игра окончена
Написать программу, имитирующую роль загадывающего, не составляет труда. Отгадывание головоломок, заданных машиной, — тоже развлечение, позволяющее отточить ум. Однако гораздо интереснее, если компьютер сможет выступать также и в роли отгадывающего, чтобы можно было сыграть несколько партий и определить победителя. Боб Кули из Lawrence Livermore Laboratory и Д. Кнут разработали довольно близкие стратегии, позволяющие ЭВМ достигнуть высокого класса игры. Центральное место в обеих стратегиях занимает идея пространства решений. Начальное пространство решений Р0 состоит из всех возможных кодов (и имеет, следовательно, б4 элементов); после i-й пробы Gi пространство Pi состоит из всех тех членов пространства Pi−1, которые не опровергаются ответом Ri. Иными словами, пространство Pi — это множество всех комбинаций, которые все еще могут быть кодом; задача отгадывающего — свести пространство к одному элементу.
36
В § 4.4 этой книги приведены алгоритмы перевода чисел в десятичную систему. —
37
В журнале «Наука и жизнь» № 2, 1978, с. 150–151; № 8, 1978, с. 142—143, опубликован вариант этой игры под названием «Быки и коровы». —