Ю.Ю. Громов и др. Информатика (2007)

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

Псевдокод. При построении алгоритма человек должен учитывать влияние большого количества связанных идей. Эта задача может выходить за рамки возможностей человеческого разума. Джордж А. Миллер (George A. Miller) в своей статье 1956 г. "Психологическое обозрение" (Psychological Review) изложил результаты исследования, которое показало, что человек может манипулировать одновременно только семью элементами. Поэтому разработчику сложных алгоритмов необходимо средствозаписичастейалгоритмадляпоследующеговозвращения кним.

В50-х и 60-х гг. XX в. для создания алгоритмов использовались блок-схемы, в которых алгоритм изображался с помощью геометрических фигур, соединенных стрелками. Однако блок-схемы часто становились запутанной паутиной переплетающихся стрелок, что значительно осложняло понимание лежащего в основе алгоритма. Поэтому блок-схемы уступили дорогу другим средствам проектирования алгоритмов. Примером может послужить псевдокод (pseudocode), в соответствии с которым алгоритмы записываются с помощью строго определенных текстовых структур (примитивов), предназначенных для неформального представления идей в процессе разработки алгоритмов.

Один из путей создания псевдокода состоит в простом ослаблении правил того формального языка программирования, на котором требуется записать окончательную версию алгоритма. Этот подход обычно используется, когда целевой язык программирования известен заранее. В подобной ситуации псевдокод, используемый на ранних стадиях разработки программы, может состоять из синтаксических и семантических структур, аналогичных структурам целевого языка программирования, но не столь формализованных.

Взаключение стоит отметить, что блок-схемы могут быть полезны, когда целью является изображение алгоритма, а не его построение. Например, на рис. 4.8 и 4.9 используется представление в виде блок-схемы, чтобы наглядно продемонстрировать алгоритмические структуры, представленные операторами управления.

Поиск лучших средств записи все еще продолжается. В главе 6 мы увидим, что сохраняется тенденция использования графики в создании крупных систем программного обеспечения, а псевдокод остается распространенным средством разработки меньших процедурных компонентов системы.

Пример псевдокода. Начиная с этого момента, мы отказываемся от использования команд формального языка программирования в пользу менее формальной и более интуитивной системы обозначений, известной как псевдокод.

Однако наша задача – рассмотреть проблемы разработки и представления алгоритмов, не концентрируя внимание на каком-либо определенном языке программирования. Поэтому выбранный здесь подход к созданию псевдокода состоит в разработке непротиворечивой и краткой системы обозначений для представления повторяющихся семантических структур.

Всвою очередь, эти структуры станут примитивами, с помощью которых мы попытаемся выразить дальнейшие идеи.

Одна из таких повторяющихся семантических структур – присвоение значения описательному имени. Например, будем использовать для значений такие имена: Температура, СуммарноеКоличествоОсадков, БалансБанка и Положение. Для установления связи между именем и значением будем использовать форму

имя ← выражение

где имя – это описательное имя, а выражение описывает значение, которое присваивается этому имени. Такое утверждение читается как "присвоить имени значение выражения". Например, утверждение

Итог ← Цена + Налог

присваивает результат сложения значений Цена и Налог имени Итог.

Другая повторяющаяся семантическая структура – выбор одного из действий в зависимости от истинности или ложности какого-либо условия.

Примеры:

Если валовой внутренний продукт растет, покупать обыкновенные акции; в противном случае продавать обыкновенные акции.

Покупать обыкновенные акции, если валовой внутренний продукт растет, и продавать их в противном случае.

Покупать или продавать обыкновенные акции в зависимости от того, растет или уменьшается валовой внутренний продукт.

Каждое из этих предложений можно переписать так, чтобы оно соответствовало следующей структуре: if (условие) then {действие} else {действие}

В этой структуре ключевые слова if (если), then (то) и else (иначе) используются для того, чтобы объявить различные подструктуры внутри основной структуры, а скобки позволяют обозначить границы этих подструктур. Включив такую синтаксическую структуру в наш псевдокод, мы получаем универсальный способ описания указанной общей семантической структуры. Этоиестьто, чтотребовалосьсделать.

Рассмотрим приведенное ниже предложение.

В зависимости от того, является год високосным или нет, разделить итог на 366 или 365, соответственно.

Хотя приведенный выше вариант больше отвечает литературному стилю, мы будем использовать следующую его вер-

сию:

if (год високосный) then {разделить итог на 366} else {разделить итог на 365}

Мы также примем сокращенный синтаксис этого конструкта: if (условие) then {действие}

Он будет использоваться в случаях, когда не предусмотрено действие для варианта else. Используем эту схему для следующего предложения:

В случае уменьшения объема продаж снизить цену на 5 %.

Применение ее позволяет сократить исходный вариант следующим образом: if (продажи сократились) then {снизить цену на 5 %}

Другая универсальная алгоритмическая структура заключается в необходимости продолжать выполнение последовательности инструкций до тех пор, пока некоторое условие остается верным. Ниже приведено несколько неформальных примеров этой структуры.

До тех пор, пока есть билеты для продажи, продолжать продавать билеты. Пока есть билеты для продажи, продолжать продажу билетов.

