Преподаватель который помогает студентам и школьникам в учёбе.

Основные структуры алгоритмов (сравнительный анализ и примеры их использования)

Содержание:

Введение

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

Объектом исследования являются основные алгоритмические структуры.

Предметом исследования являются особенности алгоритмических структур.

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

Задачи курсовой работы:

Описание основных алгоритмических структур
Сравнить основные алгоритмические структуры, указать примеры их использования
Сравнение реализации основных структур алгоритмов на различных языках программирования высокого уровня.
Создать небольшие программы на языках программирования Pascal и Python, в которых будут использованы основные структуры алгоритмов

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

Алгоритмы

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

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

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

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

Основные особенности алгоритмов:

1. Наличие ввода исходных данных.

2. Наличие вывода результата выполнения алгоритма, поскольку цель выполнения алгоритма – получение результата, имеющего вполне определенное отношение к исходным данных[1].

На основании последней особенности алгоритм будет обладать свойством массовости.

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

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

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

Корректность – алгоритм должен задавать правильное решение задачи.

Массовость (общность) – алгоритм разрабатывается для решения некоторого класса задач, различающихся исходными данными [3].

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

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

Происхождение слова «алгоритм» связано с именем среднеазиатского учёного аль-Хорезми, который считается одним из величайших математиков всех времен и народов.

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

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

Исполнителя, для которого разрабатывается алгоритм
Разработчика алгоритма
Задач, которые решает алгоритм.

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

Основные формы записи алгоритмов изображены на рисунке 1.

Рисунок 1 — Основные способы записи алгоритмов

Словесное описание используется обычно для описания алгоритмов, предназначенных исполнителю – человеку. Такое описание встречается в различных учебниках, справочниках[2]. К примеру, словесная запись алгоритма Эвклида нахождения наибольшего общего делителя (НОД) на естественном языке[4]. Под естественными языками понимаются языки, которые используют люди в разговорной и письменной речи. Например, русский или английский язык.

«Чтобы найти НОД двух чисел, составьте таблицу из двух столбцов и назовите столбцы X и Y. Запишите первое из заданных чисел в столбец Х, а второе - в столбец Y. Если данные числа не равны, замените большее из них на результат вычитания из большего числа меньшего.

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

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

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

Графическая форма записи алгоритмов представляется последовательностью рисунков, структурограммой и блок-схемой[2].

Последовательности рисунков позволяют людям очень быстро и легко воспринимать алгоритм. Такой способ описания подходит при обучении детей дошкольного и младшего школьного возраста[5].

Структурограммы изображают последовательность действий в виде вложенных друг в друга фигур. Каждый блок структурограммы имеет прямоугольную форму и может быть вложен в любой внутренний прямоугольник другого блока.

Рисунок 2 — Структурограмма алгоритма Евклида

Наиболее популярным способом преставления алгоритмов без использования компьютеров являются блок-схемы. Существуют специальные стандарты для построения блок-схем, где определяются графические изображения блоков. Команды алгоритмов записываются внутри блоков на обычном языке или с использованием математических формул. Блоки соединяются по определенным правилам линиями связи, которые показывают порядок выполнения команд[6].

Если алгоритм разработан для решения задачи на компьютере, то для того, чтобы он мог выполниться исполнителем – ЭВМ, его необходимо записать на языке, понятном этому исполнителю. Для этого разработано множество языков программирования для решения задач разных классов [14].

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

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

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

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

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

Рисунок 3 — Линейный алгоритм

Для того, чтобы иметь возможность выбора, какое действие выполнить в зависимости от некоторых условий используют ветвящиеся алгоритмы (или алгоритм с условием). Схема таких алгоритмов представлена на рисунке 4. Сначала происходит проверка условия. В случае, если условие выполняется, происходит выполнение одной группы действий. В случае, если условие не выполняется, происходит выполнение другой группы. Отметим, что обе ветви схемы в любом случае встречаются. Это означает, что линейная группа, помещенная сразу после точки соединения двух ветвей, будет выполнена в любом случае. Это необходимо учитывать при составлении алгоритмов [6].

Начало

Действие 1

…

Действие 2

условие

