ТЕХНОЛОГИИ ПРОГРАММИРОВАНИЯ. Алгоритмизация как обязательный этап разработки программы.

Содержание:

Введение

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

Понятие алгоритма – одно из фундаментальных понятий, которое составляет самостоятельную дисциплину - «теорию алгоритмов». Также теорию алгоритмов можно рассматривать промежуточным звеном между двумя дисциплинами: математикой и информатикой, связанной с программированием.

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

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

Задачи работы:

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

Изучение базовых алгоритмических структур;

Изучение объектов алгоритмов.

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

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

I этап – постановка задачи. На данном этапе должна быть определена предметная область задачи, определены её цели, необходимый объем исходной информации, проведено описание всех исходных данных. Предложен общий подход к решению.

II этап – математическое описание задачи. Цель – создать математическую модель, которая может быть реализована на компьютере, выбрать оптимальный метод решения задачи.

Математическая модель - это описание объекта или процесса при помощи математических зависимостей, связывающих их количественные параметры.

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

На основе математической модели разрабатывается алгоритм решения. Обычно алгоритм разрабатывается на основе блок – схемы с четко определенной последовательностью действий.

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

V этап – ввод программы в вычислительную машину. На этом этапе программу необходимо набрать в среде программирования и сохранить на диске.

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

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

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

Понятие алгоритма

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

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

Алгоритмизация задачи - процесс разработки алгоритма решения задачи с помощью компьютера на основе ее условия и требований к конечному результату.

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

Алгоритм - понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение указанной цели или на решение поставленной задачи.[11]

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

Сам термин алгоритм происходит от имени узбекского ученого IХ в. Аль- Хорезми, который в своем труде «Арифметический трактат» изложил правила арифметических действий над числами в десятичной системе счисления. Эти правила и были названы алгоритмами. Следовательно, правила сложения, вычитания, деления, умножения чисел, правила преобразования алгебраических выражений, правила построения геометрических фигур, грамматические правила правописания слов и предложений - все это алгоритмы. Многие правила, инструкции, записанные в различных документах и представляющие собой подробные указания, которые могут быть использованы во всевозможных ситуациях, можно также отнести к алгоритмам.

Виды алгоритмов как логико-математических средств отражают также компоненты человеческой деятельности, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения и определения действий исполнителя подразделяются на [14]:

• механические, или детерминированные, жесткие алгоритмы (алгоритм работы машины, двигателя и т.п.);
• гибкие алгоритмы, например стохастические, т.е. вероятностные и эвристические.

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

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

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

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

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

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

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

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

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

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

1) последовательную декомпозицию задачи, выделение независимых этапов вычислительного процесса и разбивку каждого этапа на отдельные шаги;

2) формальную запись содержания каждого этапа или шага;

3) определение общего порядка выполнения этапов или шагов;

4) проверку правильности алгоритма.[3]

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

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

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

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

На втором этапе остается лишь выполнить кодирование (программирование), заменив формульно-словесные инструкции алгоритма операторами конкретного языка. Эта работа уже не связана с большим умственным напряжением. При простых задачах для ее выполнения достаточно знать общие правила оформления программ, правила описания данных, основные операторы (ввода, вывода, управления, обработки). [3]

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

Свойства алгоритмов

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

Алгоритмы обладают следующими свойствами [4]: понятностью, дискретностью, точностью, результативностью, массовостью.

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

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

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

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

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

Характеристики алгоритмов

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

Временные характеристики алгоритма определяют длительность решения или временную сложность [7].

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

Временной сложностью алгоритма называют зависимость времени счета, затрачиваемого на получение результатов, от объема исходных данных.

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

Для сложных задач эта характеристика имеет большое значение, т.к. её изменение значительнее влияет на время решения, чем изменение быстродействия компьютера. Например, при зависимости f(n) = 2ⁿ увеличение производительности в 10 раз увеличивает размерность задачи, решаемой за то же время, только на 15% [7].

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

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

Объем внутренней и внешней памяти необходимой для хранения данных и программ при использовании данного алгоритма определяется на основании расчётов или опытным путем. При недостатке машинной памяти для хранения информации используется сегментация программ.

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

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

Способы описания алгоритмов

Рассмотрим основные способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

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

