Более детальные проектные рассмотрения
Предыдущие разделы (в частности, "Первый пример поэтапного составления программы") вызывали критические замечания о том, что я слишком упрощенно трактую процесс проектирования программ, доходя почти до грани мошенничества. Я не считаю эту критику совсем безосновательной и, чтобы исправить дело, разберу два примера более детально. Первый пример придуман мною. Я испробовал его на нескольких устных экзаменах, а впоследствии закончил им свой лекционный курс "Введение в искусство программирования". Я поставил эту задачу перед аудиторией из пятидесяти человек, и все вместе, с моим направляющим участием, они решили ее в течение 90 минут.
Мы рассматриваем множество символов, состоящее из букв, пробела (пр) и точки (тчк). Слова образуются из одной или нескольких, но не более чем из двадцати букв. Входной текст состоит из одного или нескольких слов; соседние слова разделяются одним или несколькими пробелами; за последним словом может следовать любое число пробелов (в частности, нуль), и весь входной текст заканчивается точкой. С помощью символьной функции ЧОС (Чтение очередного символа) следует прочесть входной текст от первой буквы первого слова и до завершающей точки включительно.
Для выдачи выходного текста нужно использовать элементарную функцию ПОС(х) (т, е. Печать очередного символа) с символьным значением параметра. Если бы задача программы состояла в том, чтобы копировать текст, то годилась бы следующая программа (в предположении, что мы умеем работать с переменными, принимающими символьные значения):
char x; repeat х:=ЧОС; ПОС(x) until x= тчк
Однако в этом примере текст нужно подвергнуть следующему преобразованию:
- в выходном тексте соседние слова должны разделяться одним пробелом;
- в выходном тексте сразу же за последним словом должна стоять одиночная точка;
- если присвоить словам номера 0, 1,2, 3, ... в порядке слева направо (т. е. в том порядке, в каком они считываются при повторяемом вычислении функции ЧОС), то слова с четными номерами должны копироваться, тогда как буквы из слов с нечетными номерами должны печататься в обратном порядке.
Например, входной текст
"эта---программа-никуда-не-годится--",
нужно преобразовать в вид
"эта-аммаргорп-никуда-ен-годится."
(Здесь "-" используется для представления пробела). Я самым искренним образом советую читателям прежде, чем читать дальше, попытаться составить эту программу самостоятельно и записать свои соображения в таком виде, чтобы можно было сравнить их с тем, что я предложу далее. (У опытного программиста это должно занять гораздо меньше времени, чем 90 минут.) Поскольку неизвестна длина непустого входного текста, представляется естественной следующая структура программы:
увертюра; repeat нечто until готово; финал
Однако сразу встает вопрос: "С чем же мы имеем дело, когда однократно выполняем "нечто"?" Возникают четыре предположения. Это может оказаться
- одним символом входного текста;
- одним символом выходного текста;
- словом (из обоих текстов);
- двумя соседними словами (из обоих текстов).
Первые два предположения сразу же были отвергнуты без особых объяснений, хотя (а может быть, потому что) объяснить это нетрудно. (Первый вариант не подходит из-за того, что за счет очередного символа входного текста можно выработать самое различное количество выходной информации; аналогичное возражение справедливо и для второго предположения. Помимо всего прочего, программа с циклом в цикле оказывается в общем случае более наглядной, а это наводит на мысль искать более крупные части.) Аудитория отвергла четвертое предположение на том основании, что завершающая точка могла бы с такой же вероятностью оказаться после нечетного числа слов, как и после четного. Чтобы выявить выбор третьего варианта, мы написали на доске:
увертюра; repeat обработать очередное слово until чтение точки; финал
Все были удовлетворены, поскольку эта программа четко выражает тот факт, что мы имеем дело с выходными словами точно в том порядке, в каком читаются соответствующие входные слова; однако в ней не отражено, что половина слов должна печататься в перевернутом виде.
Это было указано слушателям, после чего они быстро ввели соответствующую специальную переменную. Сначала поступило предложение подсчитывать число обработанных слов и выполнять обработку в зависимости от четности или нечетности содержимого этого счетчика, но кислое выражение моего лица оказалось достаточным для догадки, что в этой ситуации лучше воспользоваться логической переменной. Решили, что "увертюра" должна включать
вперед:=true
а в операции "обработать очередное слово" нужно вслед за печатью, порядок которой зависит от текущего значения "вперед", выполнить
вперед:=non вперед
Меня очень обрадовало, что они ввели переменную "вперед" до того, как стали вникать в подробности отделения слов, которыми они занялись потом. У них ушло больше времени на то, чтобы осознать, что дальнейшая конкретизация действия "обработать очередное слово" требует точного описания тех символов входного текста, которые предполагается читать, и тех символов выходного текста, которые предполагается печатать при выполнении повторяемого оператора. В действительности мне пришлось обратить их внимание на это обстоятельство, после чего я спросил их, в каком из двух текстов организация групп представляется более естественной. Они предпочли выходной текст и выбрали следующую организацию групп (указывая разделение вертикальной чертой):
|эта-|аммаргорп-|никуда-|ен-|годится.|
т, е. разбиение на слова, сопровождаемые соответствующим разделителем. Затем я попросил организовать соответствующие группы из входных символов. Сосредоточив внимание на разделителях, они предложили следующее разделение входных символов (справа налево!):
|эта---п|рограмма--н|икуда-н|е--г|одится--.|
так как один из них заметил, что нашей программе достаточно "знать", что за выходным словом нужно ставить пробел, "увидев" первую букву следующего входного слова. Я хранил молчание, предоставив им разобраться в выбранной ими организации групп символов, пока один из них не обнаружил, что особая организация группы символов для первого входного слова является неизящной и что группы следует организовать так:
э|та---п|рограмма--н|икуда-н|е--г|одится--.|
т.е. что первый символ первого слова должен быть прочтен в увертюре. Была введена еще одна переменная, и у нас получилась следующая программа:
boolean вперед; char x; вперед:=true; х:=ЧОС; repeat обработать очередное слово; вперед:=non вперед until х=тчк
Здесь вторая строка представляет увертюру. В то же время мы решили, что финал может быть пустым. Этот этап был достигнут после первых 45 минут, и затем последовал небольшой перерыв. Лично я сознавал, что проблема уже решена и что остальное - дело техники. Однако моя аудитория оказалась недостаточно опытной, и на завершение программы ушли все последующие 45 минут. Слушатели единодушно решили ввести массив
char array с [1:20]
для запоминания букв из слова. (Никто не заметил, что считывание букв и выдача их в обратном порядке на печать могли выполняться рекурсивной программой.) В сущности, нужно производить четыре действия: читать буквы из слова, печатать буквы из слова, читать информацию, необходимую для выбора печатаемого разделителя, и печатать этот разделитель. Я не перечислял эти четыре действия и не спрашивал у слушателей, как бы они решили вопрос о том, как эти действия будут группироваться или объединяться. Аудитория решила, что следует сначала все прочитать, а затем все напечатать. (Вряд ли такое решение можно считать разумным.)
Пытаясь конкретизировать процессы чтения и печати, они столкнулись с неожиданным препятствием. По крайней мере меня удивило, как медленно до них доходило, что требуется еще определить взаимосвязь между чтением и печатью для передачи обрабатываемых слов независимо от того, что эта взаимосвязь тривиальна. Прошло довольно много времени, прежде чем все осознали, что значение с[i] следует приравнять t-й букве из слова, читаемого слева направо. Чуть ли не половина слушателей недоумевала, из-за чего мы суетимся, но потребовалось много времени и на то, чтобы установить, что требуется также некоторая форма представления длины слова.
Никто не предложил использовать для этого запоминание разделителя; они ввели специальную целую переменную "l" для подсчета числа букв в слове. Было решено, что первое слово "эта" следует представлять следующим образом:
с[1]="э", с[2]="т", с[3]="а" и l=3.
Они продолжали испытывать затруднения по поводу вхождения в цикл чтения, и только когда я повторил: "итак, мы решили, что "l" предназначается для представления числа букв слова, запомненных в массиве", они приняли решение начать процесс чтения так:
l:=0; repeat l:=l+1; c[l]:=x; x:=ЧОС until x=прx=тчк
(в первом наброске было пропущено "x=тчк", но это быстро исправили). После того как эта запись появилась на доске, они завершили процесс чтения без особых затруднений:
while x=пр do x:=ЧОС
Когда мы переключили внимание на процесс печати, дело пошло быстрее. Разумеется, процесс чтения прояснил задачу взаимосвязи, и предложения посыпались со всех сторон. До этого я не знакомил слушателей с проблемой, кодировать ли заголовок альтернативы между двумя повторениями или же заголовок повторения применительно к оператору альтернативы (см. стр. 33). Я ждал пока эта проблема естественно возникнет, здесь она встретилась, и я продемонстрировал ее аудитории. Неожиданно для меня один из студентов предложил совместить оба цикла с помощью дополнительных переменных. Мы ввели три целых переменных "k, доб, разд", и печать букв приобрела вид
if вперед then begin k:=0; доб:=+1; разд:=l end
else begin k:=l+1; доб:=-1; разд:=1 end; repeat k:=k+доб; ПОС(с[k]) until k=разд
а далее следовало
if x=тчк then ПОС(тчк) else ПОС(пр)
Итак, мы пришли к следующей программе:
boolean вперед; char x; char array с[1:20]; integer l, k, доб, разд; вперед:=true; x:=ЧОС; repeat l:=0; repeat l:=l+1; c[l]:=x; x:=ЧОС until x=np х=тчк; while x=пр do х:=ЧОС; if вперед then begin k:=0; доб:=+1; разд:=l end
else begin k:=l+1; доб:=-1; разд:=l end
repeat k:=k+доб; ПОС(с[k]) until k=разд; if x=тчк then ПОС(тчк) else ПОС(пр); вперед:=non вперед until x=тчк
Я включил этот раздел вовсе не потому, что в нем рассматривается интересная задача. Напротив, хочется отметить, что эта задача выглядит слишком тривиальной для того, чтобы служить хорошим тестовым материалом для методического анализа проблемы составления программ. Этот раздел включен, потому что правдиво отражает то, что произошло в классной комнате. Следует рассматривать его как частичный ответ на часто задаваемый мне вопрос, до какой степени я способен научить стилю программирования. (Я никогда не пользовался в своей педагогической практике "Заметками по структурному программированию", предназначенными в основном для себя и своих коллег. Описанный в этом разделе учебный эксперимент был поставлен в конце курса "Введение в искусство программирования", для которого я подготовил отдельный конспект лекций с упражнениями и всем подобающим. Когда я пишу эти строки, моим студентам еще предстоит сдавать экзамен, и поэтому для меня остается открытым вопрос, насколько я преуспел в своих лекциях студентам. Курс им нравится, я слыхал, что они называют мои программы "логическими поэмами", так что у меня есть основания для оптимизма.)