…

Конец

Истина

Ложь

Рисунок 4 — Алгоритмическая конструкция ветвление

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

Циклический алгоритм — алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. Цикл программы — последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия[6].

Существует два вида цикла: с постусловием и с предусловием. Цикл с предусловием представлен на рисунке 5.

Начало

Тело цикла

…

условие

Да

Нет

Конец

Рисунок 5 — Алгоритмическая конструкция «цикл с предусловием»

Между двумя этими схемами существует два принципиальных отличия. Как следует из названия, в цикле с предусловием сначала идет проверка условий, затем, в случае если условие выполнено, выполняется последовательность действий из тела цикла[4]. Выполнение происходит до тех пор, пока условие истинно. Когда условие становится ложным, происходит выход из цикла. Отсюда становится ясным, что в теле цикла должны выполняются операции, приводящие к изменению значений параметров, содержащихся в условии. Иначе, цикл будет выполняться бесконечно. Такой эффект называется зацикливанием[6].

Рисунок 6 — Алгоритмическая конструкция цикл с постусловием

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

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

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

для i от i1 до i2 шаг k повторять

нц

<тело цикла>

кц

Здесь i — параметр цикла, то есть переменная, изменяющая свое значение на шаг цикла при каждой итерации. При этом параметр iпроходит все значения от i1 до i2 с шагом k.То есть каждый раз к значению i,полученному при выполнении предыдущего шага прибавляется k[4].

Это равнозначно использованию цикла с предусловием, в котором в качестве условия используется i<=i2, а в конце тела цикла выполняется оператор i:=i+k. Для полного соответствия двух схем переменная iопределяется до цикла:

i:=i+1

Реализация основных алгоритмических структур на Pascal и Python

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

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

Язык Pascal был разработан Никлаусом Виртом для обучения программированию студентов в 70-х годах XX века. Этот язык является одним из самых известных в мире языков, служит основой для ряда других, например Object Pascal.

Конструкция ветвление (полное) реализуется с помощью условного оператора[9]:

if <условие> then<оператор1>else <оператор2>;

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

if <условие> then<оператор1>;

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

begin

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

<...>;¶end

Цикл с предусловием (конструкция while) имеет в языке Pascal следующий вид [9]:

while < условие> do <оператор 1>;

Цикл с постусловием (конструкция repeatuntil) имеет в языке Pascalследующий вид:

repeat

<оператор 1>;¶< оператор 2>;¶until<условие>

Реализация цикла с постусловием имеет две особенности на языке Pascal [10]:

конструкция не требует операторных скобок begin...end;
цикл выполняется до тех пор пока условие ложно, выход их цикла соответствует ложному значению условия.

Цикл с параметром записывается с помощью следующей конструкци (цикл for):

for<счетчик1>:= <значение1>to<конечное_значение>do<оператор1>;

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

for<счетчик2> = <значение2>downto<конечное_значение>do<оператор1>;

Отметим, что в реализации цикла со счетчиком на Pascal нет возможности указать шаг не равный единице [11].

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

Интерпретатор — это программа или техническое средство, выполняющее интерпретацию, а также вид транслятора, осуществляющего пооперационную (покомандную) обработку и выполнение исходной программы или запроса. В отличие от компилятора, который осуществляет трансляцию всей программы высокого уровня в машинные коды один раз без ее выполнения (создает объектную программу), интерпретатор транслирует исходную программу команда за командой каждый раз при выполнении и не создает объектного модуля. За счет такого режима выполнение программы происходит медленнее, чем в случае ее обработки транслятором, однако при обработке интерпретатором программы выполняются сразу, без промежуточной стадии трансляции[14].

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

Цикл while в Python записывается следующим образом:

while условие:

выражение 1

выражение 2

выражение 3

Цикл for в Python обладает способностью переберать элементы любого комплексного типа данных (например, строки или списка). В Python цикл for обладает следующим синтаксисом:

for item in sequence:

<выражения>

Cинтаксис оператора if выглядит так.

if выражение:

инструкция_1

инструкция_2

инструкция_n

