Файл: ОСНОВНЫЕ СТРУКТУРЫ АЛГОРИТМОВ: сРАВНИТЕЛЬНЫЙ АНАЛИЗ И ПРИМЕРЫ ИХ ИСПОЛЬЗОВАНИЯ (Алгоритмы и их структура).pdf

Введение

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

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

Цель данной курсовой работы научиться составлять алгоритмы различной структуры, уметь применять их при написании программ на языках программирования Turbo pascal и Turbo c++.

Объектом является понятие алгоритма его описание, структуризация.

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

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

1.Алгоритмы и их структура

1.1 История появления алгоритмов

Слово алгоритм происходит от имени великого среднеазиатского ученого 8–9 вв. Абу Абдуллах Мухаммеда ибн Мусса аль-Хорезми. Из математических работ Аль-Хорезми до нас дошли только две – алгебраическая и арифметическая. Вторая книга долгое время считалась потерянной, но в 1857 в библиотеке Кембриджского университета был найден ее перевод на латинский язык. В ней описаны четыре правила арифметических действий, практически те же, что используются и сейчас. Первые строки этой книги были переведены так: «Сказал Алгоритми. Воздадим должную хвалу Богу, нашему вождю и защитнику». Так имя Аль-Хорезми перешло в Алгоритми, откуда и появилось слово алгоритм. Термин алгоритм употреблялся для обозначения четырех арифметических операций, именно в таком значении он и вошел в некоторые европейские языки.

Постепенно значение слова расширялось. Учёные начали применять его не только к сугубо вычислительным, но и к другим математическим процедурам. Например, около 1360 г. французский философ Николай Орем написал математический трактат «Algorismus proportionum» («Вычисление пропорций»), в котором впервые использовал степени с дробными показателями и фактически вплотную подошёл к идее логарифмов. Когда же на смену абаку пришёл так называемый счёт на линиях, многочисленные руководства по нему стали называть «Algorithmus linealis», то есть правила счёта на линиях.

В 1684 году Готфрид Лейбниц в сочинении «Nova Methodvs pro maximis et minimis, itemque tangentibus…» впервые использовал слово «алгоритм» (Algorithmo) в ещё более широком смысле: как систематический способ решения проблем дифференциального исчисления.

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

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

1.2 Определение алгоритмов

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

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

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

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

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

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

• словесно-формульный (на естественном языке);

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

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

y = (a+1)-b

Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:

- Ввести значения a и b;

- Сложить a и 1;

- Вычесть из a сумму (a+1);

- Вывести у как результат вычисления выражения.

• структурный или блок-схемный;

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

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

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

• Программный, т.е. тексты на языках программирования.

Например произведение двух чисел a и b и вывод на экран на языке BASIC:

Input a,b

c=a*b

print c

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

Алгоритмы линейной структуры;

Алгоритмы разветвленной структуры;

• Циклические алгоритмы;

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

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

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

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

c=a+b

Ввод a, b

Вывод c

Рисунок 2 - блок схема математического выражения c = a+b

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

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

2.2 Разветвленные алгоритмы

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

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

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

Условие

Действие 2

Действие 1

Рисунок 3 - полное ветвление

Неполное ветвление предполагает наличие некоторых действий алгоритма только на одной ветви (то), вторая ветвь отсутствует, т.е. для одного из результатов проверки никаких действий выполнять не надо, управление сразу переходит к точке слияния (рис.4).

Рисунок 4 - неполное ветвление

В зависимости от типа и числа проверяемых условий различают:

- ветвление с простым условием (условие - выражение отношения);

- ветвление с составным условием (условие - логическое выражение);

- сложное ветвление (несколько условий).

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

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

Рисунок 5 – структура множественный выбор

И усеченная структура множественного выбора где опускается действие иначе (рис.6).

Рисунок 6 – множественный выбор без действия иначе

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

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

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

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

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

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