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

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

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

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

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

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

или

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

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

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

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

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

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

ПРОЧЕСТЬ a, b; p : = max (a, b); q := min (a, b)
ПОКА q > eps ВЫПОЛНЯТЬ
  r := (q/p)?; s := r/(r + 4)
  p := (2 * s + 1) * p; q := s * q
ВЕРНУТЬСЯ
результат := p

Как вам кажется, что вычисляет эта программа?

Оглавление книги