Организация групп и последовательностей
Пока мы рассматриваем подход к программированию, при котором четко распознается иерархия уровней абстракции. Материал данного раздела применим также к программированию на языках программирования в том виде, как они понимаются в настоящее время, т. е. на уровне неизменяемой семантики. (И есть основания полагать, что выводы этого раздела применимы за рамками ограниченной области программирования, поскольку они касаются решения проблем в общем случае.)
Я проиллюстрирую мою основную мысль на двух примерах, которые я тоже использовал на устных экзаменах. Первым примером я обязан Н. Вирту.
Задача состоит в том, чтобы построить программу, генерирующую непустые последовательности из цифр О, 1 и 2 без непустых поэлементно совпадающих соседних подпоследовательностей; эти последовательности требуется генерировать в лексикографическом порядке до тех пор, пока не будет получена последовательность длины 100 (т. е. из ста цифр). Программист может использовать известный факт, что удовлетворяющая этим условиям последовательность длины 100 действительно существует. Список последовательностей, которые должны генерироваться, начинается так:
0 01 010 0102 01020 010201 0102010 0102012 .......
Мы занимаемся поиском "хороших" последовательностей и предполагаем, что имеется элементарная операция проверки, является ли испытуемая последовательность хорошей. Если она хорошая, то эта последовательность печатается и расширяется присоединением нуля, что дает новую испытуемую последовательность. Если же последовательность не является хорошей, мы выполняем над ней операцию "увеличить" для получения следующей испытуемой последовательности; при этом имеющиеся в конце цифры 2 удаляются, а последняя оставшаяся цифра увеличивается на 1. (Операции "расширить нулем" и "увеличить" обеспечивают лексикографический порядок генерации испытуемых последовательностей; поэтому выбираемые из них решения будут печататься также в лексикографическом порядке.)
Алгоритм начнется с исследования приведенных ниже испытуемых последовательностей; те последовательности, которые помечены звездочками, будут отвергнуты как "нехорошие",
0 *00 01 010 *0100 *0101 0102 01020 *010200 010201 0102010 *01020100 *01020101 *01020102 *0102011 0102012 .......
Я заметил, что большинство моих студентов были склонны писать программу со следующей структурой:
установить в исходную последовательность одиночный нуль, repeat if хорошая then
begin печатать испытуемую последовательность; расширить испытуемую последовательность нулем end else
увеличить испытуемую последовательность until длина=101
Хотя эта программа дает правильный результат, она может (и мне бы хотелось сказать - должна) вызывать возражения. Первое возражение относится к критерию останова. Когда будет напечатано решение длины 100, мы (зная алгоритм) можем сообразить, что после этого начальная испытуемая последовательность будет иметь длину 101, а это и есть критерий останова. Однако такой способ обоснования критерия останова является слишком обходным и неестественным. (То, насколько он неестественный, ярко продемонстрировали студенты, которые не замечали, что генерируется лишняя испытуемая последовательность, и описывали испытуемую последовательность как массив из 100 элементов, а не из 101). Второе возражение состоит в том, что операция "увеличить испытуемую последовательность" никогда не увеличивает длину этой последовательности; поэтому, после того как отвергается испытуемая последовательность, выполняется ненужная проверка длины. (Я использовал этот пример на студенческих экзаменах, не выделив перед этим в своих лекциях общие принципы решения проблем, и поэтому не испытывал особой досады. В каком-то смысле я даже был доволен впечатлением от этих экзаменов, потому что оно оказалось для меня побудительным мотивом к тому, чтобы разобраться как можно глубже в принципах решения проблем, сформулировать и преподавать их.) Приведенные выше возражения не применимы к следующей программе, в которой пустая последовательность трактуется как действительное решение, которое не должно печататься. На том же уровне детализации эта программа имеет следующую структуру:
установить испытуемую последовательность пустой; repeat расширить испытуемую последовательность нулем; while не хорошая do увеличить испытуемую последовательность; печатать испытуемую последовательность until длина=100
Здесь длина - это длина печатаемого решения (если оно есть); это избавляет нас от неестественного обоснования прежнего критерия останова. Кроме того, не будет генерироваться впустую избыточная последняя испытуемая последовательность (которая даже не проверялась) и не будет более появляться лишняя проверка длины; поскольку теперь у нас два цикла; один внутри другого. Последнее соображение, вероятно, окажется наиболее убедительным для тех, кто считает эффективность главным критерием. Лично я, придавая существенное значение понимаемости, отдаю предпочтение второй программе, потому что могу интерпретировать ее как конкретизацию следующей программной структуры:
установить последовательность пустой; repeat преобразовать последовательность в следующее решение; печатать последовательность until длина=100
Эта (более абстрактная) программа имеет дело только с теми последовательностями, которые являются решениями: на этом уровне описания можно игнорировать то обстоятельство, что переход от одного решения к следующему осуществляется через некую последовательность испытуемых решений, которые оказываются неподходящими. Вторым примером я обязан Дж. Вейзенбауму. Нужно составить программу, которая для заданного положительного целого п определяет наименьшее число s, которое может быть разложено в сумму вида аn+bn по крайней мере двумя нетривиально различными способами.
(Для n=1 s=2=01-21=11+11 n=2 s=25=02=52=32+42
n=4 s=635318657=594-1584=1334+1344)
Когда я впервые использовал этот пример на устном экзамене, студент потратил двадцать минут на то, чтобы как-то разобраться в задаче, а затем набросал алгоритм поиска, который, если бы его слегка подправить, действительно позволял бы найти число, допускающее различные разложения в суммы вида аn+bn. Однако студент не мог доказать, что вырабатываемое его алгоритмом значение s было бы минимальным значением. (Фактически он до последнего момента просто игнорировал эту часть постановки задачи.) Затем он перестроился и написал программу следующего вида:
integer s, k; s:=l; repeat s:=s+1; k:="число способов разложения s на сумму вида an+bn" until k>1
получив при этом безнадежно неэффективный алгоритм. Его ошибка состояла в том, что он решил на слишком раннем этапе последовательно исследовать натуральные числа, подавляющее большинство которых вовсе не допускают нужного разложения. Если же принять во внимание, что мы ищем значение минимального разложимого числа, удовлетворяющего некоему дополнительному требованию, то мы приходим к алгоритму, первый набросок которого может иметь такой вид:
integer k, s, t; t:=1 (и другие начальные установки); repeat s:="минимальное разложимое значение, превышающее t" k:="число способов разложения этого минимального значения" t:=s until k>1
Можно накапливать в памяти множество триплетов (пар чисел с соответствующими s-значениями), в которых каждый раз будут представлены одна или несколько пар с минимальным s-значением, превышающим t, и перестраивать это множество всякий раз, когда увеличивается значение t. При этом получается программа, которая более эффективно обеспечивает продвижение t от одного разложимого значения к следующему разложимому значению. Итак, речь идет о программировании (а может быть, о решении проблем в общем случае?) методом разумной отсрочки решений и оформлений!