Пример. Запишем алгоритм Эвклида нахождения наибольшего общего делителя двух натуральных чисел.

Алгоритм следующий:

1. задать два числа;
2. если числа равны, то взять любое из них в качестве результата и остановиться, в противном случае продолжить выполнение алгоритма;
3. определить набольшее из чисел;
4. заменить набольшее из чисел разностью большего и меньшего из чисел;
5. повторить алгоритм с шага 2.

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

1. а = 125; b = 75
2. 125 - 75 = 50; а = 50, b = 75
3. 75 - 50 = 25; а = 50, b = 25
4. 50 - 25 = 25; а = 25, b = 25
5. НОД = 25; 125 / 25 = 5, 75 / 25 = 3

Словесный способ не имеет широкого распространения, так как обладает следующими недостатками:

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

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

Пример.

Основные служебные слова

алг (алгоритм)	сим (символьный)	дано	для	да
арг (аргумент)	лит (литерный)	надо	от	нет
рез (результат)	лог (логический)	если	до	при
нач (начало)	таб(таблица)	то	знач	выбор
кон (конец)	нц (начало цикла)	иначе	и	ввод
цел (целый)	кц (конец цикла)	все	или	вывод
вещ (вещественный)	длин (длина)	пока	не	утв

Общий вид алгоритма:

алг название алгоритма (параметры) дано условия применимости алгоритма надо цель выполнения алгоритма нач описание промежуточных величин | последовательность команд (тело алгоритма) кон

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

Блок-схема - описание структуры алгоритма с помощью геометрических фигур с соединительными линиями-связями, показывающими порядок выполнения отдельных инструкций. Данный способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает читаемость алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур. Запись алгоритма должна выполняться в соответ­ствии с ГОСТ 19.701-90 «Схемы алгоритмов, программ данных и систем. Условные обозначения и правила выполнения».[2]

Пример.

Название символа	Обозначение и пример заполнения	Пояснение
Процесс	да нет	Вычислительное действие или последовательность действий
Решение		Проверка условий
Модификация		Начало цикла
Предопределенный процесс		Вычисления по подпрограмме, стандартной подпрограмме
Ввод-вывод		Ввод-вывод в общем виде
Пуск-останов		Начало, конец алгоритма, вход и выход в подпрограмму
Документ		Вывод результатов на печать

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

Программа - описание структуры алгоритма на языке алгоритмического программирования. С другой стороны, понятие «программа» нельзя трактовать только таким образом, программа на языке декларативного программирования представляет собой совокупность описанных знаний и не содержит явного алгоритма исполнения.[9]

Типы алгоритмов

Существует три основных типа алгоритмов: линейный, разветвляющийся и циклический.[5]

Линейный алгоритм предполагает однократное выполнение одной и той же последовательности шагов при любых наборах исходных данных.

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

IF <условие> THEN <оператор_1> ELSE <оператор_2>

<условие> - произвольное выражение логического типа;

<оператор_1>, <оператор_2> - любые операторы алгоритмического языка.

При выполнении условия будет выполняться <оператор_1>, в противном случае <оператор_2>. Часть оператора ELSE может быть опущена. В этом случае мы имеем краткую форму записи оператора:

IF <условие> THEN <оператор>

При выполнении условия будет выполняться <оператор>, в случае невыполнения условия выполняется первый оператор, следующий за оператором IF.

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

цикл - пока

условие В;

повторить

действие А;

все - цикл

выбор - по

если (=0)

действие А;

если (=1)

действие В;

если (=2)

действие С;

все - выбор

если α, то действие А;

иначе действие В;

все - если

действие А

действие В

А

В

α

А

В

цикл

действие А;

по

условие В;

все - цикл

д)

нет

да

B

A

=1

i

А

B

C

цикл - пока

условие В;

повторить

действие А₁

если

условие γ

то

выйти...

все - если

действие А₂;

все - пока

е)

к обработке

ошибки

да

да

B

A₁

да

γ

B

A₂

A

1. Основные управляющие структуры. а)последовательность; б)разветвление; в)выбор; г)цикл «пока»; д)цикл «до»; е)выход из цикла

Примеры записи основных алгоритмических структур на языке Pascal.

1. Линейный алгоритм

Найти сумму, разность и произведение двух чисел.

