Программирование игр и головоломок
Шрифт:
П (p, x),
которая ищет способ представить x с помощью p первых значений таблицы a, причем это решение должно иметь вид произведения одной из шашек на некоторую комбинацию остальных (П поставлено для решения в виде Произведения);
процедуру
О (p, x),
которая ищет решения задачи о формировании x из p первых шашек,
Программа довольствуется чтением 6 шашек (в порядке возрастания) и числа n, которое нужно найти, а затем вызывает О (6, n).
Вся задача состоит в том, чтобы поддерживать часть таблицы от 1 до p в неубывающем порядке. Это нетрудно. Вот схематическое описание процедуры П. В нем t является глобальной булевой переменной, которой присвоено начальное значение ЛОЖЬ.
Вы покажете, что часть от 1 до р– 1 остается расположенной в неубывающем порядке. Но при выходе из цикла в p стоит элемент, который меньше всех остальных. Следовательно, нужно восстановить исходный порядок в части от 1 до p, если t не принимает значения ИСТИНА (в противном случае все кончено). Это вы легко изобретете.
Процедура О вдохновляется той же идеей, но есть два цикла:
— один, приводящий
— другой, который приводит в p– 1 элементы, расположенные ниже того, который попал в p.
В конце каждого цикла нужно восстанавливать порядок. Эти восстановления порядка могут показаться дорогостоящими. Они стоят не меньше переписывания одной таблицы в другую со сравнением каждый раз по трем индексам, где добавляются перестановки таблицы в качестве формальных параметров процедуры. Здесь а — глобальная таблица.
Наконец, нужно заметить, что эта процедура прекрасно подходит для итеративного переписывания, Создаем вектор x, дающий искомое число для каждого p. Как и выше, индексы i и j процедур Па О связаны с p. Наконец, переменную p сделали глобальной. Мне кажется достаточно очевидным, что итеративная процедура не пойдет намного быстрее рекурсивной процедуры: придется делать много проверок, которые выполнялись автоматически на уровне машинного языка, исполняющей системой. Но это и есть способ выйти из положения в случае, если, к несчастью, у нас нет рекурсивности.
Если у вас есть предубеждения против рекурсии, то сейчас подходящий момент избавиться от них. И бросьте думать, что рекурсия всегда дорого обходится. Она всегда сокращает время программирования. Неверно, что она всегда приводит к более медленному вычислению (эта головоломка и есть пример). Я соглашусь с вами, что она всегда занимает немного больше места…
Эта процедура, действуя на 6 шашек
100 75 50 25 10 10,
быстро находит число 370, но терпит неудачу для 369.
7. Обо всем понемногу
Головоломка 29.
Эта задача также не должна была бы излагаться ошибающимися людьми. Я пытался понять, где эти программисты оступаются. Я считаю, что есть две опасности:
— прежде всего нет никакой уверенности в том, что поступающее число удастся эффективно разместить между двумя числами таблицы. Оно может оказаться перед первым элементом и после последнего элемента. Так как эта возможность влечет появление некоторых особенностей, то наши программисты начинают с изучения этих случаев, что совершенно ненужно;
— далее поиск должен происходить с помощью разделения каждый раз таблицы на две части. Сравниваем x со средним элементом. Если он больше, то нужно искать его место в верхней полутаблице. В противном случае он — в нижней половине. Но средний элемент — это элемент с индексом k = (1 + n)/2 или, в наиболее общем случае, где рассматривается кусок таблицы, начинающийся в p и кончающийся в q, — элемент с индексом (p + q)/2. Конечно, рассматривается только целая часть дроби. По этой причине некоторые программисты опасаются, что это может заставить обращаться много раз к одному и тому же элементу, и тогда программа не остановится или может вызвать потерю элемента.