Представление алгоритма

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

Примитивы

Для представления алгоритма требуется язык представления. Если говорить о человеке, то это может быть естественный язык (английский, русский или японский) или язык картинок (рис. 4.1), описывающий, например, алгоритм создания птицы из квадратного листа бумаги. Однако часто такие естественные средства общения приводят к неправильному пониманию, потому что используемые термины имеют несколько значений. Предложение «Посещение внуков может действовать на нервы» может означать, что внуки, когда они приходят, являются источником проблем или что поход к ним в гости является проблемой. Неправильное понимание также возникает из-за недостаточной степени детализации алгоритма. Немногие читатели смогут сложить птицу, следуя указаниям, данным на рис. 4.1 Однако для человека, занимающегося оригами, сделать это не составит труда. Таким образом, трудности в передаче алгоритма возникают тогда, когда используемое для этого языковое представление не является однозначным или когда данной информации недостаточно.

ПРЕДСТАВЛЕНИЕ АЛГОРИТМА В ПРОЦЕССЕ ЕГО ПОСТРОЕНИЯ

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

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

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

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

КАК НАЗЫВАТЬ ЭЛЕМЕНТЫ ПРОГРАММЫ

В естественном языке названия элементов часто состоят из нескольких слов, например «стоимость производства прибора» или «предполагаемое время прибытия». Однако когда мы записываем алгоритм в виде программы, такие имена могут осложнить описание алгоритма. Опыт показывает, что лучше присваивать элементу имя, состоящее из неразрывного текста. В течение последних лет использовались разные способы сжатия нескольких слов в одну лексическую единицу для получения имен элементов программы. Один из них состоит в том, чтобы использовать символ подчеркивания для соединения слов, например предполагаемое _время прибытия. При другом способе используются заглавные буквы, чтобы читателю было легче расшифровать имя. Например, можно начинать каждое слово с заглавной буквы ПредполагаемоеВремяПрибытия. Такую технику часто называют паскалевским стилем (Pascal casing), поскольку она была распространена среди тех, кто использовал язык программирования Pascal. Разновидностью формата «паскалевский стиль» является формат «верблюжий стиль» (camel casing), который отличается от паскалевского стиля только тем, что первая буква имени является строчной: ПредполагаемоеВремяПрибытия. Какой формат использовать — это дело вкуса. Каждый примитив состоит из двух компонентов: синтаксиса и семантики. Синтаксис — это символическое представление примитива, а семантика — его значение. Синтаксис слова «воздух» включает в себя шесть символов, а семантика — газообразное вещество, которое окружает планету. Некоторые примитивы, которые используются в оригами, изображены на рис. 4.2.

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

Псевдокод

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

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

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

имя <— выражение

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

RemainingFunds <— CheckingBalance + SavingsBalance

присваивает результат сложения значений CheckingBalance и SavingsBalance имени RemainingFunds.

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

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

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

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

Каждое из этих утверждений соответствует структуре

if (условие) then (действие) else (действие).

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

В то же время утверждение

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

может иметь более наглядный вид:

if [год является високосным)

then (ежедневная сумма <- сумма, разделенная на 366) else (ежедневная сумма <— сумма, разделенная на 365)

Мы также включаем в псевдокод более короткую синтаксическую структуру

if (условие) then (действие))

которую можно применять в случаях, когда нет действия, выполняемого в противном случае. Используя это представление, утверждение «В случае уменьшения объема продаж снизить цену на 5 %» можно записать как

if (уменьшился объем продаж) then (снизить цену на 5 %)

Следующая распространенная семантическая структура — исполнение некоторых действий до тех пор, пока некоторое условие истинно. Например: «До тех пор, пока есть билеты, продавать билеты». Для таких случаев мы включаем в псевдокод структуру

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

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

while (есть билеты) do (продавать билет).

Расположение записи программы влияет на ее разборчивость. Например, утверждение

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

легче понять, чем запись

if (предмет облагается налогом^пеп (if (цена > предельная цена) then (выплатить х) else (выплатить у)) else (выплатить z)

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

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

procedure имя

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

procedure Приветствие

Счетчик «— 3:

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

(вывести на печать сообщение "Привет"

и Счетчик <— Счетчик - 1)

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

if (...) then (выполнить процедуру ПроцессЗаимствования) else (выполнить процедуру ОтклонитьПросьбу).

Процедура ПроцессЗаимствования будет выполнена в том случае, если проверяемое условие истинно, а процедура ОтклонитьПросьбу будет выполнена, если условие ложно.

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

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

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

Если дальше в представлении упоминается сортируемый список, то для него используется имя Список. А когда мы вызываем процедуру Сортировка, мы задаем, какой именно список нужно отсортировать. Следовательно, в зависимости от наших потребностей мы напишем «применить процедуру Сортировка к списку сотрудников организации» или «применить процедуру Сортировка к списку гостей».

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

while (...) do (.

) end while

или

while (...) do (if (...)

then (.

) end if) end while

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

Создание алгоритма

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