program lin;

var

a, b, s, r, p: real;

begin

writeln('Введите числа a, b ');

readln(a, b);

s := a + b;

r := a - b;

p := a * b;

writeln('Сумма ', s:6:2);

writeln('разность ', r:6:2);

writeln('произведение ', p:6:2);

readln;

end.

2. Разветвляющийся алгоритм

Вывод на экран последовательности вида

может быть организован следующей программой:

program vetv;

var

n, i: integer;

f: boolean;

begin

write('Введите натуральное число n = ');

readln (n);

if n mod 2=0 then

f := false

else

f := true;

write('s =');

for i := 1 to n - 2 do

if (not f) and (i mod 2 = 0) then

write(i,'*')

else

if f and (i mod 2 <>0) then

write(i,'*');

writeln(n)

end.

3. Циклический алгоритм

Вводится последовательность из N целых чисел. Найти сумму всех ее чисел.

program cikl;

var

n, x, sum, i: integer;

begin

write('ВВедите длину последовательности n = ');

readln (n);

sum := 0;

for i := 1 to n do

begin

write('Введите х = ');

readln (x);

sum := sum+x

end;

writeln('Сумма чисел sum = ', sum);

end.

Вспомогательные алгоритмы

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

Формальные параметры должны быть выбраны таким образом, чтобы ими был полностью исчерпан набор необходимых входных и выходных величин. Причем один и тот же параметр может оказаться как входным так и выходным одновременно. Пример: на вход алгоритма может быть подан массив для обработки, а на выходе он (массив) может предстать в измененном виде как выходной параметр (например, отсортированный).

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

Декомпозиция алгоритма

Под декомпозицией алгоритма понимают разделение его o6щeй алгоритмической схемы на вспомогательные алгоритмы (процедуры и функции) и главный алгоритм. [12]

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

Приведем пример декомпозиции для решения задачи сортировки массива в порядке возрастания значений его элементов.

Решение задачи декомпозиции состоит из трёх основных этапов: 1) ввода данных, 2) сортировки массива и 3) вывода отсортированного массива. Первый и третий этапы вследствие их простоты не нуждаются в декомпозиции, поэтому выполняются в главном алгоритме. Второй этап представляет достаточно сложный и самостоятельный фрагмент алгоритмической работы, поэтому его целесообразно выделить в отдельную процедуру, которой дадим имя Bubble.

Процедура сортировки требует перестановки значений двух простых переменных. Вспомогательный алгоритм, реализующий эту процедуру, показан на рис. 2. Алгоритм имеет имя Swap и два формальных параметра - переменные a, b. Тело алгоритма состоит из одного блока, где выполняется три оператора присваивания. Сначала оператором c := a значение ячейки a копируется во вспомогательную переменную c, затем оператором a := b из ячейки с адресом b производится копирование значения в ячейку с адресом a, последним оператором b := c из вспомогательной ячейки с адресом c значение копируется в переменную с адресом b. В результате такого кругового копирования содержимое ячеек a и b поменяется местами.

Swap(a, b)

c = a; a = b; b =c

Конец

1

2

3

1. Процедура Swap

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

Основной алгоритм сортировки массива приведен на рис. 3. Алгоритм имеет имя Bubble и содержит два формальных параметра: N - длина массива, Z - имя массива, который нужно отсортировать.

Сортировка производится при помощи двух вложенных друг в друга циклов. Внешний цикл образован блоками 2 - 7 и предназначен для многократного прохода по массиву. Внутренний цикл содержит блоки 3 - 6. Этот цикл нужен для однократного прохода по всем парам соседних элементов массива с целю перестановки несортированных пар элементов. Переменная L играет роль параметра, по которому можно определить производились ли перестановки при выполнении внутреннего цикла.

1

Bubble(N, Z)

L = 0

Конец

2

3

i = 1, N - 1

4

Z_i+1 > Z_i

Perm(Z_i+1, Z_i)

5

L = L + 1

6

да

нет

L = 0

да

нет

7

8

1. Процедура Bubble

