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

Должно получиться:

s = a1 + — комбинация из n − 1 чисел или

s = a1 − — комбинация из n − 1 чисел.

Заметим, что разность нужно брать по абсолютному значению.

Таким образом, остается искать способ представления s + a1 или s − a1 помощью n − 1 оставшихся шашек. Такую процедуру легко написать. Таблица чисел может быть глобальной величиной. Чтобы сохранять только n − 1 чисел, кроме первого, достаточно сказать, что таблица рассматривается, начиная с индекса 2. Следовательно, нужна процедура, в которой в качестве параметров берутся:

индекс, начиная с которого должны рассматриваться числа,

сумма, которую нужно найти.

Итеративные формы программы, которые вы сможете написать, суть немедленные переводы на итеративный язык этой рекурсивной формы.

Головоломка 28.

Решение, набросок которого я привожу здесь, принадлежит не мне. Я нашел его вышедшим из-под пера Николь Брео Поликен и Оливера Герца в журнале «Персональный компьютер» (Lʼordinateur individuel) за март 1983 г.

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

Я переписал это решение практически без изменений на LSE83 (намного более структурированная форма LSE, соединяющая преимущества структурирования языка Паскаль с возможностями манипуляций с цепочками символов, имеющихся в LSE, и, сверх того, облегчением программирования сверху вниз), и результат немедленно оказался удовлетворительным. Все это служит прославлению авторов. Как же могло тогда случиться, что пояснения, которые авторы дают к своей программе, до такой степени недоступны пониманию, что мне потребовался большой труд, чтобы достичь понимания их метода? Там, действительно, есть две или три «хитрости», которые гораздо больше заслуживали комментария, чем тот факт, что из-за рекурсии результаты записываются в порядке, обратном порядку их получения…

Сохраним предположения работы этих авторов, приведенные в условиях задачи. Зачем от них отказываться? Например, такая комбинация, как

n = p1 * p2 + p3 * p4 − p5/p6

не сводится ни к одной из предложенных форм.

Программа, написанная авторами, рекурсивна, но ее читателю доставляют затруднения две особенности ее написания:

— как я уже указывал, некоторые переменные, являющиеся локальными в одной процедуре, глобальны в другой… Конечно, это может быть обнаружено при внимательном чтении текста, но это и требует внимания;

— некоторые процедуры мультиформны и дают совершенно различные результаты в зависимости от значений формальных параметров.

Вернемся к задаче в той форме, в какой она была поставлена. Что нужно делать?

Сначала пройдем по таблице шашек от 1 до 6. Для каждой шашки pi посмотрим, делится ли n на pi. Если да, то нужно решать меньшую задачу: образовать число n/p[i] с помощью пяти шашек, получаемых удалением шашки i из набора. Если n не делится ни на одну из шашек или если поиск шашки, на которую делится n, потерпел неудачу, то для каждой шашки i ищем решение задачи: образовать n + p[i] или n − p[i] с помощью 5 шашек, получаемых изъятием шашки i из набора. Но здесь мы довольствуемся решением, которое должно иметь вид произведения одной из шашек на комбинацию четырех остальных.

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

Я действую по-другому. Я помещаю 6 шашек в таблицу из 6 чисел, скажем a. В начале они упорядочены и расположены в неубывающем порядке. Чтобы изъять шашку из этого множества, мне достаточно переставить ее с шестой шашкой, а затем работать с первыми 5 элементами таблицы a. Таким образом, я создаю две процедуры: процедуру

П (p, x),

которая ищет способ представить x с помощью p первых значений таблицы a, причем это решение должно иметь вид произведения одной из шашек на некоторую комбинацию остальных (П поставлено для решения в виде Произведения);

процедуру

О (p, x),

которая ищет решения задачи о формировании x из p первых шашек, в котором результат имеет какую-нибудь из форм, предложенных в формулировке задачи (О — от Общее),

Программа довольствуется чтением 6 шашек (в порядке возрастания) и числа n, которое нужно найти, а затем вызывает О (6, n).

Вся задача состоит в том, чтобы поддерживать часть таблицы от 1 до p в неубывающем порядке. Это нетрудно. Вот схематическое описание процедуры П. В нем t является глобальной булевой переменной, которой присвоено начальное значение ЛОЖЬ.

П (p, x)

ЕСЛИ p < 3 ТО упрощенная форма;

КОНЧЕНО КОНЕЦ_ЕСЛИ

i := p

ВЫПОЛНЯТЬ

  ЕСЛИ x = a[p] ТО ИСТИНА; КОНЧЕНО

  КОНЕЦ_ЕСЛИ

up := x/a[p]; u = целая_часть(up)

  ЕСЛИ u = up ТО О (p − 1, u);

    ЕСЛИ t ТО ВЫВЕСТИ u, '*', а [р], '=', x

    КОНЧЕНО КОНЕЦ_ЕСЛИ

  КОНЕЦ_ЕСЛИ

  i := i − 1; ЕСЛИ i = 0 ТО

  КОНЧЕНО КОНЕЦ_ЕСЛИ

  переставить (i, p)

ВЕРНУТЬСЯ

Вы покажете, что часть от 1 до р − 1 остается расположенной в неубывающем порядке. Но при выходе из цикла в p стоит элемент, который меньше всех остальных. Следовательно, нужно восстановить исходный порядок в части от 1 до p, если t не принимает значения ИСТИНА (в противном случае все кончено). Это вы легко изобретете.

Процедура О вдохновляется той же идеей, но есть два цикла:

— один, приводящий в p все элементы один за другим;

— другой, который приводит в p − 1 элементы, расположенные ниже того, который попал в p.

В конце каждого цикла нужно восстанавливать порядок. Эти восстановления порядка могут показаться дорогостоящими. Они стоят не меньше переписывания одной таблицы в другую со сравнением каждый раз по трем индексам, где добавляются перестановки таблицы в качестве формальных параметров процедуры. Здесь а — глобальная таблица.

Наконец, нужно заметить, что эта процедура прекрасно подходит для итеративного переписывания, Создаем вектор x, дающий искомое число для каждого p. Как и выше, индексы i и j процедур Па О связаны с p. Наконец, переменную p сделали глобальной. Мне кажется достаточно очевидным, что итеративная процедура не пойдет намного быстрее рекурсивной процедуры: придется делать много проверок, которые выполнялись автоматически на уровне машинного языка, исполняющей системой. Но это и есть способ выйти из положения в случае, если, к несчастью, у нас нет рекурсивности.

Если у вас есть предубеждения против рекурсии, то сейчас подходящий момент избавиться от них. И бросьте думать, что рекурсия всегда дорого обходится. Она всегда сокращает время программирования. Неверно, что она всегда приводит к более медленному вычислению (эта головоломка и есть пример). Я соглашусь с вами, что она всегда занимает немного больше места…

Эта процедура, действуя на 6 шашек

100 75 50 25 10 10,

быстро находит число 370, но терпит неудачу для 369.

7. Обо всем понемногу

Головоломка 29.

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

— прежде всего нет никакой уверенности в том, что поступающее число удастся эффективно разместить между двумя числами таблицы. Оно может оказаться перед первым элементом и после последнего элемента. Так как эта возможность влечет появление некоторых особенностей, то наши программисты начинают с изучения этих случаев, что совершенно ненужно;