начальной таблицы шашек в другую, перепрыгивая через шашки, подлежащие изъятию,
Я действую по-другому. Я помещаю 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.
Головоломка 29.
Эта задача также не должна была бы излагаться ошибающимися людьми. Я пытался понять, где эти программисты оступаются. Я считаю, что есть две опасности:
— прежде всего нет никакой уверенности в том, что поступающее число удастся эффективно разместить между двумя числами таблицы. Оно может оказаться перед первым элементом и после последнего элемента. Так как эта возможность влечет появление некоторых особенностей, то наши программисты начинают с изучения этих случаев, что совершенно ненужно;
— далее поиск должен происходить с помощью разделения каждый раз таблицы на две части. Сравниваем x со средним элементом. Если он больше, то нужно искать его место в верхней полутаблице. В противном случае он — в нижней половине. Но средний элемент — это элемент с индексом k = (1 + n)/2 или, в наиболее общем случае, где рассматривается кусок таблицы, начинающийся в p и кончающийся в q, — элемент с индексом (p + q)/2. Конечно, рассматривается только целая часть дроби. По этой причине некоторые программисты опасаются, что это может заставить обращаться много раз к одному и тому же элементу, и тогда программа не остановится или может вызвать потерю элемента.
Это — пустые опасения. Возьмем как общую следующую ситуацию: пусть мы смогли найти такие два целых p и q, что
a[p] < x ? a [q], причем p < q.
Тогда все очевидным образом завершено, если q = p + 1.
В противном случае скачок между q и p не меньше 2, и