Алгоритм работает следующим образом. Сначала в блоке 2 параметр L получает значение 0 (ноль). Далее выполняется внутренний цикл из блоков 3 - 6. В нем счетчик цикла i будет последовательно принимать значения 1, 2, 3, ..., N-1. При каждом таком значении счетчика в блоке 4 производится сравнение соседних элементов с номерами i и i + 1. В том случае, если пара не отсортирована, то в блоке 5, используя вспомогательный алгоритм Swap, эта пара будет отсортирована путем перестановки значений этих элементов. После каждой перестановки счетчик перестановок L будет увеличиваться на 1. После прохода по всем парам элементов по завершении внутреннего цикла выполнится проверка количества совершенных перестановок. Если перестановок не было (т.е. L = 0), то это означает, что массив отсортирован и работа процедуры сортировки завершена. Если же L отлично от 0, то управление предается на блок 2 и процесс сортировки продолжится по той же схеме. Внешний цикл будет выполняться до тех пор, пока при выполнении по внутреннего цикла не будет выполнено ни одной перестановки.

На рис. 4 показан главный управляющий алгоритм, который и решает поставленную задачу. Сначала в блоке 2 задается количество N элементов массива и вводятся значения всех N элементов массива A. Затем в блоке 3 происходит вызов алгоритма сортировки Bubble. В нем на место формального параметра N подставляется фактическое значение параметра N головного алгоритма, а на место формального массива Z подставляется фактический массив A. Теперь управление передается в алгоритм Bubble, который выполнит сортировку массива A. После сортировки в блоке 4 головного алгоритма отсортированный массив будет выведен. В блоке 5 алгоритм закончит свою работу.

Начало

N, A

Конец

1

2

5

Bubble(A, N)

3

A

4

1. Головной алгоритм

Реализация алгоритмов

После разработки алгоритма встает задача его реализации в виде программы, которую можно выполнить на вычислительной машине (компьютере). В ГОСТ 19781-90 дано следующее определение программы.

Программа - это данные, предназначенные для управления конкретными компонентами обработки информации в целях реализации определенного алгоритма.[1]

Для написания программы необходимо в первую очередь выбрать язык программирования (алгоритмический язык). В общем случае алгоритмический язык - это набор символов с заданными правилами образования из этих символов конструкций, с помощью которых описывается процесс выполнения алгоритма. В ГОСТ 19781-90 дано следующее определение алгоритмического языка.[1]

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

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

Выбор языка определяется:

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

Например, для программирования сложных (чаще всего системных) задач выбирают язык Ассемблер или С++, а для решения инженерных задач предпочтение отдают Pascal (Object Pascal), Fortran, C# или Basic.

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

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

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

2. Компоновка (редактор связей) - сборка объектного модуля программы, модулей ввода-вывода и компонентов стандартной библиотеки объектных модулей в один модуль, который называется выполняемым файлом или загрузочным модулем.

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

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

Ошибки в алгоритме - в этом случае необходимо вернутся к начальным этапам разработки алгоритма. Для выявления этих ошибок рекомендуется выполнить тестирование алгоритма. [13]

Схема этапов подготовки программы представлена на рис. 5.

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

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

В общем случае отсутствуют универсальные правила выполнения тестирования.

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

Исходный модуль

Объектный модуль

Исполняемая программа

Библиотека объектных модулей

Транслятор

Компоновщик

Этап 1

Этап 2

Этап 3

1. Этапы подготовки программы

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

Величины в алгоритмах

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

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

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

Типы данных: вещественные, целые, логические, текстовые, символьные и другие.

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

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

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

Используются простые и индексные переменные. Переменная с индексом - это элемент некоторой последовательности значений, которая называется массивом.

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

Массив - совокупность однотипных данных, связанных общим именем.

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

Первый компонент одномерного массива - это элемент с номером 1, второй - с номером 2 и т.д., запись в математике - X₁, X₂,... При программировании запись более формализована: X(1), X(2),... (в некоторых языках программирования допускается использование нулевых и отрицательных индексов).

Двумерный массив - это матрица из строк и столбцов. Первый индекс определяет номер строки, второй - номер столбца. Номер строки изменяется от 1 до N, где N - полное число строк, номер столбца от 1 до М, где М - полное число столбцов. При программировании элементы двумерного массива по имени Y будут записаны Y(1,1), Y(1,2), Y(1,3) и т.д. Индексы отделяются запятыми.

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

Основными характеристиками массива являются:

- имя массива;