Для подобных случаев в нашем псевдокоде будет применяться следующий универсальный шаблон: while (условие) do {действие}

Коротко говоря, эта инструкция предписывает проверить условие и, если оно верно, выполнить действие, а затем вновь проверить условие. Если при очередной проверке условие оказывается неверным, следует перейти к инструкции, следующей за данной структурой. Таким образом, оба предшествующих примера при записи на псевдокоде будут выглядеть следующим образом:

while (имеются билеты, которые можно продать) do {продавать билеты}

Использование отступов при размещении текста позволяет повысить читабельность программы:

if (товар налогооблагаемый) then {if (цена > минимум)

then {платить х} else {платить у}

}

else {платить z}

Эта конструкция воспринимается легче, чем ее эквивалент, приведенный ниже:

if (товар налогооблагаемый) then {if (цена > минимум) then {платить х} else {платить у}} else {платить z}

Поэтому мы договоримся использовать отступы для отражения структуры текста в нашем псевдокоде. (Заметим, что мы даже будем выравнивать скобки, связанные с внешней конструкцией then, чтобы отметить начало и окончание этой структуры.)

Мы собираемся использовать наш псевдокод для описания действий, которые могут выступать в роли абстрактных вспомогательных программ в других приложениях. В компьютерных науках такие программные элементы имеют несколько различных названий, а именно: подпрограммы, процедуры, модули и функции (значение каждого из них имеет свой смысловой оттенок). Договоримся применять к нашему псевдокоду термин процедура (procedure), используя его для обозначения заголовка, по которому можно будет распознать данный блок псевдокода. Точнее говоря, мы будем начинать каждый блок псевдокода со следующей инструкции:

procedure имя

Здесь имя – это конкретное название, присвоенное данному блоку. Ниже будут следовать инструкции, определяющие выполняемые в этом блоке действия. Например, на рис. 4.4 представлен псевдокод процедуры с именем Приветствие, в которой трижды печатается сообщение "Привет".

procedure Приветствие Счетчик ← 3

while (Счетчик > 0) do

{напечатать сообщение “Привет”; Счетчик ← Счетчик - 1}

Рис. 4.4. Процедура "Приветствие", записанная на псевдокоде

Когда где-либо в псевдокоде потребуется выполнить действия, реализованные в некоторой процедуре, эта процедура будет просто вызываться по имени. Например, пусть две процедуры имеют имена Предоставление3айма и ОтклонениеЗаявки, соответственно. Тогда мы сможем включить их выполнение в структуру if-then-else, написав следующую инструкцию:

if (...)

then {выполнить процедуру Предоставление3айма} else {выполнить процедуру ОтклонениеЗаявки}

В результате процедура Предоставление3айма будет выполняться, если проверяемое условие истинно, а процедура Отклонение-Заявки – если это условие ложно.

Процедура должна быть общей насколько это возможно. Например, процедура для сортировки списка имен должна сортировать любой список, а не какой-то один. То есть она должна быть написана так, чтобы параметры сортируемого списка задавались не в самой процедуре. Вместо этого в представлении процедуры список должен быть представлен формаль-

ным параметром.

В нашем псевдокоде мы будем записывать формальные параметры в скобках сразу после имени процедуры. Например, процедура с именем Сортировка, которая сортирует любой список имен, будет начинаться следующей инструкцией

Procedure Сортировка (список)

Если дальше в представлении упоминается сортируемый список, то для него используется имя Список. А когда мы вызываем процедуру Сортировка, мы задаем, какой именно список нужно отсортировать. Для этого можно использовать, например, следующий синтаксис:

Применить процедуру Сортировка к списку членов организации.

В зависимости от наших потребностей, мы можем применить другой вариант синтаксиса:

Применить процедуру Сортировка к списку гостей на свадьбе.

Не забывайте, что назначение нашего псевдокода состоит в предоставлении средств, позволяющих записывать схемы алгоритмов лишь в общих чертах, а не в написании законченных формальных программ. Поэтому мы не связаны запретом использования неформальных фраз, запрашивающих такие действия, детали которых не определены достаточно строго. (Как именно будут разрешены эти детали, не столь уж важно для описания алгоритма, поскольку это касается только свойств языка, на котором будет написана формальная программа).

В то же время, если позже мы обнаружим, что определенная идея повторяется в обсуждаемых нами схемах, то мы примем соответствующий синтаксис для ее представления и этим расширим наш псевдокод.

Вопросы для самопроверки

1. То, что является примитивом в одном контексте, может, в свою очередь, быть составлено из примитивов другого контекста. Например, инструкция while является примитивом в нашем псевдокоде, хотя она является сложной конструкцией из нескольких команд машинного языка. Приведите два примера подобных явлений из области, не связанной с компьютерами.

2.В каком смысле построение процедур является построением примитивов?

3.Алгоритм Евклида позволяет найти наибольший общий делитель двух положительных целых чисел X и Y с помощью следующего процесса:

до тех пор, пока значения X и Y отличны от нуля, выполнять деление большей величины на меньшую и присваивать переменным X и Y значения делителя и остатка, соответственно. (Конечное значение X является наибольшим общим делителем.)

Запишите этот алгоритм с помощью нашего псевдокода.

