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

Я надеялся не приводить в этой книге никаких готовых программ. Программирую не я, а вы. И я не очень люблю смотреть, как подростки копируют программу, набирая ее на клавиатуре и при этом не отдавая себе отчета в том, что она делает и как устроена. Но сказать, что делает та или иная программа, может оказаться настоящей головоломкой, Программы, которые мы будем обсуждать, написаны на некотором воображаемом языке[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.

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