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

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

КОНЕЦ_ЕСЛИ

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, и так как p меньше q, то, следовательно, элемент с промежуточным номером

r = целая_часть (( p + q )/2)

обязательно отличается от элементов с номерами p и q , и вам нечего опасаться. Вы сравниваете x с элементом с индексом r и в зависимости от результата сравнения берете r либо как новую нижнюю границу p , либо новую верхнюю границу q .

Остается одна трудность. Как выбрать p и q , чтобы так пустить в ход процесс, чтобы выполнялось общее двойное неравенство? Всегда, когда приходится выполнять обращение к таблице, представляет интерес введение дополнительных элементов, освобождающих от влияния концов таблицы. Введем элемент с индексом 0, меньший, чем любой из тех x , к которым можно обратиться (мы отложим на более поздний срок решение вопроса, как мы можем сделать это эффективно), и элемент с номером n + 1, больший, чем все возможные x . Тогда x обязательно больше, чем a [0], и меньше, чем a [ n + 1].

Тогда мы можем начать с p = 0 и q = n + 1. Напишите соответствующую программу, вовсе не заботясь заранее о значениях a [0] и a [ n + 1] и оставляя в неопределенном положении задачу эффективного описания таблицы (некоторые языки, такие как Фортран или LSE, не допускают индекса ноль — один только бог знает почему…). Покажите, что единственный индекс, для которого фактически приходится читать значение элемента таблицы, — это индекс r . Так как r всегда строго содержится в интервале ( p , q ), причем p не убывает, a q не возрастает, то r всегда строго больше 0 и не меньше n . Таким образом, элементы 0 и n + 1 никогда не опрашиваются. Поэтому и нет необходимости их материализовывать. Объявите массив (таблицу) с индексом, пробегающим от 1 до n , и все пройдет без сучка и задоринки…

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

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

100 i = 0; j := 0.

110 продвинуть i к ближайшему символу в цепочке a , не являющемуся пробелом

120 ЕСЛИ мы вышли из a ТО ПЕРЕЙТИ К 200 КОНЕЦ_ЕСЛИ

130 продвинуть j к ближайшему символу в цепочке b , не являющемуся пробелом

140 ЕСЛИ мы вышли из b ТО ПЕРЕЙТИ К 300 КОНЕЦ_ЕСЛИ

150 ЕСЛИ a [ i ] = b [ j ] ТО ПЕРЕЙТИ К 110

160 ПЕРЕЙТИ К 800

200 продвинуть j к ближайшему символу в цепочке b , не являющемуся пробелом

210 ЕСЛИ мы вышли из b ТО ПЕРЕЙТИ К 900 КОНЕЦ_ЕСЛИ

220 ПЕРЕЙТИ К 800

300 продвинуть i к ближайшему символу в цепочке а , не являющемуся пробелом

310 ЕСЛИ мы вышли из a ТО ПЕРЕЙТИ К 900 КОНЕЦ_ЕСЛИ