4.Опишите набор примитивов, используемых не в программировании, а в какой-либо другой области.

4.3. СОЗДАНИЕ АЛГОРИТМА

Разработка программы состоит из двух различных действий – создания алгоритма ее работы и представления этого алгоритма в виде программы. До настоящего момента мы рассматривали только способы представления алгоритмов и не касались вопроса, как, собственно, эти алгоритмы создаются. Однако создание алгоритма – это, как правило, наиболее сложный этап в процессе разработки программного обеспечения. В конце концов, создать алгоритм – означает найти метод решения задачи, в решении которой и состоит назначение этого алгоритма. Поэтому, чтобы понять, как создаются алгоритмы, необходимо понять процесс решения задач.

Теория решения задач. Рассмотрение методов решения задач и их подробное изучение не являются аспектами, специфическими только для компьютерных наук. Напротив, это важно практически для любой области науки. Тесная связь между процессом создания алгоритмов и общей проблемой поиска решения задач привела к сотрудничеству специалистов в области компьютерных систем и ученых из других областей науки в поисках лучших методов решения задач. В конечном счете, желательно было бы свести проблему решения задач к алгоритмам как таковым, но это оказалось невозможным. (В главе 11 будет показано, что существуют задачи, не имеющие алгоритмических решений.) Таким образом, способность решать задачи в значительной степени является профессиональным навыком, который необходимо развивать, а не точной наукой, которую можно изучить.

Решение задач является скорее искусством, чем наукой. Доказательством этого может служить тот факт, что представленные ниже, весьма расплывчато определенные фазы решения задач, предложенные математиком Дж. Полиа (G. Polya) в 1945 г., остаются теми основными принципами, на которых и сегодня базируется обучение навыкам решения задач.

Фаза 1. Понять существо задачи.

Фаза 2. Разработать план решения задачи. Фаза 3. Выполнить план.

Фаза 4. Оценить точность решения, а также его потенциал в качестве средства для решения других задач. Применительно к процессу разработки программ эти фазы выглядят следующим образом.

Фаза 1. Понять существо задачи.

Фаза 2. Предложить идею, какая алгоритмическая процедура позволяет решить задачу. Фаза 3. Сформулировать алгоритм и представить его в виде программы.

Фаза 4. Оценить точность программы и ее потенциал в качестве средства для решения других задач.

Необходимо подчеркнуть, что предложенные математиком Полиа фазы не являются этапами, которым надо следовать при решении задачи. Скорее, это те фазы, которые должны быть когда-либо выполнены в процессе ее решения. Здесь ключевое слово – следовать, т.е. просто "следуя", вы не сможете решить задачу. Напротив, чтобы решить задачу, необходимо проявлять инициативу и двигаться вперед. Если подходить к решению задачи по принципу: "Ну вот, я закончил фазу 1, пора переходить к фазе 2", то вряд ли вам будет сопутствовать успех. Однако если вы с головой окунетесь в решение задачи и, в конечном счете, решите ее, то, оглянувшись назад, обязательно увидите, что выполнили все четыре фазы, предложенные математиком Полиа.

Кроме того, необходимо заметить, что эти четыре фазы не обязательно выполняются в указанном порядке. Как отмечают многие авторы, те, кто успешно решают задачи, часто начинают формулировать стратегию решения (фаза 2) еще до того, как полностью смогут понять существо задачи (фаза 1). Впоследствии, если выбранные стратегии так и не приведут к успеху (что проявится во время фазы 3 или 4), решающий задачу человек все же приобретет более глубокое понимание сути задачи и, основываясь на этом понимании, сможет вновь вернуться к формулированию других, возможно, более успешных стратегий.

Не забывайте, что здесь мы обсуждаем, как задачи решаются, а не то, как бы нам хотелось, чтобы они решались. В идеале хотелось бы полностью исключить изнурительный по своей сути процесс проб и ошибок, описанный выше. При разработке крупной системы программного обеспечения обнаружение неправильного понимания лишь на фазе 4 может привести к огромным потерям ресурсов. Избежать таких катастроф – основная задача разработчиков программного обеспечения (глава 6), которые традиционно настаивают на том, что полное осмысление задачи должно предшествовать ее решению. Можно возразить, что истинное понимание задачи невозможно, пока не будет найдено ее решение. Тот факт, что решить задачу не удается, подразумевает недостаток ее понимания. Следовательно, настаивать на том, что нужно вначале полностью осознать задачу, прежде чем предлагать какое-либо ее решение, – это чистый идеализм. В качестве примера рассмотрим следующую задачу.

Предположим, что некто А хочет определить возраст трех детей некоего В. Этот В сообщает А, что произведение возрастов его детей равно 36. Обдумав эту подсказку, А отвечает, что необходима еще подсказка, и B сообщает ему сумму возрастов его детей. Затем А отвечает, что требуется еще подсказка, и В говорит ему, что старший из детей играет на пианино. Услышав эту подсказку, А сообщает В возраст всех трех его детей. Сколько лет детям?

На первый взгляд может показаться, что последняя подсказка совсем не имеет отношения к задаче, хотя именно она позволила А окончательно определить возраст детей. Как это может быть? Давайте двигаться вперед, формулируя план и следуя ему, несмотря на то, что у нас еще остается много вопросов по поводу этой задачи. Наш план будет состоять в том, чтобы отслеживать этапы, описанные в условии задачи, учитывая информацию, доступную А по мере развития событий.

