Программирование игр и головоломок

либо a^m = 1 по модулю n,

либо a^m2r = n– 1 по модулю n = 2^sm + 1 для некоторого r, 0 <= r < s.

Очень мало сильно псевдопростых чисел, не являющихся простыми; так

2047 = 23 * 89 — сильно псевдопросто по основанию 2,

1373653 = 829 * 1657 — по основанию 2 и 3,

25326001 = 2251 * 11251 — по основанию 2, 3 и 5,

3215031751 = 151 * 751 * 28351 — по основанию 2, 3, 5 и 7.

Метод интересен, потому что aⁿ вычисляется за время, растущее не быстрее, чем ln n. Это утверждение вытекает из соотношений:

а⁰ = 1, а¹ = а,

a²ⁿ = (а * а)ⁿ, a²ⁿ⁺¹ = (a * a)ⁿ * а.

Все, что нужно для работы, у вас есть. Больше делать нечего, кроме собственно составления программы.

Кстати: знаете ли вы две универсальные конструкции в информатике? Первая — «известно, что…». Вторая — «это и нужно сделать…».

Таинственные программы

Я надеялся не приводить в этой книге никаких готовых программ. Программирую не я, а вы. И я не очень люблю смотреть, как подростки копируют программу, набирая ее на клавиатуре и при этом не отдавая себе отчета в том, что она делает и как устроена. Но сказать, что делает та или иная программа, может оказаться настоящей головоломкой, Программы, которые мы будем обсуждать, написаны на некотором воображаемом языке [10] . Вам придется по крайней мере сделать усилие, чтобы перевести их на ваш обычный язык: Бейсик, LSE или Паскаль. Условная команда записывается в виде

10

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

 ЕСЛИ условие ТО последовательность команд
 КОНЕЦ_ЕСЛИ

(последовательность команд выполняется тогда и только тогда, когда условие истинно)

или

 ЕСЛИ условие ТО последовательность команд
  ИНАЧЕ последовательность команд
 КОНЕЦ_ЕСЛИ

(если условие истинно, то выполняется последовательность команд, заключенная между ТО и ИНАЧЕ, в противном случае выполняется та последовательность команд, которая расположена между ИНАЧЕ и КОНЕЦ_ЕСЛИ).

В обоих случаях КОНЕЦ_ЕСЛИ играет роль закрывающей скобки, связанной с открывающей скобкой ЕСЛИ. Мы будем использовать цикл

 ПОКА условие ВЫПОЛНЯТЬ
  последовательность команд
 ВЕРНУТЬСЯ

Последовательность команд, содержащаяся между ВЫПОЛНЯТЬ и ВЕРНУТЬСЯ, повторяется, ПОКА условие истинно.

* Головоломка 17. Для забавы. Вот легко понимаемая программа. Здесь n и b — два натуральных числа и b нечетно (это существенно)

 ПРОЧЕСТЬ n, b
ПОКА n > b ВЫПОЛНЯТЬ
  ЕСЛИ n четно ТО n := n/2
  ИНАЧЕ n := n–  b
  КОНЕЦ_ЕСЛИ
 ВЕРНУТЬСЯ
 СООБЩИТЬ ЕСЛИ n = 0 ТО 'ДА'
 ИНАЧЕ 'НЕТ' КОНЕЦ_ЕСЛИ

Вы можете попробовать выполнить ее вручную для

n = 2⁷⁷– 3, b = 7.

Забавно, не правда ли? Несмотря на свою исключительную» простоту, эта программа, кажется, новая…

*** Головоломка 18. Посерьезнее. Эта — несомненно более трудная. И тоже неопубликованная. Боюсь, что вы можете избаловаться… На вход программы подается n — нечетное натуральное число.

 ПРОЧЕСТЬ n
 q := (n–  1)/4; p := целая_часть (q)
 ЕСЛИ q /= p ТО СООБЩИТЬ 'НЕТ';
 КОНЕЦ_РАБОТЫ КОНЕЦ ЕСЛИ
 ЕСЛИ нечетное p ТО СООБЩИТЬ 'НЕТ';
 КОНЕЦ_РАБОТЫ КОНЕЦ_ЕСЛИ
 a := 4; b := 1
 ПОКА p >= a ВЫПОЛНЯТЬ
 p := p/2
 ЕСЛИ нечетное p ТО p := p–  a/2 - b;
 b := a–  b КОНЕЦ ЕСЛИ a := a + a ВЕРНУТЬСЯ
 ЕСЛИ p = 0 ТО СООБЩИТЬ b;
 КОНЕЦ РАБОТЫ КОНЕЦ_ЕСЛИ
 ЕСЛИ p + 2*b = a ТО СООБЩИТЬ a–  b;
 КОНЕЦ РАБОТЫ КОНЕЦ_ЕСЛИ
 ЕСЛИ p = 4 * (a–  b) ТО СООБЩИТЬ 2 * a–  b;
 КОНЕЦ РАБОТЫ КОНЕЦ_ЕСЛИ
 СООБЩИТЬ 'НЕТ'; КОНЕЦ_РАБОТЫ

Я не запрещаю вам перевести эту программу на ваш любимый язык, а затем испытать ее для различных значений n. Есть маленький шанс, что вы угадаете, на что она способна. Это не очевидно!

** Головоломка 19. Вклад Жака Гебенстрейта. Я обязан Жаку Гебенстрейту следующей программой. Она была предложена в том виде, в каком я ее привожу, без какого-либо комментария (это было сделано без злого умысла с его стороны: сам он получил не больше от того, кто дал ему эту программу).