Ильин А.А., Евсюков В.В., Ильин Р.А. Информатика

Подождите немного. Документ загружается.

–

201

–

Есть еще ряд символов, которые мы узнаем в дальнейшем, но для первого

знакомства с понятием «алгоритм» нам достаточно и этих.

4.3. ТЕХНОЛОГИЯ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

Как в любом виде деятельности в алгоритмизации и программировании

имеется своя технология: это знания, правила, навыки и инструменты,

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

поставлен на

последнее место вполне сознательно. Среди начинающих

программистов распространено мнение, что “фирменный” инструмент, в

данном случае это трансляторы, оболочки, отладчики, сам по себе определяет

качество изделия. Это не так – скорее даже наоборот. Оболочка, автоматически

исправляющая мелкие огрехи программиста, приучает его к небрежности в

работе, не дает навыка самостоятельной отладки и поиска

ошибок. В

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

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

остается беспомощным. Для многих такое событие становится последней

самостоятельной попыткой алгоритмизации и программирования. Как

аналогия – для езды на мотоцикле рекомендуется вначале выработать навык

поддержания равновесия на велосипеде. На мотоцикле его поддерживать

легче,

но и цена ошибки несколько иная.

Итак, важно придерживаться какой-нибудь технологии алгоритмизации и

программирования. Но само по себе соблюдение ряда правил не дает гарантию

качества результата. Это объясняется спецификой алгоритмизации и

программирования. Во-первых, это не наука, где знание какой-либо формулы

позволяет однозначно решить задачу, подставив в

нее исходные данные и

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

на бумаге, сколько в голове. Технология алгоритмизации и

программирования – это скорее способ организации процесса обдумывания

программы, нежели ее записи.

И, конечно же, нельзя не затронуть вопрос о взаимоотношении

алгоритмизации и программирования и искусства, тем более, что "искусство

программирования" – термин, особенно широко использующийся в названиях

книг. Самое главное, в чем алгоритмизация и программирование

противоположно искусству – способ мышления в процессе работы: если в

искусстве оно образное, основанное на интуиции, ассоциациях, то в

алгоритмизации и программировании – формально-логическое. Но с другой

стороны, в процессе создания алгоритма программист сначала строит у

себя в

–

202

–

голове образную модель, которая соответствует уже работающей, но еще не

написанной программе, а затем пытается ее формализовать. То есть он сначала

должен мысленно увидеть, как в ней перемещаются элементы массивов,

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

программисту необходимо образное мышление, интуиция, и, если хотите,

вдохновение. С

такой точки зрения алгоритмизация и программирование

действительно является искусством.

Если пишущий программу мыслит, то он уже придерживается какой-то

технологии алгоритмизации и программирования, даже не подозревая об этом.

Самый простой метод заключается в написании программы сразу от начала до

конца, без использования каких-либо общих принципов, то есть "как бог

на

душу положит".

Основная последовательность действий, составляющих суть

программирования: по формулировке задачи (описанию действий или

желаемому результату) программист в голове строит ее образную модель.

Затем в процессе ее "оживления" пытается перевести законы ее

функционирования на формальный язык. Все в этом процессе может быть

идеальным за исключением того, что человеческий разум не

в состоянии

одномоментно охватить более или менее сложный образ. Он разбивает его на

более простые, с которыми в состоянии справиться. Любая технология

алгоритмизации и программирования, собственно, и заключается в том, чтобы

сделать этот процесс более регулярным и управляемым.

Составные части образной модели могут иметь неформальную или

полуформальную словесную формулировку действий,

производимых этой

частью. Например, “найти минимальный элемент в массиве А и запомнить его

индекс в n”. Технология программирования задает правила, при помощи

которых можно переходить от более абстрактной, к более конкретной

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

Нисходящее проектирование программ

Нисходящее проектирование программ состоит в движении "от общего

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

записи алгоритма это соответствует движению от внешней (объемлющей)

конструкции к внутренней (вложенной). Конкретно в структурном

программировании это выражается в том, что любая словесная формулировка

действий (алгоритма) может быть заменена на одну из трех формальных

конструкций языка программирования:

• простая последовательности действий;

• конструкция выбора или оператор if;

• конструкция повторения или оператор цикла.

–

203

–

Выбранная формальная конструкция представляет собой часть процесса

перевода словесного описания алгоритма на формальный язык. Естественно,

что эта конструкция не определяет полностью всего содержания алгоритма.

Поэтому составными ее частями остаются словесные формулировки более

конкретных (вложенных) действий.

Основной принцип: конструкции языка программирования замещают

словесную формулировку алгоритма "сверху-вниз", действие общего вида

превращается в

формальную конструкцию, содержащую частные действия, но

тоже в неформальной словесной формулировке.

Теперь перечислим по отдельности основные принципы нисходящего

проектирования:

• первоначально программа формулируется в виде некоторого

неформального действия на естественном языке, и оформляется

отдельной функцией;

• на очередном шаге проектирования словесная формулировка некоторого

действия может быть заменена на одну из

трех конструкций: простую

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

• очередной шаг детализации не меняет структуру программы, полученную