В первой подсказке сообщалось, что произведение возрастов детей равно 36. Это означает, что искомые значения образуют одну из троек, перечисленных на рис. 4.5, а. Следующая подсказка указывала сумму искомых значений. Нам неизвестно, чему именно равна эта сумма, но мы знаем, что этой информации оказалось недостаточно, чтобы А смог выбрать правильную тройку. Следовательно, искомая тройка должна быть одной из тех, которые имеют одинаковые суммы в списке на рис. 4.5, б. Таких троек на рисунке две: (1, 6, 6) и (2, 2, 9); сумма членов каждой из них равна 13. Это та информация, которая была известна А на момент, когда он получил последнюю подсказку. Именно на данном этапе мы осознаем важность последней подсказки. Собственно умение играть на пианино не имеет никакого значения, важен тот факт, что в семье есть старший ребенок. Это позволяет отбросить тройку (1, 6, 6) изаключить, чтоодномуребенку9 лет, адвум– по2 года.

Рис. 4.5. Иллюстрация к задаче о трех детях:

а– тройки чисел, произведение которых равно 36;

б– суммы троек чисел, приведенных в а)

Это именно тот случай, когда, не попытавшись реализовать выбранный план решения (фаза 3), невозможно достичь полного понимания задачи (фаза 1). Если бы мы настаивали на завершении фазы 1, вместо того чтобы двигаться дальше, то, возможно, так и не смогли бы определить возраст детей. Такая неупорядоченность процесса решения задач является основной причиной трудностей, связанных с разработкой систематического подхода к решению задач.

Кроме того, существует и некое мистическое вдохновение, посещающее человека, решающего задачу. Оно проявляется в том, что, работая какое-то время над задачей без видимого успеха, позднее он неожиданно может найти ее решение при выполнении совершенно другого задания. Этот феномен был обнаружен ученым Г. фон Гельмгольцем (Н. von Helmholtz) еще в 1896 г., а математик Анри Пуанкаре (Henri. Poincare) говорил о нем в своей лекции, прочитанной Психологическому обществу в Париже. Пуанкаре описал свой опыт, связанный с неожиданным осознанием способа решения задачи, которой он безуспешно занимался некоторое время, а затем отложил, обратившись к другим проблемам. Этот феномен отражает процесс, в котором подсознание осуществляет непрерывную работу над решением задачи и в случае успеха выталкивает найденный результат в сознание человека. В наши дни промежуток времени между процессом сознательного решения задачи ивнезапнымозарением получилназвание инкубационного периода. Исследования этогоявленияпродолжаются ивнастоящеевремя.

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

Перед соревнованиями участники А, В, С и D сделали следующие прогнозы: Участник А предсказал, что победит участник В.

Участник В предсказал, что участник D будет последним. Участник С предсказал, что участник А будет третьим. Участник D предсказал, что сбудется предсказание участника А.

Только один из этих прогнозов оказался верным, и это был прогноз победителя.

В каком порядке участники А, В, С и D закончили соревнования?

Ознакомившись с задачей и проанализировав приведенные в ее условии сведения, нетрудно заметить, что, поскольку прогнозы участников А и D эквивалентны, а верным оказался только один прогноз, прогнозы участников А и D неверны. Следовательно, ни участник А, ни участник D не являются победителями соревнования. Теперь можно считать, что первый шаг сделан. Для получения окончательного решения надо просто продолжить наши рассуждения. Поскольку прогноз участника А оказался неверным, значит, участник В также не стал победителем. Остается единственный возможный вариант, в котором победителем стал участник С. Итак, участник С выиграл соревнования, и его прогноз оказался верным. Отсюда можно сделать вывод, что участник А занял третье место. Это означает, что участники финишировали либо в порядке CBAD, либо в порядке CDAB. Но первый вариант нужно отбросить, так как прогноз участника В не оправдался. Следовательно, участники финишировали в порядке CDAB.

Конечно, сказать, что нужно сделать первый шаг и занять оптимальную позицию, – совсем не то же самое, что сказать, как это сделать. Первоначальный прорыв, а затем осознание того, как закрепить полученный успех, чтобы суметь найти окончательное решение задачи, потребуют значительных усилий от того, кто ее решает. Однако существует несколько общих подходов, предложенных математиком Полиа и другими исследователями, подсказывающими, как можно осуществить этот первоначальный прорыв. Один из подходов состоит в том, чтобы работать с задачей в обратном порядке. Например, если задача заключается в том, чтобы найти способ получения определенного конечного результата из заданного начального, можно начать поиск с конечного результата и попытаться пройти путь к заданному начальному. Этот подход будет полезен, если потребуется найти алгоритм складывания бумажной птички, упомянутый в предыдущем разделе. Логично начать с попытки развернуть сложенную птичку с целью понять, как она была сделана.

