Файл: Алгоритмизация как обязательный этап разработки программы.pdf

Временная сложность позволяет определить наибольший размер задачи, которую можно решить с помощью данного алгоритма на компьютере. Каждый алгоритм можно характеризовать функцией 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.

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

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