на предыдущих шагах (то есть возвраты в последовательности шагов

допускаются только как исключение);

• если в процессе проектирования получаются идентичные действия в

различных ветвях, то это означает необходимость оформления этого

действия отдельной функцией;

•

необходимые структуры данных проектируются одновременно с

детализацией программы.

В результате проектирования получается программа, в которой

принципиально отсутствует оператор безусловного перехода (GOTO), поэтому

структурное программирование иначе называется как

"ПРОГРАММИРОВАНИЕ БЕЗ GOTO".

Нисходящее проектирование по своей природе является пошаговым, ибо

предполагает каждый раз замену одной словесной формулировки на

единственную конструкцию языка. Но в процессе

разработки программы могут

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

в более подробную. Пошаговое проектирование выделено отдельно, чтобы

подчеркнуть необходимость предотвратить соблазн детализации программы

сразу от начала до конца и развивать умение выделять и сосредотачивать

внимание на главных, а не второстепенных деталях алгоритма.

Допустимые случаи использования оператора GOTO

Нисходящее пошаговое проектирование исключает использование

оператора GOTO, более того, запрещает его применение как нарушающего

–

204

–

структуру программы. Но нет правил без исключений. Чрезвычайными

обстоятельствами, вынуждающими прибегнуть к помощи оператора GOTO,

являются глобальные нарушения логики выполнения программы, например

грубые неисправимые ошибки во входных данных. В таких случаях делается

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

к повторению некоторой ее части. В других обстоятельствах его использование

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

программы – наличии неявных условных или циклических конструкций.

Одновременное проектирование программ и структур данных

При нисходящей пошаговой детализации программы необходимые для

работы структуры данных и переменные появляются по мере перехода от

неформальных определений к конструкциям языка, то есть процессы

детализации алгоритма и данных идут параллельно.

Однако это касается

прежде всего отдельных локальных переменных и внутренних параметров.

Предмет (данные) всегда первичен по отношению к выполняемым с ним

действиям (алгоритм). Способ организации данных в программе более

существенно влияет на ее структуру алгоритма, чем что-либо другое, и процесс

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

алгоритма их обработки

Более подробно проблемы технологии программирования (структурное

программирование, модульное программирование, объектно-ориентированное

программирование) рассмотрены в следующем разделе.

4.4. ПРОВЕРКА ПРАВИЛЬНОСТИ ПОСТРОЕНИЯ АЛГОРИТМА

В правильности функционирования алгоритма на достаточно мощном

множестве исходных данных возможно убедиться лишь с помощью средств

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

возможность тестирования разрабатываемых алгоритмов:

1) интегрированные среды

разработки программного обеспечения,

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

структурного и объектно-ориентированного программирования;

2) специализированные системы разработки и тестирования алгоритмов.

Для облегчения создания и анализа алгоритма в таких системах

предусмотрены:

• Наглядное выделение и анализ корректности фрагментов, имеющих

ветвящуюся структуру.

• Аналогичные возможности для фрагментов, имеющих циклическую

структуру.

• Возможность

динамической трассировки алгоритма, которая позволяет

наглядно следить за последовательностью выполнения блоков и модулей

–

205

–

(функций, процедур). Данный режим «оживляет» алгоритм и полезен для

разрушения ошибочного представления о нем как абстрактном понятии.

Интегрированные среды разработки программного обеспечения

Проверку правильности построения алгоритма на основе

интегрированных сред разработки программного обеспечения целесообразно

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

программирования. Интегрированные среды разработки программного

обеспечения включают в

свой состав встроенные отладчики, позволяющие

останавливать вычислительный процесс в заданной точке, пошагово выполнять

фрагменты алгоритма либо все задание, просматривать значения переменных

(их изменение) во время реализации шагов алгоритма. На рис. 4.1 представлено

окно меню встроенного отладчика интерпретатора QBasic, разработанного

Micrsoft Corporation для операционной системы MS DOS.

Рис. 4.1. Окно меню встроенного отладчика интерпретатора QBasic

Нажимая клавишу F8, можно пошагово (пооператорно) выполнить

программу с заходом в подпрограммы-фукнции и подпрограммы-процедуры.

Нажимая клавишу F10, можно пошагово (пооператорно) выполнить

программу без захода в подпрограммы-фукнции и подпрограммы-процедуры.

Клавиша F9 используется для создания контрольной точки в операторе,

на котором расположен курсор клавиатуры. При

выполнении программы, в

случае попадания вычислительного процесса в контрольную точку, будет

происходить останов выполнения программы перед контрольной точкой.

К сожалению, встроенный отладчик интегрированной среды QBasic не

позволяет отслеживать изменения значений переменных алгоритма во время

выполнения вычислительного процесса. Для реализации этой возможности

–

206

–

программисту необходимо вставлять в программу лишние операторы (print) для

вывода значений интересующих его переменных на экран (после отладки

алгоритма эти лишние операторы обычно удаляются или переводятся в

комментарии). От указанного недостатка свободна интегрированная среда

интерпретатора Visual Basic, разработанного Micrsoft Corporation для

операционной системы MS Windows, окно меню встроенного отладчика