Другой общий подход к решению задачи состоит в поиске связанных с ней проблем, которые или легче решаются, или уже были решены раньше. Позже предпринимается попытка применить способ их решения к данной задаче. Этот метод особенно важен в контексте разработки программ. Часто при разработке программы основная трудность заключается в создании общего алгоритма для решения всех разновидностей данной задачи. Другими словами, если нам необходимо разработать программу для упорядочения списка имен в алфавитном порядке, наша задача не сводится к сортировке отдельного списка, а заключается в нахождении алгоритма, пригодного для сортировки любого списка имен. Рассмотрим следующий набор инструкций.

Поменять местами имена David и Alice. Поместить имя Carol между именами Alice и David. Поместить имя Bob между именами Alice и Carol.

Этот набор позволяет правильно выполнить сортировку списка, состоящего из имен David, Alice, Carol и Bob, но он не является тем общим алгоритмом, который мы ищем. Нам же нужен алгоритм, который в состоянии выполнить сортировку как данного списка, так и любого другого, который может встретиться. Однако найденное решение сортировки конкретного списка не является совершенно бесполезным для разработки общего алгоритма. Мы можем, например, продвинуться в решении, рассматривая такие частные случаи, как попытки найти oбщий принцип, которые, в свою очередь, послужат основой для создания искомого общего алгоритма. В этом случае искомое решение, в конце концов, будет найдено с помощью метода решения набора взаимосвязанных частных задач.

Еще один подход к проблеме "с чего начинать" заключается в применении метода поэтапного уточнения, который предполагает, что задачу не следует пытаться решить сразу же и целиком во всех ее деталях. Согласно этому методу, исследователь должен разбить задачу на ряд подзадач. Идея заключается в том, что при разбиении исходной задачи на подзадачи появляется возможность найти общее решение как последовательность этапов, на каждом из которых решается задача, более простая по сравнению с исходной. Поэтапное уточнение подразумевает также, что каждый из этапов, в свою очередь, можно разбить на меньшие, а те – на еще меньшие, так что, в конце концов, вся задача сводится к набору легко разрешимых подзадач.

Поэтапное уточнение является нисходящим методом, так как его развитие происходит в направлении от общего к частному. В противоположность этому, восходящие методы предусматривают развитие от частного к общему. Хотя в теории эти подходы противоположны, на практике они просто дополняют друг друга. Например, разбиение задачи, предлагаемое нисходящим методом поэтапного уточнения, обычно осуществляется интуитивно с использованием восходящей модели.

Решениям, полученным с помощью метода поэтапного уточнения, свойственна естественная модульная структура. Именно в этом кроется основная причина популярности этого метода при разработке алгоритмов. Если алгоритм имеет естественную модульную структуру, то он легко реализуется в модульном представлении, способствующем созданию удобных в сопровождении программ. Более того, модульная структура, создаваемая в процессе поэтапного уточнения, легко совмещается с концепцией коллективного программирования, в соответствии с которой несколько человек объединяются в команду, имеющую своей задачей разработку определенного программного продукта. После того как исходная задача будет разбита на подзадачи (потенциальные модули), члены команды смогут работать над ними независимо, не мешая друг другу.

Метод поэтапного уточнения пользуется широкой популярностью при разработке программного обеспечения. Однако, несмотря на все его преимущества, этот метод отнюдь не является последним словом науки в отношении создания алгоритмов. В сущности, он представляет собой только средство организации работы, и все его возможности по решению задач являются лишь следствием этой организации. Вполне естественно использовать метод поэтапного уточнения при организации общенациональной политической кампании, написании курсовой работы или заключении торгового соглашения. Аналогичным образом для большинства проектов разработки программного обеспечения из области обработки данных характерна большая роль организационного компонента. Задача этих проектов состоит не столько в создании нового сенсационного алгоритма, сколько в представлении решаемых задач таким образом, чтобы их можно было реализовать в виде согласованно функционирующего пакета программ. Поэтому метод поэтапного уточнения по праву стал основой всей методологии проектирования в области обработки данных.

Однако поэтапное уточнение остается всего лишь одной из многих методологий проектирования, представляющих интерес для специалистов в области компьютерных наук. Поэтому не следует впадать в заблуждение, полагая, что все алгоритмы могут быть созданы с помощью этого метода. Фактически применение при решении задач предвзятых представлений и заранее выбран-

ныхсхем внекоторых случаяхможетдажеусложнить изначально простоезадание. Рассмотрим следующуюзадачу.

Когда вы садились в лодку, ваша шляпа упала в воду, но вы этого не заметили. Скорость течения реки 2,5 мили в час, и ваша шляпа поплыла вниз по течению. Тем временем вы поплыли в лодке вверх против течения со скоростью 4,75 мили в час (относительно воды). Спустя 10 минут вы заметили пропажу шляпы, развернули лодку и поплыли вниз по реке догонять вашу шляпу. Через какое время вы поймаете свою шляпу?

Большинство студентов, изучающих алгебру в высшей школе, а также любителей карманных калькуляторов начнут решение этой задачи с определения, какое расстояние прошла лодка за 10 минут вверх по течению, и какое расстояние за это время проплыла шляпа вниз по течению. Затем они попытаются вычислить, сколько времени понадобится лодке, чтобы пройти вниз по течению до той точки, где находится шляпа. Но ведь пока лодка будет идти к этой точке, шляпа будет уплывать дальше вниз по течению! Таким образом, они, весьма вероятно, попадут в цикл вычислений, где будет находиться шляпа в тот момент, когда лодка достигнет того места, где шляпа была на предыдущем этапе расчета.