После оператора if записывается выражение[12]. Если это выражение истинно, то выполняются инструкции, определяемые данным оператором. Выражение является истинным, если его результатом является число не равное нулю, непустой объект, либо логическое True. После выражения нужно поставить двоеточие/

Бывают случаи, когда необходимо предусмотреть альтернативный вариант выполнения программы. Т.е. при истинном условии нужно выполнить один набор инструкций, при ложном – другой. Для этого используется конструкция if – else[13].

if выражение:

инструкция_1

инструкция_2

...

инструкция_n

else:

инструкция_a

инструкция_b

инструкция_x

if выражение_1:

инструкции_(блок_1)

elif выражение_2:

инструкции_(блок_2)

elif выражение_3:

инструкции_(блок_3)

else:

инструкции_(блок_4)

Пример.

a = int(input("введите число:"))

if a < 0:

print("Neg")

elif a == 0:

print("Zero")

else:

print("Pos")

Если пользователь введет число меньше нуля, то будет напечатано “Neg“, равное нулю – “Zero“, большее нуля – “Pos“[12,13].

Примеры использования программ

Линейные программы

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

Python представляет собой интерпретируемый язык, синтаксис которого устроен так, чтобы создание программ требовало от программиста как можно меньше усилий. Код на данном языке выглядит компактно и понятно[14].

Рассмотрим решение одной и той же задачи, вычисление значения функции

на этих языках программирования.

Это простая линейная программа. С помощью Python данная программа может быть представлена в следующем виде[12,13]:

import math

x=float(input("Введите число "))