которого представлено на рис. 4.2.

Рис. 4.2. Окно меню встроенного отладчика интерпретатора Visual Basic

Одновременно нажимая Shift + F9 (Q

uick Watch…) после выполнения

очередного шага алгоритма, в специальном окне можно просмотреть значения

всех переменных на текущий момент выполнения алгоритма. Если Вас

интересует значение какой-то одной переменный после выполнения очередного

шага алгоритма, достаточно навести курсор манипулятора «мышь» на

идентификатор этой переменной и в появившемся желтом окне посмотреть

значение этой переменной (см.

рис. 4.3.)

–

207

–

Рис. 4.3. Пример просмотра значений отдельных переменных

Cпециализированные системы разработки и тестирования

алгоритмов

Если необходимо разработать новый алгоритм, который за тем будет

реализован на нескольких языках программирования, то в этом случае

целесообразно воспользоваться специализированными системами разработки и

тестирования алгоритмов. В этих системах запись алгоритма осуществляется

специальными символами с использованием определенного синтаксиса

Такие системы не только облегчают построение схемы алгоритма, но и

обеспечивает его непосредственное выполнение и отображение полученных

результатов в символьной и графической форме. С помощью таких систем

обеспечивается проверка правильности алгоритма до составления программы

на том или ином языке, а не после. Системы позволяют создавать весьма

сложные алгоритмы, которые включают

ветвящиеся, циклические, а также

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

всеми основными навыками структурно-ориентированного программирования

(которое отнюдь не теряет своей актуальности в связи с появлением объектно-

ориентированного подхода).

–

208

–

4.5. АЛГОРИТМЫ ЛИНЕЙНОЙ СТРУКТУРЫ И СТРУКТУРЫ ВЫБОРА,

ИХ СХЕМНОЕ ОПИСАНИЕ

Схема линейной структуры

Алгоритм линейной структуры – алгоритм, символы которого

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

выполнены предписываемые ими действия. Еще он называется естественным

порядком выполнения.

Пример: вычислить

cos

bexa

−

= . Схема алгоритма представлена на

рис. 4.4.

НАЧАЛО

Ввод a, b, x

Y := a

⋅

cos(x)

⋅

(

)

xxC

−=

cos:

−

Вывод D

КОНЕЦ

Рис. 4.4. Пример схемы алгоритма линейной структуры

4.6. АЛГОРИТМЫ РАЗВЕТВЛЕННОЙ СТРУКТУРЫ

Алгоритмы разветвленной структуры – алгоритмы, в которых

предусмотрено разветвление выполняемой последовательности действий в

зависимости от результата проверки какого-либо условия. Рассмотрим пример

–

209

–

схемы алгоритма решения квадратного уравнения в поле вещественных чисел

(см. рис. 4.5).

Пример – алгоритм решения квадратного уравнения. В зависимости от

введенных параметров меняется вычисленное значение дискриминанта, после

чего. Если это значение отрицательное, то действительных корней нет

(выдается сообщение об этом), иначе – вычисляются значения действительных

корней. Возможен также вариант алгоритма, при котором

различаются случаи

нулевого дискриминанта (вычисляется один корень) и ненулевого (вычисляется

два корня). В общем случае разветвление может быть на любое число

параллельных последовательностей. Возможны два варианта: Первый – все эти

ветви опять сходятся вместе (как изображено на схеме), второй – некоторые из

них приводят к окончанию работы алгоритма.

4.7. АЛГОРИТМЫ ЦИКЛИЧЕСКОЙ СТРУКТУРЫ. АЛГОРИТМЫ

ПРОСТОЙ ЦИКЛИЧЕСКОЙ СТРУКТУРЫ. АЛГОРИТМЫ СТРУКТУРЫ

ВЛОЖЕННЫХ ПОВТОРЕНИЙ

Алгоритм циклической структуры

– это алгоритм, в котором

предусмотрено неоднократное выполнение одной и той же последовательности

действий. Эту последовательность называют циклом. Циклический алгоритм

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

Для организации цикла необходимо предусмотреть задание начального

значения параметра цикла – переменной, которая будет изменяться при

повторениях цикла; изменение значения этой переменной перед каждым новым

повторением цикла;

проверку условия окончания повторений по значению

параметра и переход к началу цикла, если повторения не закончены.

–

210

–

Ввод

a, b, c

Конец

D := b

- 4ac

Начало

Вычисление

Вывод

≤

Вывод

“нет

действиельных

корней”

Рис. 4.5. Пример схемы алгоритма разветвленной структуры

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

ряд Тейлора:

()

!12

1...

!5!3!1

)sin(

−

−++−=

−

xxxx

Вычисление заканчивается, когда последний член ряда по модулю не

превышает заданной точности вычислений

Таким образом, алгоритм в цикле вычисляет очередное слагаемое. После

его прибавления проверяется величина этого слагаемого по модулю. Если оно

больше

, то повторяем цикл еще раз, иначе – цикл считаем завершенным.

Схема алгоритма простой циклической структуры вычисления синуса

через разложение в ряд Тейлора представлена на рис. 4.6.