На самом же деле задача гораздо проще. Весь фокус состоит в том, чтобы суметь противостоять стремлению писать формулы и делать вычисления. Необходимо просто отложить эти навыки в сторону и взглянуть на задачу в ее истинном свете. Суть всей проблемы в реке. В данном случае тот факт, что вода движется относительно берегов, не имеет никакого значения. Представьте себе ту же задачу на длинной конвейерной ленте. Сначала решим поставленную задачу, когда лента неподвижна. Если вы, стоя на ленте, положите шляпу у своих ног, а затем будете идти вдоль ленты в течение 10 мин, то вернуться к шляпе вы сможете за те же 10 мин. Теперь включим конвейер. Это будет означать, что сначала вы пойдете против движения ленты. Но поскольку вы, как и шляпа, находитесь на ленте, это не изменит ваших взаимоотношений с лентой и шляпой. Вам по-прежнему потребуется 10 мин, чтобы вернуться к оставленной шляпе.

В результате можно прийти к заключению, что создание алгоритмов является сложным искусством, которое необходимо постоянно совершенствовать, а не изучать как предмет, состоящий из хорошо определенных методологий. Учить решать задачи, следуя четко определенным методологиям, значит "загубить" творческие способности учащихся, которые, напротив, нужно всемерно развивать.

Вопросы для самопроверки

1. Найдите алгоритм решения следующей задачи и ответьте на дополнительные вопросы.

а) Для заданного положительного числа n найдите такую комбинацию целых положительных чисел, произведение которых максимально среди всех возможных комбинаций целых положительных чисел, сумма которых равна n. Например, если n равно 4, то искомый список есть (2, 2), так как 2*2 больше, чем 1*1*1*1, 2*1*1 и 3*1. Для n, равного 5, искомая комбинация будет (2, 3).

б) Какова искомая комбинация для n = 2001?

в) Объясните, каквам удалось продвинуться врешенииэтойзадачи.

2. Найдите алгоритм решения следующей задачи и ответьте на дополнительные вопросы.

а) Пусть дана квадратная шахматная доска размером 2n ×2n , где n – целое положительное число, и коробка с L- образными фишками, каждая из которых может закрыть в точности три квадрата на доске. Если вырезать из доски один ка- кой-либо квадрат, сможем ли мы покрыть оставшуюся часть доски фишками таким образом, чтобы они не перекрывались и не выступали за край доски?

б) Объясните, как предложенное решение этой задачи может быть использовано, чтобы показать, что 2n −1 делится на 3 для любых целых положительных n.

в) Как ответы на два предыдущих вопроса связаны с фазами решения задач, предложенными математиком Полиа? 3. Декодируйте следующее сообщение и объясните, как вам удалось сделать первый шаг в поисках решения:

Pdeo eo pda yknnayp wjosan.

4.4. ИТЕРАЦИОННЫЕ СТРУКТУРЫ

Теперь нашей задачей является изучение некоторых повторяющихся структур, используемых при описании алгоритмических процессов. В этом разделе мы обсудим итерационные структуры, в которых выполнение набора инструкций повторяется в циклическом режиме. В следующем разделе рассматривается метод рекурсии. Читатель также сможет познакомиться с некоторыми популярными алгоритмами – последовательного и двоичного поиска, а также с алгоритмом сортировки методом вставки. Начнем с рассмотрения алгоритма последовательного поиска.

Алгоритм последовательного поиска. Рассмотрим задачу поиска в списке некоторого заданного значения. Необходимо разработать алгоритм, позволяющий установить, есть ли заданное значение в списке. Если это значение в списке присутствует, поиск будет считаться успешным, в противном случае будем считать его завершившимся неудачей. Будем считать, что список отсортирован согласно некоторому правилу, позволяющему упорядочить его элементы. Например, если это список имен, будем считать, что имена в нем расположены в алфавитном порядке. Если же это список числовых значений, будем полагать, что его элементы расположены в порядке возрастания.

Давайте попробуем представить, как бы мы действовали при поиске определенного имени в списке гостей, содержащем около 20 фамилий. В данном случае можно было бы просмотреть весь список от начала и до конца, сравнивая каждый его элемент с искомым именем. Если требуемое имя будет найдено, поиск завершится успешно. Однако, если будет достигнут конец списка или обнаружено имя, расположенное по алфавиту после искомого, поиск завершится неудачей. (Не забывайте, что список упорядочен в алфавитном порядке, поэтому если будет найдено имя, расположенное по алфавиту после требуемого, то это означает, что нужного нам имени в списке нет.) Таким образом, наша задача – выполнять последовательный просмотр элементов списка в направлении сверху вниз до тех пор, пока не будут проверены все имена или нужное нам имя не будет найдено.

С помощью нашего псевдокода этот процесс можно представить следующим образом:

Выбрать в качестве ПроверяемоеЗначение первый элемент Списка; while (ИскомоеЗначение > ПроверяемоеЗначение

и есть непроверенные элементы) do

{выбрать в качестве ПроверяемоеЗначение следующий элемент Списка}

