основой, формулировкой и предполагаемым методом решения. Большинство из них допускает вариации, так что преподаватель может привязать задачу к конкретным условиям.
Разнообразие предлагаемых композиций весьма велико. Некоторые этюды требуют прежде всего интеллектуальных усилий (гл. 9), у других основная трудность заключена в реализации (гл. 12); есть совсем короткие этюды (гл. 16) и, напротив, очень длинные (гл. 6); в некоторых используются широкоизвестные методы реализации (гл. 5), в других же (гл. 2) методы реализации можно непрерывно совершенствовать. Главы 25–28 образуют связный цикл, который можно включить в курсы по языкам программирования и системам. Для выполнения этих этюдов нужно подобрать группы студентов, обладающих необходимыми знаниями по системному программированию (как правило, раньше студенты и не подозревали, что работа в группе программистов — совсем не то же самое, что работа в одиночку). Главы 5, 6, 13, 17, 19 и 25 могут дать хороший материал для курса по моделированию на ЭВМ, а гл. 6, 11, 14, 19, 20 связаны с задачами искусственного интеллекта. Разумеется, широко представлены также традиционные задачи по информатике.
Студенты, выполняющие лабораторный практикум, смогут оценить четкие формулировки задач. (Сколько несчастных поклялось никогда в жизни и близко к машине не подходить после отчаянных попыток разобрать неряшливые формулировки, нечетко отпечатанные на ротапринте.) Те же студенты, которые могли сами выбирать задачи (как в курсе, послужившем основой этой книги), оценят разнообразие предоставляемого им здесь выбора — ни одному преподавателю не хватило бы энергии подготовить столько задач. Разумеется, наш сборник, равного которому по объему еще не было, окажется полезным тем, кто повышает свою квалификацию самостоятельно. Отдельные этюды могут послужить источником методов программирования для лиц, уже окончивших учебные заведения.
Как и всегда в подобных случаях, книга не могла быть написана без помощи многих и многих людей. Джордж Майкл впервые выдвинул идею обучения на задачах (которая теперь нашла признание во многих других учебных заведениях). Студенты нескольких групп охотно испытывали задачи, предлагая исправления и даже новые темы. Хэнк Молл написал программу форматирования текстов, при помощи которой была подготовлена рукопись книги, и всегда был готов по мере надобности вносить в свою программу изменения. Рукопись с включенными в нее иллюстрациями была напечатана изящными шрифтами благодаря программе Джона Битти. Обе эти программы позволили лучше представить себе окончательный внешний вид книги, что очень помогло автору при ее создании. Многие мои друзья читали, обсуждали и критиковали книгу и ободряли автора. Наконец, перфораторщицы Ливерморской лаборатории не только никогда не жаловались на плохой почерк, а всегда быстро возвращали готовые колоды карт, да еще с исправленными орфографическими ошибками. Не будь всех этих помощников — не было бы и книги; лишь благодаря их участию она увидела свет.
1.
Что бы это значило?
или Как читать книгу
Преподавание программирования — дело почти безнадежное, а его изучение — непосильный труд. Преподаватель может всячески возиться со студентами, читать лекции, делать критические замечания, направлять по верному пути. Студент[3] может все тщательно записывать, запоминать, читать, сдавать зачеты, дискутировать хоть до двух часов ночи. Но все усилия тщетны, если студент не будет практиковаться в написании программ, поскольку навык программирования (как, впрочем, и всякий навык) дается только практикой. Более того, учиться надо на «настоящих» программах, а не на упрощенных примерах, вроде тех, которыми изобилует большинство руководств по языкам программирования. Сколько ни бренчи чижика, вторым Рубинштейном не станешь. Точно так же долбежка языка APL вряд ли поможет вам достичь высот в программировании. Поэтому в настоящей книге представлены довольно объемистые задачи. В качестве учебных проектов они вполне подойдут новичкам, стремящимся стать сначала просто грамотными программистами, а затем и специалистами высокого класса.
Способности, необходимые программисту, можно сравнить с теми, которые требуются, например, очеркисту. Как и очеркист, программист должен владеть некоторыми правилами правописания и грамматики, но, вопреки общепринятому мнению, для них обоих это не главное. Гораздо важнее быть наблюдательным и ищущим, уметь анализировать и ясно выражать свои мысли. Перечислим те способности, которые жизненно необходимы всякому программисту (и очеркисту тоже).
Способность читать и понимать описание поставленной задачи, улавливать пожелания того, кто ее ставит (что не всегда легко, так как и задачи, и те, кто их ставит, часто отличаются именно неуловимостью).
Способность четко видеть действительные трудности и отбрасывать все, не относящееся к делу.
Способность выявлять все случаи, где можно применить теорию, самостоятельно решиться на ее применение или обратиться за советом к специалисту.
Способность разбить задачу на ряд обозримых независимых частей и понять взаимосвязи этих частей.
Способность оценивать эффективность предлагаемых решений с точки зрения затрат на программирование, машинных ресурсов и удовлетворения потребностей пользователя и находить приемлемый компромисс между этими видами эффективности.
Способность объединять множество частных решений воедино, получая при этом четкое и изящное решение всей задачи.
Способность выражать решения на простом и понятном языке. Естественный это язык или искусственный — роли не играет, важно лишь, чтобы правильность решения была ясна и людям, и машине.
И наконец, способность при неудаче подавить самолюбие и поискать другой подход (или даже другую задачу).
Способности эти, как видим, столь сложны и многообразны, что приобрести их можно только на практике. Этюды дают возможность отработать конкретные технические приемы. Накапливая опыт, студент постепенно приобретает качества, необходимые программисту.
Составлять этюды, однако, не так просто, как может показаться. Все еще слишком часто задачки из книжек по программированию представляют собой просто технические «упражнения для пальцев». Полезные для выработки навыков уверенного использования простейших языковых конструкций, они редко бывают «высокохудожественными», что требуется от этюда в определении, приводимом в энциклопедическом словаре. Несмотря на то что этюд — упражнение, «основанное на определенном техническом приеме исполнения» (см. тот же словарь), хороший этюд должен быть достаточно большим, чтобы ощущалась взаимосвязь этого приема с другими областями программирования. Все это наталкивает на мысль взять задачи непосредственно из жизни. «Настоящие» задачи, однако, изобилуют несущественными деталями, требуют обработки массы данных, порождают гору результатов и к тому же меняются чуть ли не каждый день, так как руководство никак не может принять окончательное решение. Из студента, способного освоить профессию прямо в производственном коллективе, конечно, выйдет прекрасный специалист, но слишком многие из обучающихся программированию таким образом не выдерживают и, отчаявшись, бросают. Так что этюд должен лежать где-то посередине между реальной жизнью и тривиальными упражнениями. Две области — игры и информатика — породили, в сущности, почти все эти этюды и наделили их рядом полезных черт. Программисты, как правило, интересуются и тем, и другим приложением (уж лучше бы только информатикой, разумеется). Поскольку культура — всеобщее достояние, большинство игр доступно пониманию каждого; объяснить прикладную задачу в наше время также нетрудно. Очень часто поведение игровой программы или, скажем, транслятора поддается строгому описанию, так что корректность решения можно проверить. Входные данные обычно невелики по объему, и готовить их легко; выходные данные легко воспринимаются. Обе упомянутые области требуют применения
