Жак Арсак - Программирование игр и головоломок

Arsac — Mondou О., Bourgeois — Camescasse, Gourtay M.

Premier livre de programmation (écriture de boucles de proggrammes).

Deuxiéme livre de programmation (procédures, fichiers).

Pour aller plus loin en programmation (récursivité, structures de donnees), Cedic — Nathan, Paris, 1982.

Taurisson A., Petitguillaume A.

A vous de jouer, Introduction à la science de lʼinformatique, Modulo Editeur, Outremont, Québec, Canada.

Я здесь совершаю плагиат по отношению к поговорке жителей плоскогорья Высоких Вивар, которая звучит так: кто сам пилит свои дрова, согревается дважды.

Строго говоря, эти рассуждения применимы к любой программе, написанной на любом языке, если только эта программа не использует никакой внешней информации в качестве исходных данных. В качестве такой внешней информации удобнее всего использовать что-нибудь связанное с временем: число изменений напряжения в сети с момента последнего включения вашего компьютера или число секунд с момента его покупки, если ваш компьютер снабжен внутренними энергозависимыми часами (на литиевой батарейке), и т. п. Обычно, на каком бы языке вы ни работали, у вас есть возможность прочесть показания внутренних часов компьютера (посмотрите в документации, как работать с таймером). — Примеч. ред.

См. предыдущую сноску. — Примеч. ред.

«Пришлите побольше денег.»

«Помогите молодому человеку.»

«Нужно, лекция, ученик.»

S — первая буква слова «somme» (фр. сумма), P — слова «produit» (фр. произведение). — Примеч. ред.

Да и от языка, который вы используете. — Примеч. ред.

Повторим эти рассуждения чуть более подробно. Пусть

a 1= 2, a i +1= a i ² − 1 mod n ,

b 1= 2, b i +1= b i ² mod s

— последовательности, соответствующие числам n и s соответственно. Тогда легко доказать по индукции, что b i = a i mod s . Одним из периодов последовательности { а i } является n . Значит, n является периодом и для последовательности { b i }. Известно, что любой период последовательности кратен ее минимальному периоду, Так как p , по определению, является минимальным периодом последовательности b i , то n делится на p . — Примеч. ред.

Этот язык описан на стр.7–8 выше. Здесь лишь кратко напоминаются формы записи условных операторов и операторов цикла. — Примеч. ред.

В оригинале «master-mind». — Примеч. ред.

Так начинаются правила проведения автогонок. — Примеч. ред.

Напомним, что книга написана в начале 80-х годов. — Примеч. ред.

Таким образом, подсчитывается общая сумма карт, взятых партнерами, а не отдельные суммы для каждого партнера. — Примеч. ред.

Имеется в виду постановка Блезом Паскалем (1623–1662) вопроса о вере в существование бога как задачи о выборе стратегии в азартной игре («Мысли», отрывок 233): «Взвесим выигрыш и проигрыш, ставя на то, что бог есть. Возьмем два случая: если выиграете, вы выиграете все; если проиграете, то не потеряете ничего. Поэтому, не колеблясь, ставьте на то, что он есть» (Антология мировой философии в четырех томах, Том 2, М., «Мысль», 1970, С. 306). — Примеч. пер.

«Ослиным мостом», дальше которого учащегося сдвинуть трудно, считалась в XII–XIII вв. в Парижском университете либо теорема о равенстве углов при основании равнобедренного треугольника, либо геометрическое доказательство теоремы Пифагора. — Примеч. пер.

Вот другая и, на мой взгляд, более правильная формулировка этой задачи: циклически сдвинуть элементы n -вектора на m позиций влево. — Примеч. ред.

Нужно было бы сказать «не убывает», но получилось бы совершенно не в стиле этой книги. — Примеч. ред.

Важно и то, что никаких других позиций, кроме 0, из 1 получить нельзя. — Примеч. ред.

Читатель может вернуться к определению чисел Спрага-Грюнди и убедиться, что эти числа определяются на множестве игровых позиций раз и навсегда, исходя из правил игры, и, разумеется, не могут меняться в процессе разыгрывания конкретной партии. Что же является позицией в этой средневековой игре? — Позицией является состав выложенных на стол карт, а также их значения: сколько карт на столе имеет значение 1, сколько карт имеет значение 2, и т. д. Сумма, набранная игроками в данный момент, равна 84 минус сумма значений карт на столе. Что же имеет в виду автор книги, когда он пишет SG(50)? Почему он приписывает число Спрага-Грюнди не позиции, а сумме карт этой позиции? Дело в том, что для всех позиций с набранной суммой 50 число Спрага-Грюнди одинаково и равно 0. Это и позволяет написать равенство SG(50) = 0. А что могло бы значить SG(49)? Если бы все позиции с суммой 49 имели одинаковое число SG, мы бы обозначили его SG(49). Но, увы! Разные позиции с суммой 49 имеют разные числа Спрага-Грюнди. Так что автор книги дальше рассуждает о несуществующих вещах. Я из этих рассуждений ничего полезного извлечь не смог (кроме подозрения, что у автора нет работающей программы, играющей в 24 карты). — Примеч. ред.

Можно доказать, что в играх, подобных игре Нима и обычным шахматам, — в играх с полной информацией — выигрывающая стратегия всегда существует. Это — относительно простая теорема. Другое дело, что эта выигрывающая стратегия может быть не очень простой (Ним) или вообще еще не открытой (шахматы). — Примеч. ред.

В частном случае, когда в каждой кучке игра идет по правилам игры Нима, число Спрага-Грюнди каждой кучки равно просто числу спичек. — Примеч. ред.

Эти рассуждения безусловно справедливы, если в моем распоряжении остался один-единственный ход — тогда этим ходом я хочу «попасть в десятку», т. е. угадать искомую комбинацию. Если же ход не последний, то моя цель — получить как можно больше информации об искомой комбинации. Может случиться, что для этого выгоднее взять комбинацию вне множества, описанного автором. — Примеч. ред.

Маленькая головоломка для знающих французский (или хотя бы имеющих словарь): откуда это обозначение? — Примеч. ред.

При чтении этого абзаца вспоминается шутка Маяковского. После одного из своих выступлений он получил из зала записку: «Мы с товарищем слушали ваши стихи и ничего не поняли». Маяковский ответил: «Нужно иметь умных товарищей». — Примеч. ред.

Если разрешить перемещать каждый элемент вектора не один раз, а два, то можно найти изящное и простое решение, в котором и речи нет ни о каких общих делителях. Представим себе элементы вектора расположенными по окружности на равных расстояниях друг от друга. Нам нужно повернуть эти векторы на угол. Используйте тот факт, что всякий поворот окружности можно получить, выполнив подряд две осевые симметрии. — Примеч. ред.