По окончании выполнения структуры while искомое значение либо будет найдено, либо выяснится, что его нет в списке. В любом случае успешность поиска можно установить, сравнивая искомое значение с проверяемым. Если они эквивалентны, поиск успешен. Таким образом, в конец приведенной выше программы необходимо добавить следующую инструкцию:

if (ИскомоеЗначение = ПроверяемоеЗначение) then {сообщить об успехе}

else {сообщить о неудаче}

Наконец, в нашей программе предполагается, что первая инструкция, где в качестве проверяемого значения явно указан первый элемент списка, содержит, как минимум, один элемент. Конечно же, это условие могло бы выполняться всегда, однако для полной уверенности в правильности программы следует поместить составленную выше программу в предложение else следующей инструкции if:

if (Список пуст)

then {сообщить о неудаче} else {...}

В результате получается процедура, текст которой приведен на рис. 4.6. Заметим, что для поиска некоторых значений в списке другиепроцедурывполнемогут использоватьееспомощьюследующейинструкции:

Применить процедуру Поиск к списку пассажиров, чтобы найти имя "Даррел Бейкер"

Эта инструкция позволяет установить, является ли Даррел Бейкер пассажиром некоторого рейса. Вот еще один пример:

procedure Поиск (Список, ИскомоеЗначение) if (Список пуст)

then {сообщить о неудаче}