- тип элементов;

- размерность, равная количеству измерений массива;

- значения верхней и нижней границы для каждого индекса;

- размер массива - количество компонентов. [4]

Типовые приемы алгоритмизации

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

• алгоритмы накопления (счетчик, вычисление суммы и произведения элементов массива);
• поиск максимума (минимума);
• сортировка.

Вычисление суммы и произведения

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

S = S + у,

где у - очередное слагаемое;

S - промежуточная сумма.

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

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

P = P⋅у,

где у - очередной сомножитель;

Р - промежуточное произведение.

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

Рассмотрим вычисление суммы и произведения на примере.

Задача. Задан массив по имени А, состоящий из 20 элементов А_i; i = 1, ..., 20. Составить алгоритм вычисления суммы и произведения элементов этого массива.

Решение. В соответствии со смыслом описываемых величин выбираем имя переменных: для суммы - S, произведения - P.

Алгоритм вычисления будет состоять из следующих шагов.

1. Ввод массива A_i; i = 1, ..., 20.

2. Задание начальных значений переменных S и P.

S = 0, P = 1.

3. Цикл. Задаются параметры цикла: начальное значение параметра цикла 1, конечное значение 20, шаг 1.

4. Вычисление текущих значений S и P.

S = S + A_i;

P = P × A_i.

5. Проверка окончания цикла. Если параметр цикла меньше конечного значения, то увеличиваем переменную цикла на 1 и переходим к шагу 4. Если переменная цикла больше конечного значения, то переходим к шагу 6.

6. Печать вычисленных значений S и P.

7. Конец.

Вычисление количества элементов

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

К = К + 1.

Начальное значение К = 0.

Задача. Задан массив А, состоящий из 20 элементов, A_i; i = 1, ..., 20. Составить алгоритм вычисления суммы и количества положительных элементов массива.

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

1. Ввод массива A_i; i = 1, ..., 20.

2. Задание начальных значений переменных

S = 0,

К = 0.

3. Цикл. Задаются начальное и конечное значение переменной цикла и шаг цикла.

4. Проверка очередного элемента A_i на знак. Если условие A_i > 0 выполняется, то переход к шагу 5, если нет - к шагу 6.

5. Накопление суммы

S = S + X,

и увеличение счетчика К на 1,

К = К + 1.

6. Проверка окончания цикла.

7. Печать значений S и К.

8. Конец.

Нахождение максимального и минимального элементов в заданной последовательности

Задача. Задан массив A_i; j = 1, ..., 30. Найти максимальный элемент этого массива.

Решение. Поиск максимального элемента массива выполняется в цикле путём последовательного сравнения значения текущего элемента массива с максимальным элементом из всех предыдущих. И, если значение текущего элемента больше максимального из предыдущих, то максимуму присваивается значение текущего элемента. В j-м цикле для выбора максимального элемента используется следующая формула:

После окончания цикла значение А_max будет максимальным из всёх рассмотренных значений А.

Для применения указанного способа необходимо перед началом цикла задать начальное значение А_max некоторое начальное значение. Например, это может быть значение первого элемента массива. Поиск в цикле начинается со второго элемента. При первом выполнении цикла (j = 2) А_max будет сравниваться с А₂. И если А₂ будет больше А_max, то меняем значение А_max, присваивая переменной А_max значение А₂. И продолжаем сравнение, теперь уже со следующим элементом.

Можно взять в качестве начального значения заведомо маленькое число. Тогда после выполнения первого цикла (j = 1) А_max будет равен А₁. Данный приём используется в циклах с простыми переменными.

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

1. Ввод исходного массива А; j = 1, ..., 30.

2. Задание начального значения А_max = А₁.

3. Цикл. Задаются параметры цикла: начальное значение переменной цикла 2, конечное значение 30, шаг цикла 1.

4. Сравнение очередного j-го элемента А_j и А_max. Проверяется условие А_j > А_max? Если условие выполняется, переход к шагу 5, если нет, то - к шагу 6.

5. Присвоение А_max = А_j.

6. Конец цикла.

7. Печать максимального элемента массива А_max.

8. Конец.

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

и алгоритм выбора аналогичен рассмотренному выше.