print(“y =", math.sqrt(x)/math.cos(x))

Для сравнения запишем данный алгоритм на языке Pascal.

var a:real;

begin

write('Введите число ');

readln(a);

write('y = ',sqrt(a+5)/cos(a));

end.

Как видно из приведенного примера, код программы на языке Python состоит из трех строк, а код на языке Pascal из 5.

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

Линейные алгоритмы позволяют выполнять преобразование данных по заданным формулам, содержащих связанные параметры без проведения аналитических преобразований (упрощения формулы)[15].

Рассмотрим решение следующей задачи на языке Pascal.

Пускай необходимо вычислить

при

Блок-cхема

Начало алгоритма

y=2.25;

c=4*sqrt(0.8/y);

b=sin(c)/cos(y);

gamma:=sin(y/b)/cos(y/b)+sin(b/c)/cos(b/c)+sin(c/y)/cos(c/y)

Конец алгортима

Вывод gamma

Рисунок 7 —Блок-схема линейной программы программы на Pascal

Текст программы на языке Паскаль:

var y,b,c,gamma:real;

begin

y:=2.25;

c:=4*sqrt(0.8/y);

b:=sin(c)/cos(y);

gamma:=sin(y/b)/cos(y/b)+sin(b/c)/cos(b/c)+sin(c/y)/cos(c/y);

writeln(gamma:0:4);

end.

Результат выполнения программы: 3.1732

Программы с использованием ветвлений

В качестве программы с использованием ветвлений, рассмотрим программу нахождения НОД двух чисел Фибоначчи[16].

Утверждается, что НОД двух таких чисел равен числу Фибоначчи номера их наибольшего делителя. Другими словами, если мы обозначим, n-число Фибоначчи F(n), то есть:

НОД(Fn, Fm) = F(НОД(n,m))

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

var m,n,l,i,z:integer;

function fib(m:integer):integer;

begin

var i,k,a,b,c:longint;

k:=m;

a:=0;

b:=1;

if m=1 then fib:=1 else begin

for i:=2 to k do begin

c:=a+b;a:=b; b:=c;

fib:=c;end;end;end;

begin

writeln('Введите m>=1 ');

readln(m);

write(m,'-е число Фибоначчи= ');

writeln(fib(m),' ');

writeln('Введите n>=1 ');

readln(n);

write(n,'-е число Фибоначчи= ');

writeln(fib(n),' ');

if m<n then l:=m else l:=n;

for i:=1 to l do

if (m mod i = 0) and (n mod i = 0) then z:=i;

writeln('НОД =',fib(z));

end.

Программы с использования циклов

Рассмотрим нахождение факториала числа на языке Python c помощью функции while[10]:

Листинг программы:

number = int(input("Введите число: "))

i = 1

factorial = 1

while i <= number:

factorial *= i

i += 1

print("Факториал числа", number, "равен", factorial)

Результат работы программы:

Если вводим 5, программа выдает 120.

Одним из наиболее популярных приложений циклов являются суммы рядов и интегралы[15,16].

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

Блок-схема решения данной задачи представлена на рисунке.

начало

j<=15

j=1

S=0

s:=s+b*cos(j+1)/sin(j+1)

b:=ln(j+1)/ln(10);

Вывод s

конец

j=j+1

да

ложь

Рисунок 8 — Блок-схема решения задачи вычисления суммы

Программа на языке Паскаль.

varj:integer; b,s:real;

begin

forj:=1 to 15 do begin

b:=ln(j+1)/ln(10); {b=lg(j+1)}

s:=s+b*cos(j+1)/sin(j+1);

end;

writeln(s:0:4);

end.

Результат.

-2.0825

В данной задаче используется цикл со счетчиком, так как известно число повторений[14].

Или, например, вычисление двойной суммы

с точностью 10^-4

Программа на языке Паскаль.

Рисунок 9 — Блок-схема алгоритма вычисления двойной суммы

var a,s,e,sum: real; i,j:integer;

begin

e:=1E-4; {e=0.0001}

j:=1;

fori:=1 to 10 do begin

repeat

a:=exp(i/j)/(sqr(i)+sqr(j));

j:=j+1;

s:=s+a;

until a<=e;

sum:=sum+s/(i+1);;

end;

writeln((sum*6.4):0:4);

end.

Результат.

27.6367

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

Заключение

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

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

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

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

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

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

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

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

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

Библиография

Информатика: Учебник для вузов. Стандарт третьего поколения / Макарова Н.В, Волков В.Б.-СПб.:Питер, 2015.
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ, 3-е издание — М.: Вильямс, 2013.
Стариченко, Б.Е. Теоретические основы информатики : учебник для вузов / Б.Е. Стариченко .— 3-е изд., перераб. и доп. — М. : Горячая линия – Телеком, 2016 .— 401 с. — ISBN 978-5-9912-0462-0
Дж. Макконелл, Основы современных алгоритмов, М.: «Техносфера», 2004, С. 10-11
КуМир [Электронный ресурс]. URL: https://www.niisi.ru/kumir/(Дата обращения 15.02.2018)
Акулов О.А. Информатика: учебник / О.А. Акулов, Н.В. Медведев. – М.: Омега-П, 2007. – 270 с.
Алексеев А.П. Информатика 2007 / А.П. Алексеев. – М.: СОЛОН-ПРЕСС, 2007. – 608 с.
Лукин С.М., Турбо-Паскаль 7.0. Самоучитель для начинающих // ¶М:Диалог-МИФИ, 2015.
Абрамов, В.Г.; Трифонов, Н.П. и др. Введение в язык Паскаль; Наука, 2011. - 320 c.
Епанешников, А.М.; Епанешников, В.А. Программирование в среде Turbo Pascal 7.0; М.: ДИАЛОГ-МИФИ; Издание 4-е, испр., 2013. - 367 c
Учебник по паскалю [Электронный ресурс]. URL: http://pcfu.ru/stati/programmirovanie/uchebnik-po-paskalyu-oglavlenie//(Дата обращения 15.02.2018)
Доусон М. Программируем на Python / М.Доусон,. – СПб.: Питер, 2014. – 416 с.
Лутц М. Программирование на Python/М. Лутц- том II, 4-е издание. Пер. с англ. – СПб.: Символ-Плюс, 2011. – 992 с.
Баженова, И.Ю. Языки программирования: Учебник для студентов учреждений высш. проф. образования / И.Ю. Баженова; Под ред. В.А. Сухомлин. — М.: ИЦ Академия, 2012. — 368
Агальцов, В. П. Математические методы в программировании / В.П. Агальцов. - М.: Форум, 2012. - 240 c
Грин, Д. Математические методы анализа алгоритмов / Д. Грин, Д. Кнут. - М., 2012. - 496 c.