else {выбрать в качестве ПроверяемоеЗначение первый элемент Списка;

while (ИскомоеЗначение > ПроверяемоеЗначение и есть непроверенные элементы) do

{выбрать в качестве ПроверяемоеЗначение следующий элемент списка}

if (ИскомоеЗначение = ПроверяемоеЗначение) then {сообщить об успехе}

Рис. 4.6. Алгоритм последовательного поиска, записанный с помощью псевдокода

Применить процедуру Поиск к списку ингредиентов, используя в качестве искомого значения "мускатный орех"

Данная инструкция позволит установить, входит ли мускатный орех в перечень ингредиентов некоторого блюда. Итак, можно сказать, что представленный на рис. 4.6 алгоритм последовательно рассматривает все элементы списка. По

этой причине данный алгоритм называется алгоритмом последовательного поиска (sequential search). В силу своей простоты он часто применяется к коротким спискам либо, когда это необходимо, по каким-то иным соображениям. Однако в случае длинных списков этот метод оказывается менее эффективным, чем другие (в чем мы скоро убедимся).

Управление циклами. Неоднократное использование инструкции или последовательности инструкций представляет собой важную алгоритмическую концепцию. Одним из методов органи-

зации такого повторения является итеративная структура, известная как цикл (loop); здесь последовательность инструкций, называемая телом цикла, многократно выполняется под контролем некоторого управляющего процесса. Типичный пример цикла можно найти в алгоритме последовательного поиска, представленном на рис. 4.6. Здесь инструкция while используется в целях управления повторным выполнением единственной инструкции "выбрать следующий элемент списка как Проверяемое_значение". Общийсинтаксисинструкцииwhile имееттакойвид:

while (условие) do {тело цикла}

Эта инструкция представляет собой типичный образец циклической структуры, т.е. при ее выполнении циклически совершаются следующие действия:

проверить условие выполнить тело цикла проверить условие выполнить тело цикла

.

.

.

проверить условие

Эти действия будут продолжаться до тех пор, пока заданное условие будет выполняться.

Как правило, использование циклических структур придает алгоритму большую гибкость по сравнению с явным многократным написанием тела цикла. Рассмотрим такой пример:

Выполнить инструкцию "Добавить каплю серной кислоты" три раза.

Эта циклическая структура эквивалентна такой последовательности инструкций:

Добавить каплю серной кислоты. Добавить каплю серной кислоты. Добавить каплю серной кислоты.

Однако невозможно написать аналогичную последовательность, эквивалентную следующему циклу: while (уровень рН больше, чем 4) do {добавить каплю серной кислоты}

Суть в том, что мы не знаем заранее, сколько капель серной кислоты понадобится в каждом конкретном случае.

А теперь давайте подробно рассмотрим, как осуществляется управление циклом. Может показаться, что эта часть структуры цикла менее важна. Ведь именно в теле цикла непосредственно выполняются требуемые действия (например, добавляются капли кислоты). Поэтому управляющие действия можно рассматривать просто как надстройку, появившуюся только из-за того, что мы решили повторять выполнение тела цикла. Однако опыт показывает, что именно управление циклом чаще всего служит источником ошибок в циклических структурах и, следовательно, требует особого внимания.

Управление циклом состоит из трех операций: инициализации, проверки и модификации (рис. 4.7), причем все они обязательны для успешного управления циклом. Назначение операции проверки состоит в обеспечении своевременного окончания циклического процесса за счет отслеживания возникновения условия, указывающего, что цикл пора заканчивать. Это условие называют условием завершения цикла. Именно для выполнения операции проверки некоторое условие обязательно указывается при записи каждой инструкции while нашего

Инициализация: Установить начальное состояние, которое будет модифицироватьсядотехпор, поканебудетвыполненоусловиеокончания.

Проверка: Сравнить текущее состояние с условием завершения и прекратить повторение тела цикла, если состояние соответствует условию окончанию.

Модификация: Изменить состояние таким образом, чтобы приблизиться к ситуации, в которой будет выполнено условие окончания.

Рис. 4.7. Операции управления циклом

псевдокода. Однако условие, задаваемое в инструкции while, – это условие продолжения цикла, а условие завершения – это отрицание условия, заданного в инструкции while. Поэтому в инструкции while показанной на рис. 4.6, условие завершения выглядит следующимобразом:

(Искомое_Значение ≤ Проверяемое_Значение) или (больше нет не рассмотренных элементов)

Остальные две операции управления циклом гарантируют, что условие завершения обязательно возникнет. Операция инициализации устанавливает начальное состояние, а операция модификации изменяет его в направлении достижения условия завершения. Например, на рис. 4.6 операция инициализации выполняется инструкцией, предшествующей инструкции while. В этой операции первый элемент списка устанавливается в качестве текущего проверяемого. Операция модификации в этом случае реализуется в теле цикла, когда интересующая нас позиция (проверяемый элемент) перемещается к концу списка. Таким образом, выполнение операции инициализации и многократное выполнение операции модификации приводят к тому, что условие завершения обязательно будет достигнуто. (Или обнаружится проверяемый элемент, больший либо равный искомому, или будет достигнут конец списка.)

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

Число ← 1

while (Число ≠ 6) do {Число ← Число + 2}

В данном случае условием завершения является выражение Число ≠ 6. Однако переменная Число инициализируется значением 1, а затем увеличивается на 2 на каждом этапе модификации. Таким образом, при выполнении цикла переменной Число будут присваиваться значения 1, 3, 5, 7, 9, ... и ее значение никогда не будет равно 6. В результате выполнение данного цикла никогда не закончится.

Существуют два варианта широко распространенных циклических структур, которые отличаются только порядком выполнения операций управления циклом. Первая представлена инструкцией нашего псевдокода:

while (условие) do {действие}

Семантика этой циклической структуры представлена на рис. 4.8 в виде блок-схемы. На подобных схемах для представления отдельных этапов выполнения используются различные геометрические фигуры, а стрелки указывают порядок выполнения этих этапов. Различные фигуры отражают отдельные типы деятельности, выполняемой на соответствующем этапе. Ромб указывает на принятие решения, а прямоугольник представляет произвольную инструкцию или последовательность инструкций. Обратите внимание, что в данной циклической структуре проверка условия завершения производится до того, как выполняется тело цикла.

В противоположность этому, в структуре, представленной на рис. 4.9, указывается, что тело цикла должно выполняться до проверки условия завершения. В результате тело цикла всегда выполняется хотя бы один раз, в то время как в структуре типа while тело цикла может не выполниться ни разу (если условие завершения будет выполнено при первой же его проверке).

В нашем псевдокоде общий синтаксис цикла этого типа имеет следующий вид: repeat {действие} until (условие)

Рассмотрим конкретный пример:

repeat {взять монету из кармана} until (в кармане нет монет)

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

while (в кармане есть монета) do {взять монету из кармана}

Придерживаясь терминологии нашего псевдокода, будем называть эти структуры оператором цикла с условием продолжения и оператором цикла с условием завершения. Иногда оператор цикла while называют априорным циклом (pretest loop), или циклом с предусловием, поскольку условие завершения проверяется до выполнения тела цикла, а оператор цикла repeat называется апостериорным циклом (posttest loop), или циклом с постусловием, поскольку условие завершения проверяется после выполнения цикла.

Алгоритм сортировки методом вставки. В качестве дополнительного примера итеративной структуры рассмотрим задачу сортировки списка имен в алфавитном порядке. Прежде чем приступить к обсуждению, следует установить некоторые ограничения, которые необходимо будет учитывать. Попросту говоря, наша задача – отсортировать список "внутри его самого". Другими словами, мы хотим отсортировать список, просто переставляя его элементы, а не перемещая весь список в другое место. Это аналогично сортировке списка, элементы которого записаны на отдельных карточках, разложенных на переполненном рабочем столе. На столе достаточно места для всех карточек, однако запрещается отодвигать другие находящиеся на столе материалы, чтобы освободить дополнительное пространство. Подобное ограничение типично для компьютерных приложений, но не потому, что рабочее пространство в машине обязательно переполнено, как наш рабочий стол, а потому, что мы стремимся использовать доступный объем памяти самым эффективным образом. Попробуем сделать первый шаг в поисках решения задачи. Рассмотрим, как можно было бы отсортировать карточки с именами, расположенные на рабочем столе. Пусть исходный список имен выглядит следующим образом:

Fred

Alice

David

Bill

Carol

Один из подходов к сортировке этого списка заключается в следующем. Обратите внимание, что подсписок, состоящий из единственного верхнего имени Fred, уже отсортирован, а подсписок из двух верхних имен, Fred и Alice, – еще нет. Поэтому подымем карточку с именем Alice, поместим карточку с именем Fred вниз, туда, где раньше была карточка с именем Alice, а затем положим карточку с именем Alice в самое верхнее положение, как показано в первой строке на рис. 4.10. Теперь список будет иметь такой вид:

Alice

Fred

David

Bill

Carol