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

ПОКА условие ВЫПОЛНЯТЬ

  последовательность команд

ВЕРНУТЬСЯ

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

* Головоломка 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

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

3. Игры без стратегии

Общие предложения

Мы собираемся предложить здесь игры для программирования. Мы выбрали их потому, что они не требуют придумывания выигрывающей стратегии при составлении программы. Каждая игра ставит вас перед, вообще говоря, непредсказуемой ситуацией. Вы должны играть, соблюдая правила и имея в виду добиться определенной цели. Вам следовало бы развить собственную стратегию. После того, как вы предложили свой ход, компьютер сообщает новое состояние игры, затем изменяет это состояние некоторым почти полностью определенным образом. Ваша стратегия должна оценить, как именно.

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

Игра 6. Гениальный ответчик.

Я не думаю, что есть еще хоть кто-нибудь, кто не знает игру, которую М. Мейрович назвал «гениальный ответчик»[11]. Обычно она играется с цветными шашками (6 и 8 различных цветов в зависимости от изготовления). Играющий должен угадать сделанную из этих шашек тайную комбинацию. Так, в варианте «мини» вы должны угадать комбинацию из четырех шашек, например: ГОЛУБАЯ ЖЕЛТАЯ ЖЕЛТАЯ КРАСНАЯ (в этом порядке). Второй игрок — ведущий. Это он выбирает комбинацию для угадывания и он оценивает ходы, которые вы делаете. Ваш ход в игре состоит в том, что вы предлагаете комбинацию, содержащую то же число шашек, из того же набора цветов, например, КРАСНАЯ ГОЛУБАЯ ЖЕЛТАЯ ГОЛУБАЯ.

Ведущий сообщает вам, сколько шашек из вашей комбинации содержат правильный цвет на правильном месте: здесь — 1, третья шашка ЖЕЛТАЯ, как и в неизвестной вам комбинации. Затем он сообщает вам, сколько шашек имеют правильный цвет, но стоят на неправильных местах. Здесь 1, так как вы предложили красную шашку, но она на неверном месте. Согласно традиции, ведущий выставляет столько черных шашек, сколько в вашем ответе шашек правильного цвета на правильном месте, а затем столько белых шашек, сколько шашек правильного цвета на неверных местах.