В качестве начальных значений А_min может быть взято значение первого элемента массива, и поиск в цикле начнётся со второго элемента. Или заведомо большое число, которое больше любого элемента в исходном массиве, и поиск в цикле начнётся с первого элемента.

Задача. Для массива А, заданного в предыдущей задаче, найти минимальный элемент А_min и его порядковый номер j_min.

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

2. Задание начального значения А_min = А₁, j_min = 1.

4. Сравнение очередного элемента А_j и А_min. Если А_j меньше А_min, то переход к шагу 5, если больше - к шагу 6.

5. Присвоение А_min = А_j, j_min = j.

6. Конец цикла.

7. Печать номера минимального элемента j_min и значения минимального элемента А_min.

Так как цикл начнется со второго элемента массива, то первый элемент А₁ может оказаться минимальным. Поэтому в п. 2 задаётся начальное значение не только А_min = А₁, но и j_min = 1.

Структуры с вложенными циклами

Алгоритмы решения многих задач требуют нескольких циклов. Это:

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

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

Например, вычисление суммы всех элементов матрицы. Здесь начальное значение суммы элементов нужно задать перед внешним циклом, а накапливать её во внутреннем цикле.

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

Задача. Задана матрица Х(N×М). Определить количество положительных элементов в каждой строке матрицы.

Решение. Матрица Х имеет размер N×М, т.е. в ней N строк и М столбцов. Вводить и печатать матрицу будем в общепринятом виде - по строкам. Вывод матрицы на печать необходим для получения результата в удобном для чтения виде.

Алгоритм.

1. Ввод матрицы Х(N, М), где i = 1, ..., N; j = 1, ..., М.

2. Печать исходной матрицы Х(N, М), где i = 1, N; j = 1, М.

3. Внешний цикл по строкам. Переменная цикла i изменяется от 1 до N, шаг 1.

4. Задание начального значения количества положительных элементов для каждой строки матрицы К = 0.

5. Внутренний цикл по столбцам. Параметр цикла j изменяется о 1 до М, шаг 1.

6. Проверка очередного элемента Х_ij на знак. Если Х_ij больше или равно нулю, то переход к шагу 7, иначе - к шагу 8.

7. Увеличение счетчика количества положительных элементов К на 1,

К = К + 1.

8. Конец внутреннего цикла.

9. Печать номера строки i и количества положительных элементов К.

10. Конец внешнего цикла.

11. Конец.

Заключение

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

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

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

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

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

Список использованной литературы

1. ГОСТ 19.781-90. Обеспечение систем обработки информации программное. Термины и определения. –М.: Стандартинформ, 2010. –172 с.
2. ГОСТ 19.701-90. Схемы алгоритмов, программ данных и систем. Условные обозначения и правила выполнения. –М.: Стандартинформ, 2010. –172 с.
3. Белов М. П. Основы алгоритмизации в информационных системах: Учеб. пособие. -СПб.: СЗТУ, 2003. - 85 с.
4. Давыдов И. С. Информатика. -М.: Проспект Науки, 2009. -480 с.
5. Голицына О.П., Попов И.И. Основы алгоритмизации и программирования. Учебное пособие. -М.: Инфра-М, 2015. -432 с.
6. Ефимова О.В., Морозов В.В., Угринович Н.Д. Курс компьютерной технологии с основами информатики. –М.: АБФ, ACT, 2015. –482 с.
7. Затонский А.В., Бильфельд Н.В. Программирование и основы алгоритмизации. -М.: ДРОФА, 2014. -176 с.
8. Информатика: учебник/ Б.В. Соболь. –Ростов н/Д: Феникс, 2016. –446 с.
9. Канцедал С.А. Алгоритмизация и программирование. -М.: Инфра-М, 2016. -352 с.
10. Колмыкова Е. А., Кумскова И. А. Информатика. –М.: Академия, 2010. - 416 с.
11. Макарова Н. В., Волков В. Б. Информатика. –СПб.: Питер, 2011. -576 с.
12. Незнанов А.А. Программирование и алгоритмизация. -М.: Academia, 2010. -304 с.
13. Потопахин В.В. Искусство алгоритмизации. -М.: ДМК Пресс, 2014. -320 с.
14. Степанов А.Н. Информатика: учеб. пособие / А.Н. Степанов. - СПб.: Питер, 2008. –765 с.