![](/stc/img/evkova.png)
Основные структуры алгоритмов: сравнительный анализ и примеры их использования
Содержание:
Введение
Само слово «алгоритм» возникло из названия латинского перевода книги арабского математика 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 - последнее значение параметра
Для создания циклов с параметром необходимо использовать правила:
- Параметр цикла, его начальное и конечное значения и шаг должны быть одного типа
- Запрещено изменять в теле цикла значения начальное, текущее и конечное для параметра
- Запрещено входить в цикл минуя блок модификации
- Если начальное значение больше конечного, то шаг - число отрицательное
- После выхода из цикла значение переменной параметра неопределенно и не может использоваться в дальнейших вычислениях
- Из цикла можно выйти не закончив его, тогда переменная параметр сохраняет свое последнее значение
Использование циклов с параметром для обработки массивов.
Массив - упорядоченная структура, предназначенная для хранения однотипных данных.
Упорядочение элементов в массиве происходит по их индексам.
Индекс - порядковый номер элемента.
Массив задается именем (заглавные латинские буквы), типом данных и размерностью.
Размерность - максимально возможное количество элементов в массиве. В один момент времени можно обратиться только к одному элементу массива. Для этого указывается имя массива и в скобках индекс элемента.
Массивы делятся на одномерные (линейные) и двумерные.
Прообразом в математике для одномерного массива является вектор. Для двумерного - матрица.
Пример: вычислить n! Пример: вычислить an
Пример: ввести элементы массива:
а)одномерного, размерности 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:=I0 to In do
begin
<оператор 1>;
<оператор 2>;
...
<оператор n>;
end;
1.2 Линейный алгоритм
В алгоритмическом языке линейным является алгоритм, состоящий из команд, выполняющихся одна за другой. Они в записи алгоритма располагаются в том порядке, в каком должны быть выполнены предписываемые ими действия.
Такой порядок выполнения называется естественным. Последовательность команд образует составную команду «цепочка», которая в записи блок-схемой имеет вид, приведенный на рисунке 2.
Рис.2 Блок-схема линейной структуры.
В математике к линейным алгоритмам относятся алгоритмы, представленные формулами. Они наиболее просты для программирования. Заметим, что естественный способ кодировки формул делает программу легко читаемой, но нередко приводит к лишним вычислениям, поэтому, чтобы избежать повторных вычислений и сократить общее количество операций выполняйте тождественные преобразования выражений. С другой стороны, надо знать, что не всегда следует осуществлять оптимизацию, поскольку она является не правилом, а исключением. Этому есть три причины, главная из которых состоит в том, что оптимизация ухудшает наглядность программ, вторая - выгоды от оптимизации должны быть существенными и третья - современные системы, как правило, имеют удовлетворительные оптимизирующие компиляторы.
1.3 Разветвляющийся алгоритм
При исполнении алгоритмов приходится не только находить значения величин, но и анализировать их свойства, сравнивать их друг с другом и в зависимости от результата сравнения выбирать ту или иную ветвь алгоритма.
Алгоритмы, имеющие несколько ветвей, называются нелинейными. К таким относятся разветвляющиеся и циклические алгоритмы. Для их записи применяются составные команды.
Базовая структура "ветвление" определяет выполнение действий в зависимости от выполнения условия. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран.
Язык блок-схем
|Язык QBasic
|Неполное
|IF Условие THEN действия
|Полное
|IF Условие THEN действия 1
|ELSE действия 2
Пример алгоритма ветвления на алгоритмическом языке QBasic:
INPUT «1 или 2?»
IF=1 OR I=2 THEN
PRINT “Ок”
ELSE
PRINT “Вне диапазона”
END IF
Разветвляющаяся блок-схема приведена на рисунке 3.
Рис. 3 Разветвляющаяся блок-схема
Полная форма ветвления.
If <условие>
Then <оператор 1>
Else <оператор 2>;
Неполная форма ветвления
If <условие>
Then <оператор 1>; [6]
Полное ветвление позволяет организовать две ветви в алгоритме (то или иначе), каждая из которых ведет к общей точке их слияния, так что выполнение алгоритма продолжается независимо от того, какой путь был выбран.
Неполное ветвление предполагает наличие некоторых действий алгоритма только на одной ветви (то), вторая ветвь отсутствует, т.е. для одного из результатов проверки никаких действий выполнять не надо, управление сразу переходит к точке слияния.
2. Разработка программы в среде Delphi, показывающая информацию об учениках
2.1 Постановка задачи
Разработать программу для сохранения и обработки информации об учениках (ФИО, класс, адрес и т.д.). В программе сделать несколько отчётов:
- Все ученики одного класса
- Проживают в одном доме
2.2 Блок-схема
2.3 Программный код
|unit жихарева;
interface
uses
Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Data.DB, Data.Win.ADODB, Vcl.StdCtrls,
Vcl.ExtCtrls, Vcl.Grids, Vcl.DBGrids, Vcl.ComCtrls;
type
TForm1 = class(TForm)
ComboBox1: TComboBox;
PageControl1: TPageControl;
DBGrid1: TDBGrid;
PaintBox1: TPaintBox;
DataSource1: TDataSource;
Button1: TButton;
ADOConnection1: TADOConnection;
ADODataSet1: TADODataSet;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
begin
ADODataSet1.Close;
case ComboBox1.ItemIndex of
0:ADODataSet1.CommandText:='select имя, фамилия, очество, адрес, класс FROM клиенты';
1:ADODataSet1.CommandText:='select имя, фамилия, очество, адрес, класс FROM клиенты WHERE [класс] Like "4"';
2:ADODataSet1.CommandText:='select имя, фамилия, очество, адрес, класс FROM клиенты WHERE [адрес] Like "Чапаева, дом 110"';
end;
ADODataSet1.Open;
end;
end.
2.4 Результаты работы
Ученики, проживающие в одном доме
Учащиеся одного класса
Результат формирования всех учеников
Выводы и предложения
В данной работе мы узнали, что такое алгоритм, виды основных алгоритмических структур и их применение, а также какое место занимает алгоритм при решении повседневных задачах. Итак, алгоритм – это точная последовательность предписаний, исполнение которых позволяет посредством конечного числа шагов получить решение задачи, однозначно определяемое исходными данными. Значение его в решении повседневных задачах играет важную роль, так например информатика, как и арифметика, тоже дает явно необходимые знания для выживания человека в современном мире. Например, умение программировать домашнюю бытовую технику: видеомагнитофон (составление списка записываемых телепередач), магнитофон (составление списка записываемых дорожек аудио-CD), сотовый телефон (запоминание номеров, установка параметров, управление роумингом, управление голосовой почтой), часы и таймеры в любом бытовом приборе (выставление и корректировка времени), микроволновые печи, кофеварки, хлебопечки, телевизоры, наконец, компьютеры. Здесь необходимо составление алгоритма, запись которого осуществляется на языке прибора (кодирование в соответствии с прилагаемой инструкцией) с последующей загрузкой составленной программы в компьютер (домашнего) прибора.
Далее мы выяснили, что существуют 3 вида алгоритмов: линейный, разветвляющийся с полным и неполным ветвлением и циклический, который в свою очередь делится на цикл с постусловием и предусловием. Анализируя и сравнивая данные алгоритмические структуры, можно смело сказать, что каждая из них обязательно применяется в программах, при определенных условиях. При выполнении сложных задач, применение каждого из видов алгоритмов, позволит качественно и правильно решить поставленную задачу. Так как в современном мире используются колоссальное количество программ, которые пишутся на разных языках программирования, и задаются сложные параметры, то только грамотное использование алгоритмов помогут правильно разработать программ и решить задачу, так как в исходном коде программы будут задействованы все виды алгоритмических структур. И нельзя строго утверждать, что какой либо из видов алгоритмических структур наиболее важен, так как только совместное применение позволят решить сложные задачи.
Впоследствии написания данной работы, было необходимо решить задачу на языке Delphi и описать этапы её разработки, в которой были применены разные алгоритмические структуры. В результате чего получилась программа, которая соответствовала требованию поставленной задачи.
Список используемой литературы
1. http://festival.1september.ru/articles/571923
2. http://www.infosgs.narod.ru/20.htm
3. Введение в информатику. Лабораторные работы. / Авт.-сост. А.П. Шестаков;
4. Кузнецов А.А. и др. Основы информатики. - М.: Дрофа, 1998
5. Кушниренко А.Г. и др. Информатика. - М.: Дрофа, 1998
6. Л.З. Шауцукова, "Основы информатики в вопросах и ответах", Издательский центр "Эль-Фа", Нальчик, 1994
7. Лебедев Г.В., Кушниренко А.Г. 12 лекций по преподаванию курса информатики. - М.: Дрофа, 1998
8. Шауцукова Л.З. Информатика 10 - 11. М.: Просвещение, 2000
Размещено на Allbest.ru
- Моделирование предметной области «Управление документооборотом» с помощью UML (Соответствие требований MoReq2 функциональности DocsVision)
- Разработка конфигурации «Продажи» в среде 1С:Предприятие 8.3. (Анализ предметной области и постановка задачи)
- Анализ деятельности спортивной организации футбольного клуба «Ливерпуль»
- Предотвращение допинга в спорте и борьба с ним (Классификация и характеристика допинга)
- правовая природа корпораций и корпоративных правоотношений
- Характеристики и типы мониторов для персональных компьютеров
- Автоматизация продажи железнодорожных билетов (Технико-экономическая характеристика предметной области и предприятия0
- Понятие оперативно-розыскной деятельности (Понятие и правовая природа оперативно-розыскной деятельности)
- «Понятие, признаки и правовое регулирование несостоятельности (банкротства)»
- Физические и юридические лица. Общее понятие (Физические лица, как субъекты гражданского права)
- Понятие пенсии по инвалидности (Пенсия по инвалидности)
- Разработка конфигурации «Запасы-склад (приходование товара)» в среде 1С:Предприятие 8.3 (Выбор комплекса задач автоматизации)