Первый пример пошагового составления программы
Маленькие примеры, с которыми мы имели дело до этого, не являются репрезентативными для программ, которые приходится делать: они на несколько порядков меньше. Опытный программист "видит" их с одного взгляда, он может думать о них без карандаша и бумаги. Они по размеру не превышают параграфа, тогда как мы должны иметь дело с программами, размером со страницу, главу или книгу, и в конечном счете - цитируя А.Перлиса - с программами, длина которых больше, чем может поместиться в голове у программиста! Составление таких очень больших программ выходит за пределы этой маленькой монографии, но наименьшее, что мы можем сделать, это показать читателю, как организовать свое мышление при составлении программ, скажем, страничного размера. Если при чтении последующего читатель подумает, что я слишком скрупулезен, он должен имеет в виду программы размера главы. (Если это его все же не убедит, он должен изучить программу размера страницы, сделанную неаккуратным программистом: он обнаружит, что даже на одной странице достаточно места для большого объема отвратительной и интеллектуально вредной необоснованной сложности!)
Итак, начнем. Рассмотрим последовательность, составленную из единиц, двоек и троек, которая содержит только пары разных соседних непустых подпоследовательностей. Примерами правильных последовательностей являются:
1
12312
3212321
Примерами неправильных последовательностей являются:
11
12323131
32132132132
По всей видимости, список правильных последовательностей является бесконечным. Проблема состоит в следующем: допустим, что есть, как минимум, одна правильная последовательность длиной 100 (т.е., состоящая из 100 цифр), сделать программу, генерирующую начало этого списка правильных последовательностей в алфавитном порядке вплоть до первой последовательности длиной 100 включительно. (Алфавитный порядок следует соглашению, что 1 предшествует 2, 2 предшествует 3; критерий может быть переведен в числовой, если поставить десятичную точку перед началом последовательности и затем интерпретировать последовательность как десятичную дробь. По этому соглашению алфавитный порядок является порядком возрастания величины.)
Я интенсивно использовал этот пример в устных экзаменах. После некоторой начальной перепалки большинство студентов открывали для себя
- что неправильная последовательность никогда не может быть сделана правильной расширением ее, т.е., все правильные последовательности являются либо последовательностью,состоящей из одной цифры, либо расширением на одну цифру правильной последовательности;
- если последовательность B является правильным расширением на одну цифру последовательности A, последовательность A предшествует последовательности B в алфавитном порядке, т.е., за правильной последовательностью следуют все ее возможные расширения;
- алфавитный порядок требует, чтобы за правильной последовательностью A сначала следовало ее расширение, начинающееся с 1 (если оно есть), за ним - начинающееся с 2 (если есть), за ним - начинающееся с 3 (если есть).
Эти наблюдения ведут к следующему правилу:
правильная последовательность должна быть отпечатана и расширена единицей, как следующая пробная последовательность; для неправильной последовательности, завершающая тройка (если она есть) должна быть удалена и последняя цифра (теперь не тройка) должна быть увеличена на 1, что дает следующую пробную последовательность.
Начало списка, который должен быть сгенерирован, такое:
1
12
121
1213
12131
121312
1213121
1213123
.......
Он генерируется рассмотрением следующего списка пробных последовательностей (изъятые элементы помечены *):
1
* 11
12
121
* 1211
* 1212
1213
12131
* 121311
121312
1213121
* 12131211
* 12131212
* 12131213
* 1213122
1213123
.......
Многие из них затем предлагают программу следующей структуры:
Программа 1:
УСТАНОВИТЬ ПОСЛЕДОВАТЕДЬНОСТЬ В ЕДИНИЦУ И ДЛИНУ В 1;
repeat if ПРАВИЛЬНАЯ then begin ПЕЧАТАТЬ; РАСШИРИТЬ ЕДИНИЦЕЙ end
else МОДИФИЦИРОВАТЬ
until length > 100
в которой примитив "РАСШИРИТЬ ЕДИНИЦЕЙ" расширяет данную последовательность единицей, а примитив "МОДИФИЦИРОВАТЬ" увеличивает последнюю цифру на 1 после удаления последней тройки (если она есть). (При определении операции "МОДИФИЦИРОВАТЬ" последовательность, остающаяся после удаления последней тройки, не должна быть пустой; это следует из того факта, что список, который должен, как известно, иметь длину = 100.)
Множество возражений может быть выдвинуто против программы, сделанной по этому эскизу. Одно из возражений состоит в том, что в начале выполнения повторяющегося оператора длина будет 
100 и, кроме того, мы знаем, что операция "МОДИФИЦИРОВАТЬ" никогда не увеличивает длину, тем не менее, такая модификация предшествует во времени проверке длины, и первое возражение, следовательно, что такая проверка не нужна. Более серьезное возражение состоит в мучительности рассуждений, требующихся для установления того, что с условием окончания все в порядке. Вместо того, чтобы останавливаться, когда в первый раз будет напечатано решение длиной 100, приходится останавливаться, когда будет сгенерирована первая пробная последовательность длиной < 100. Ясно, что приведенная программа никогда не выработает решения длиной больше 100, поскольку такая длинная пробная последовательность никогда не будет проверяться проверкой "ПРАВИЛЬНАЯ". Показать, однако, что программа остановится после выработки первого решения длиной = 100, гораздо труднее.
Значительно более приятная программа базируется на том наблюдении, что мы можем рассматривать пустую последовательность как виртуальное решение, которое не нужно печатать.
Программа 2:
УСТАНОВИТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ ПУСТОЙ И ДЛИНУ В 0;
repeat РАСШИРИТЬ ЕДИНИЦЕЙ;
while non ПРАВИЛЬНАЯ do МОДИФИЦИРОВАТЬ;
ПЕЧАТАТЬ
until length = 100
Выдвинутые возражения уже недействительны. Однако правильная причина, по которой приведенная программа гораздо более привлекательна, находится в том наблюдении, что мы можем мысленно соединить первые два оператора повторяющегося оператора. Вышеприведенная версия усовершенствуется до более абстрактной.
Программа 3:
УСТАНОВИТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ ПУСТОЙ И ДЛИНУ В 0;
repeat ПРЕОБРАЗОВАТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ В СЛЕДУЮЩЕЕ РЕШЕНИЕ;
ПЕЧАТАТЬ
until length = 100
(Примечание. В Программах 1, 2 и 3 внешний цикл также может управляться фразой while.)
Заметьте, что здесь, в Программе 3, мы имеем уровень описания, на котором пробные последовательности исчезают! Этот уровень описания может пониматься только в терминах решения. Разделением, т.е., мысленным выделением оператора "ПРЕОБРАЗОВАТЬ ПОСЛЕДОВАТЕДЬНОСТЬ В СЛЕДУЮЩЕЕ РЕШЕНИЕ" и последующим его совершенствованием мы отделили задачу формулирования корректного критерия для завершения от того, как будет выполняться переход от одного решения к следующему через множество пробных последовательностей, которые могут отбрасываться. Памятуя об ограниченном размере головы программиста, разделение является жизненно важным достижением, поскольку оно позволяет нам иметь дело только с чем-то одним за раз.
Чтобы показать, что все это не просто праздная игра словами, мы сделаем программу, взяв за отправную точку Программу 3. Как сюрприз, мы достигнем улучшения, отличающего от Программы 2, без существенного изменения алгоритма. (Хотя я интенсивно использовал этот пример на экзаменах, следующая версия возникла у меня только при написании этого текста! Это только показывает, что такие абстрактные программы являются жизненно важными этапами в процессе наших конструктивных рассуждений!)
Чтобы определить это усовершенствование, вернемся на шаг назад и спросим себя, что позволило нам сделать переход от Программы 1 к Программе 2. Это было введение пустой последовательности как "виртуального решения". В Программе 1 первое решение было задано, тогда как остальные генерировались; В Программах 2 и 3 все решения для печати генерировались одним и тем же оператором "ПРЕРБРАЗОВАТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ В СЛЕДУЮЩЕЕ РЕШЕНИЕ".
При преобразовании этого оператора должна быть сгенерирована пробная последовательность, и в Программе 2 мы находим, что критерий "ПРАВИЛЬНАЯ" должен быть применен к пробным последовательностям, сгенерированным двумя способами, при помощи либо "РАСШИРИТЬ ЕДИНИЦЕЙ", либо "МОДИФИЦИРОВАТЬ". Можем ли мы привести в порядок нашу модификацию, утверждением, что все пробные последовательности, которые будут проверяться, должны генерироваться одним оператором? Да, можем, просто изменив оператор расширения и просто обобщив оператор "МОДИФИЦИРОВАТЬ", как в следующей модификации:
ПРЕРОБРАЗОВАТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ В СЛЕДУЮЩЕЕ РЕШЕНИЕ:
РАСШИРИТЬ НУЛЕМ;
repeat МОДИФИЦИРОВАТЬ until ПРАВИЛЬНАЯ
Здесь "ПРАВИЛЬНАЯ" обозначает более сложную функцию; альтернативная форма использует булевскую переменную "good" и приводит нас к задаче преобразования оператора "УСТАНОВИТЬ ПРАВИЛЬНОЕ".
ПРЕРОБРАЗОВАТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ В СЛЕДУЮЩЕЕ РЕШЕНИЕ:
boolean good;
РАСШИРИТЬ НУЛЕМ;
repeat МОДИФИЦИРОВАТЬ; УСТАНОВИТЬ ПРАВИЛЬНОЕ until good
(Примечание. В приведенной выше модификации повторение не управляется фразой while. Почему?)
Теперь пришло время принять решение о представлении "последовательности". Она имеет свойство "length", удовлетворяющее неравенству 0 length 100, и она является упорядоченной последовательностью из length цифр. Подходящим средством для представления этой последовательности является линейный массив целых переменных. Мы предлагаем объявление integer array d[1;100], так что в любой момент последовательность может быть представлена как
d[1], d[2], ... , d[length]
Мы хотим указать, что это хорошо мотивированное решение. Альтернативным решением может быть:
d[101 - length], d[102 - length], ... , d[100]
но по последнему соглашению все операции, изменяющие длину последовательности, будут подразумевать изменение величие вверх или вниз, тогда как в предложенном представлении сохраненные значения могут "оставаться там, где они есть". Если выбранное соглашение применить ко всем обрабатываемым последовательностям (т.е., как к решениям, так и к пробным последовательностям), то следующие четыре модификациями являются вполне очевидными. ( В отношении их выбранное представление является определенно адекватным.)
УСТАНОВИТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ ПУСТОЙ И ДЛИНУ В 0:
length:= 0
РАСШИРИТЬ НУЛЕМ:
length:= length +1; d[length]:= 0
МОДИФИЦИРОВАТЬ
while d[length] = 3 do length:= length +1; d[length]:= 0
ПЕЧАТАТЬ:
i:=0; repeat i:= i + 1; printdigit(d[i]) until i = length; newline
где мы предположили доступность примитивов "printdigit" и "newline" для перехода на начало новой строки вывода. Единственной модификацией, которая все еще может вызывать головную боль, является оператор "УСТАНОВИТЬ ПРАВИЛЬНОЕ".
Исследовать произвольную последовательность, на самом деле, - ужасная задача, но она становится гораздо легче, если мы используем то обстоятельство, что последовательности, которые являются субъектами проверки, являются только пробными последовательностями, а каждая пробная последовательность является расширением на одну цифру правильной последовательности (более ранней). В результате чего она может нарушить условие только в своем последнем элементе, включенном в одну из последовательностей, т.е., она может быть забракована как неправильная, если существует такое m (удовлетворяющее 0 < 2 * m length), что пара соседних "m-последовательностей"
d[length - 2 * m + 1], ... , d[length - m] и
d[length - m + 1], ... , d[length]
равны. Предполагая доступность оператора для сравнения таких пар "m-последовательностей" (для произвольно заданного m), наша первая модификация для "УСТАНОВИТЬ ПРАВИЛЬНОЕ" такая
УСТАНОВИТЬ ПРАВИЛЬНОЕ:
integer m;
good:= true; m:= 1;
while 2 * m ≶= length and good do
begin ПРИДАТЬ GOOD ЗНАЧЕНИЕ ТОГО, ЧТО M-ПОСЛЕДОВАТЕЛЬНОСТИ РАЗНЫЕ;
m:= m + 1
end
или (возможно, лучше)
УСТАНОВИТЬ ПРАВИЛЬНОЕ:
integer m, mbound;
good:= true; mbound:= length div 2; m:= 1;
while m ≶= mbound and good do
begin ПРИДАТЬ GOOD ЗНАЧЕНИЕ ТОГО, ЧТО M-ПОСЛЕДОВАТЕЛЬНОСТИ РАЗНЫЕ;
m:= m + 1
end
Здесь оператор div является целочисленным делением, округляющим частное до ближайшего целого в направлении нуля. Двойное условие для продолжения повторений выражает, что исследование может быть остановлено, как только будет найдена равная пара, и этого достаточно, чтобы определить, что последовательность неправильная. Мы видели эту конструкцию в конце предыдущего раздела.
Вопрос. Альтернативной формой может быть
integer m;
good:= true; m:= length div 2;
while m > 0 and good do
begin ПРИДАТЬ GOOD ЗНАЧЕНИЕ ТОГО, ЧТО M-ПОСЛЕДОВАТЕЛЬНОСТИ РАЗНЫЕ;
m:= m + 1
end
Почему мы предлагаем производить исследование в порядке увеличения m?
Наконец, мы модифицируем сравнение двух "m-последовательностей"
ПРИДАТЬ GOOD ЗНАЧЕНИЕ ТОГО, ЧТО M-ПОСЛЕДОВАТЕЛЬНОСТИ РАЗНЫЕ:
integer firstend, k;
firstend:= length - m; k:= 0;
repeat good:= (d[length - k) 
d[firstend - k]);
k:= k+1
until k = m or good
опять-таки выражает, что сравнение двух "m-последовательностей" может быть прекращено, как только будет установлено, что они в чем-то отличаются.
Собирая все объявления и вставляя модификации - сохранив их имена как метки для ясности - мы получаем полную программу, показанную ниже. Последовательные уровни детализации показаны при помощи семантики использования отступов.
begin integer array d[1:100]; boolean good; integer length, i, m, mbound, k, firstend;
УСТАНОВИТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ ПУСТОЙ И ДЛИНУ В 0:
length:= 0;
repeat ПРЕОБРАЗОВАТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ В СЛЕДУЮЩЕЕ РЕШЕНИЕ:
РАСШИРИТЬ НУЛЕМ:
length:= length + 1; d[length]:= 0;
repeat МОДИФИЦИРОВАТЬ:
while d[length] = 3 do length:= length - 1;
d[length]:= d[length] + 1;
УСТАНОВИТЬ ПРАВИЛЬНУЮ:
good:= true; m:= 1; mbound:= length div 2;
while m mbound and good do
begin ПРИДАТЬ GOOD ЗНАЧЕНИЕ ТОГО, ЧТО M-ПОСЛЕДОВАТЕЛЬНОСТИ РАЗНЫЕ:
firstend:= length - m; k:= 0;
repeat good:= (d[length - k] d[firstend - k]);
k:= k + 1
until k = m or good
until k = m or good
end
until good;
ПЕЧАТАТЬ:
i:= 0; repeat i:= i + 1; printdigit(d[i]) until i = length; newline
until length = 100
end
* *
*
Упражнение. Дан линейный массив из 36 позиций, сделать программу, генерирующую все возможные (если они есть) способы, при которых эти позиции могут быть заполнены нулями и единицами (по одной цифре в позиции), так, чтобы 32 пятерки из пяти соседних чисел представляли 32 различных образца пятиразрядных двоичных чисел, ограничивая себя последовательностями, начинающимися с четырех нулей. Ч. Лигтман показал, что любое такое решение должно заканчиваться четырьмя нулями. Его аргумент следующий. Каждое решение должно начинаться с 000001..., потому что образец 00000 должен появляться только раз. Где-то в последовательности образец 10000 должен появляться только раз; поскольку за этим образцом может следовать только 0 или 1, следующей за ним пятеркой может быть либо 00000, либо 00001, уже представленные первыми двумя пятерками. В результате образец 10000 не может появиться внутри линейной последовательности и, следовательно, он должен быть последним образцом. Из наблюдения Лигтмана следует, что мы можем замкнуть кольцо, сделав последние четыре нуля перекрывающими начальные четыре нуля. Различные образцы затем выстраиваются в цикле по 32 позициям.
Образцы должны генерироваться в алфавитном порядке.
Обсуждение и некоторые советы
Я гарантирую, что для последовательности из 36 двоичных чисел существует вычислимая булевская функция, устанавливающая, представляет ли последовательность решение, и что мы можем написать алгоритм для ее вычисления. В принципе, мы можем написать программу, генерирующую все 36-цифровые последовательности с пятью ведущими нулями в алфавитном порядке и подвергнуть все эти последовательности упомянутой проверке, выбирая те, которые удовлетворяют проверке. Это даст очень нереалистическую программу, и мы не будем ее рассматривать; мы только отметим, что генерация пробных последовательностей в алфавитном порядке гарантирует, что решение, если оно будет найдено, также будет в алфавитном порядке.
Программа, которая должна быть сделана, может рассматриваться как производная от кратко описанной выше, а именно, введением некоторых важных сокращений. В настоящее время мы дополнительно ничем не будем нагружать это отношение.
Вместо того, чтобы генерировать все 36-цифровые последовательности и выбирать из этого ряда, мы намерены генерировать значительно меньший ряд, который будет гарантировано содержать все решения. Давайте назовем "длиной последовательности" число пятерок, содержащихся в ней (т.е., длина = число цифр - 4). Давайте назовем последовательность "приемлемой", если никакие две разные пятерки в ней не представляют один и тот же цифровой образец. При таком определении решения будут подмножествами множества приемлемых последовательностей, а именно, тех, длина которых = 32.
Мы не знаем, имеются ли вообще какие-то решения, но мы знаем, что множество приемлемых решений не пустое (напр., "00000"); мы не имеем готового критерия для распознания "последнего решения, когда мы его встретим; в нашем множестве приемлемых решений, однако, мы можем назвать виртуально, как минимум, одно (а именно, "10000"); когда оно встретится, мы знаем, что все приемлемые последовательности с пятью ведущими нулями просмотрены и что больше решений найдено не будет.
Подводя итоги, мы знаем, что множество приемлемых последовательностей:
- не пустое и конечное
- мы знаем первый элемент ("00000")
- мы знаем виртуальный последний элемент ("10000")
- мы можем преобразовать приемлемую последовательность в следующую приемлемую последовательность
- решениями являются все приемлемые последовательности, удовлетворяющие дополнительному условию длина = 32
- никакое расширение последовательности, которая не является приемлемой, не будет приемлемым.
Последнее свойство делает эту проблему, выражаясь математически, очень похожей на предыдущую.
Совет. Проверка приемлемости может быть значительно ускорена сведением в таблицу пятерок, которые не найдены в последовательности.
Замечание. Эта проблема трудна и выработка красивой программы может занять у вас много часов. Но эти часы будут чрезвычайно хорошо использованы.