Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования.pdf

Введение

Само слово «алгоритм» возникло из названия латинского перевода книги арабского математика IX века Аль-Хорезми «Algoritmi de numero Indoru», что можно перевести как «Трактат Аль-Хорезми об арифметическом искусстве индусов».

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

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

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

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

Для осуществления данной цели, необходимо было решить следующие задачи:

1. Рассмотреть, что такое циклическая структура, цикл с постусловием и предусловием;

2. Изучить линейную структуру;

3. Описать разветвляющийся алгоритм, его полное и неполное ветвление.

Основной метод исследования, применяемый в написании данной курсового проекта, является:

1. Метод индукции и дедукции;

2. Метод анализа и синтеза;

3. Метод восхождения от простого к сложному;

4. Метод научной абстракции;

5. Метод качественного и количественного анализа.

линейная структура программа алгоритм приложение

1. Основные алгоритмические конструкции

1.1 Циклическая структура

Повторяющееся выполнение действий (групп действий), зависящее от выполнения условия, называется циклом.

Любой цикл состоит из трех частей: начала, проверки и тела цикла.

Начало – всегда первая часть цикла. Главная его функция – подготовить цикл.

Проверка определяет момент выхода из цикла.

Базовая структура "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов представлены в таблице:

|Язык QBasic |Язык блок-схем |

|Цикл типа пока. |

|Do Until условие |[pic] |

|тело цикла (последовательность действий) | |

|Loop | |

|Do While условие |[pic] |

|тело цикла (последовательность действий) | |

|Loop | |

|Цикл типа для. |

|For i=i1 to i2 |[pic] |

|тело цикла (последовательность действий) | |

|Next i | |

Пример алгоритма цикл на алгоритмическом языке QBasic:

FOR I=1 TO 15

PRINT I

NEXT I

FOR I=7 TO –6 STEP –3

PRINT I

NEXT I

I=0

PRINT «Значение I в начале равно»; I

DO WHILE I<10

I=I+1

LOOP

PRINT “Значение I в конце цикла равно”; I

Циклическая блок-схема приведена на рисунке 1.

Рис.1 Блок-схема циклической структуры

Алгоритмическая конструкция цикла.

Цикл - управляющая структура, организующая многократное выполнение указанного действия.

Цикл "пока":

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

Цикл "до":

Исполнение цикла начинается с выполнения действия. Таким образом тело цикла будет реализовано хотя бы один раз. После этого происходит проверка условия. Поэтому цикл "до" называют циклом с постусловием. Если условие не выполняется, то происходит возврат к выполнению действий. Если условие истинно, то осуществляется выход из цикла. Таким образом условие цикла "до" - это условие выхода. Для предотвращения зацикливания необходимо предусмотреть действия, приводящие к истинности условия. Цикл с параметром, или цикл со счетчиком, или арифметический цикл - это цикл с заранее известным числом повторов.

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

Xo - начальное значение параметра

h - шаг

Xn - последнее значение параметра

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

1. Параметр цикла, его начальное и конечное значения и шаг должны быть одного типа
2. Запрещено изменять в теле цикла значения начальное, текущее и конечное для параметра
3. Запрещено входить в цикл минуя блок модификации
4. Если начальное значение больше конечного, то шаг - число отрицательное
5. После выхода из цикла значение переменной параметра неопределенно и не может использоваться в дальнейших вычислениях
6. Из цикла можно выйти не закончив его, тогда переменная параметр сохраняет свое последнее значение

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

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

Упорядочение элементов в массиве происходит по их индексам.

Индекс - порядковый номер элемента.

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

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

Массивы делятся на одномерные (линейные) и двумерные.

Прообразом в математике для одномерного массива является вектор. Для двумерного - матрица.

Пример: вычислить n! Пример: вычислить aⁿ

Пример: ввести элементы массива:

а)одномерного, размерности 10; б)двумерного, 5x5

Условные конструкции.

1) неполная форма с одним оператором

2) полная форма с одним оператором

3) неполная форма с несколькими операторами

4) полная форма с несколькими операторами

1) IF условие THEN оператор;

2) IF условие THEN оператор1 ELSE оператор2;

3) IF условие THEN BEGIN

оператор1;

оператор2;

…

операторN;

END;

4) IF условие THEN BEGIN

оператор1;

оператор2;

…

операторN;

END ELSE

BEGIN

оператор1;

оператор2;

…

операторN;

END;

Пример: ввести оценку студента в баллах и сообщить ее название.

Begin

Read(b)

If b=5 then Write('отлично') else

If b=4 then Write('хорошо') else

If b=3 then Write('удовл.') else

If b=2 then Write('неудовл.') else

Write('это не оценка');

End.

Конструкция выбор.

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

Оператор выбора является структурированным и использует в своей записи операторы case, of, else, end и операторные скобки по необходимости.

В самом общем виде оператор выбора можно записать так:

Case порядковая переменная of

значение1: begin оператор1; оператор2; …; операторN; end;

значение2: begin оператор1; оператор2; …; операторN; end;

…

значениеM: begin оператор1; оператор2; …; операторN; end;

else begin оператор1; оператор2; …; операторN; end;

end;

Пример: ввести оценку студента в баллах и сообщить ее название.

Begin

Read(b)

Case b of

5: Write('отлично');

4: Write('хорошо');

3: Write('удовл.');

2: Write('неудовл.');

else Write('это не оценка');

end;

End.

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

Пример: напечатать количество дней во введенном месяце:

Begin

Read(m);

Case m of

янв, мар, май, июл, авг, окт, дек: Write('31');

апр, июн, сен, ноя: Write('30');

фев: Write('28');

else Write ('это не месяц');

end;

End.

Циклические конструкции.

1. Цикл с предусловием.

Для реализации циклов с предусловием используется составной оператор, включающий оператор while, do, операторные скобки.

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

while <условие> do <действие>;

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

while <условие> do

begin

<оператор 1>;

<оператор 2>;

...

<оператор n>;

end;

2. Цикл с постусловием.

Для реализации цикла используется составной оператор, состоящий из операторов repeat и until.

В общем виде цикл записывается так:

Repeat

<действие>;

until <условие>;

Пример: задано целое число. Вывести на печать все цифры введенного числа.

1 способ:

var a,b:longint;

Begin

read(a);

repeat

b:=a mod 10;

writeln(b); a:=a div 10;

until a=0;

End.

2 способ:

var a,b:longint;

Begin

read(a);

while a<>0 do

begin

b:=a mod 10;

write(b:3);

a:=a div 10;

end;

End.

2. Цикл с параметром.

Для реализации в языке Pascal используется составной оператор, состоящий из операторов for, to, downto, do и при необходимости из операторных скобок. Переменная параметр обязательно объявляется в декларационной части программы и может принадлежать одному из порядковых типов. Если при изменении переменной параметра необходимо использовать переход к следующему значению, то используется оператор to; если переход необходимо осуществить к предыдущему значению, то используется оператор downto. Тогда в общем виде цикл записывается так:

for I:=I₀ to I_n do

begin

<оператор 1>;

<оператор 2>;

...

<оператор n>;

end;

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

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

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

Рис.2 Блок-схема линейной структуры.

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