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

Содержание:

Введение

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

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

Цель данной курсовой работы научиться составлять алгоритмы различной структуры, уметь применять их при написании программ на языках программирования 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 Алгоритмическая структура цикл

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

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

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

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

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

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

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

Арифметическим называется циклический процесс, число повторений в котором может быть определено заранее, т.е. не зависит от результатов счёта в теле цикла. Такой цикл еще называют счетчиком (рис.7)

Рисунок 7 – цикл со счетчиком

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

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

Рисунок 8 – цикл с предусловием

Цикл с постусловием сначала проводит действием потом проверяет условие если оно правдиво заканчивает цикл если ложно то возвращается обратно и снова проводит действие (рис.9).

Рисунок 9 – цикл с постусловием

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

3.Основные структуры алгоритмов на практике в turbo pascal и turbo с++

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

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

Возьмем простенькую задачу вычисления объема пирамиды при известных: площади основания и высоте. Формула вычисления V=(1/3)*s*h.

Рисунок 10 – решение задачи в Turbo pascal

Описание программы:

Называем программу p1; добавляем модуль uses crt для того чтобы очищать экран вывода; описываем переменные V,s,h вещественным типом real; очищаем экран clrscr; просим ввести s и h командой writeln ; считываем их с клавиатуры командой read; далее считаем V и выводим на экран результат.

Рисунок 11 - результат решения при вводе s=4,h=5

Рисунок 12 - решение задачи в Turbo C++

Описание программы:

#include подключает нужные библиотеки к программе, math.h заголовочный файл стандартной библиотеки языка программирования С, разработанный для выполнения простых математических операций, iostream.h заголовочный файл с классами, функциями и переменными для организации ввода-вывода в языке программирования C, conio.h заголовочный файл объявляет несколько библиотечных функций для работы с «консольным вводом и выводом» программы, очищаем экран вывода функцией clrscr(); описываем вещественные переменные V, s, h; просим ввести площадь s и высоту h командой cout, и считываем их с клавиатуры командой cin; вычисляем объем V и выводим на экран; функция getch() задерживает экран вывода.

Рисунок 13 - результат решения при вводе s=4,h=5.

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

3.2 Разветвленные структуры алгоритмов

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

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

Создадим программы решения уравнения:

Рисунок 14 – решение задачи в Turbo pascal

Описание программы:

Называем программу p2; добавляем модуль uses crt для того чтобы очищать экран вывода; описываем переменные y,x целочисленным типом integer; очищаем экран clrscr; просим ввести командой writeln ; считываем его клавиатуры командой read; далее делаем сравнение x c 0 если он больше или равен 0 то считаем y по формуле y=x*x и выводим на экран результат, если меньше 0 то y=2*x и выводим результат на экран.

Рисунок 15 - результат решения при x>0

Рисунок 16 - при x=0

Рисунок 17 - при x<0

Рисунок 18 - решение задачи в Turbo C++

Описание программы:

Подключаем стандартные библиотеки iostream и conio; очищаем экран командой clrscr; описываем целочисленные переменные y,x типом int; просим ввести x с помощью команды cout; считываем x с клавиатуры с помощью cin; далее делаем сравнение x c 0 если он больше или равен 0 то считаем y по формуле y=x*x и выводим на экран результат, если меньше 0 то y=2*x и выводим результат на экран.

Рисунок 19 - результат решения при x>0

Рисунок 20 - при x=0

Рисунок 21 - при x<0

Результаты программ идентичны. Строение конструкции if так же совпадают с некоторыми отличиями в символах.

3.2.2 Множественный выбор

Один из разновидностей разветвления это множественный выбор. Составим программу, которая после введенного с клавиатуры числа (в диапазоне от 1 до 99), обозначающего денежную единицу, дописывает слово «Копейка» в правильной форме. Например, 5 копеек, 41 копейка и т. д. на двух языках программирования.

Рисунок 22 – решение задачи в Turbo pascal

Описание программы:

Называем программу p3; добавляем модуль uses crt для того чтобы очищать экран вывода; описываем переменные n целочисленным типом integer; очищаем экран clrscr; просим ввести n командой writeln ; считываем его с клавиатуры командой read; далее делаем сравнение n c 1 и 99 если он больше или равен 1 и меньше или равно 99 то выводим на экран число n, и с помощью case выбирается нужное окончание слова kopeika, добавляется к n ; если n не входит в этот диапазон значений выводим на экран надпись oshibka vvoda dannih .

Рисунок 23 - результат выполнения программы

Рисунок 24 – решение задачи в Turbo C++

Описание программы:

Подключаем стандартные библиотеки iostream и conio; очищаем экран командой clrscr; описываем целочисленную переменную n типом int; просим ввести n с помощью команды cout; считываем n с клавиатуры с помощью cin; далее с помощью оператора множественного выбора switch производим проверку числа n и выводим нужное окончание слова kopeika; если диапазон цифр не верный то командой default выводим надпись oshibka vvoda dannih.

Рисунок 25 - результат выполнения программы

Результаты программы идентичны. Операторы множественного выбора отличаются. В pascal чтобы проверить число на диапазон от 1до 99 мне пришлось использовать конструкцию if в то время как в c++ есть специальный оператор default на который программа переходит если не выполнено не одно из условий выбора case. Но так же в c++ есть минус того, что нельзя в case прописать диапазон цифр идущий по порядку и мне пришлось писать каждую по очереди, это очень увеличило размер программы и усложнило ее составление.

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

3.3.1 Цикл со счетчиком

Составим программу подсчета суммы чисел от 1 до 100. (1+2+3+…+100) (не используя формулу суммы членов арифметической прогрессии).

Рисунок 26 – решение задачи в Turbo pascal

Описание программы:

Называем программу p4; добавляем модуль uses crt для того чтобы очищать экран вывода; описываем переменные i,S целочисленным типом integer; очищаем экран clrscr; далее выполняем цикл со счетчиком тело цикла будет считать сумму когда i станет 100, после сложения, компилятор не вернется назад а продолжит выполнять следующую команду; эта команда writeln которая выводит сумму .

Рисунок 27 - результат выполнения программы

Рисунок 28 – решение задачи в Turbo C++

Описание программы:

Подключаем стандартные библиотеки iostream и conio; очищаем экран командой clrscr; описываем целочисленные переменные S,i типом int; обнуляем S; далее выполняем цикл со счетчиком тело цикла будет считать сумму когда i станет 100, после сложения, компилятор не вернется назад а продолжит выполнять следующую команду; эта команда cout которая выводит сумму.

Рисунок 29 - результат выполнения программы

Результаты выполнения программы идентичны. Конструкция цикла счетчика for так же совпадают с некоторыми отличиями в символах.

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

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

Решим задачу: в первый день пловец проплыл 3 км. В каждый следующий день он проплывал на 10% больше, чем в предыдущий. В какой по счету день пловец начнет проплывать более 5 км?

Рисунок 30 – решение задачи в Turbo pascal

Описание программы:

Называем программу p5; добавляем модуль uses crt для того чтобы очищать экран вывода; описываем переменные i,S целочисленным типом integer и вещественным real; очищаем экран clrscr; далее выполняем цикл с предусловием, тело цикла будет считать расстояние которое проплыл пловец за день и так же считать дни, после будет сравнение S c 5 и если оно больше или равно цикл останавливается и управление передается дальше; команда writeln выводит на экран количество дней .

Рисунок 31 - результат выполнения программы

Рисунок 32 – решение задачи в Turbo C++

Описание программы:

Подключаем стандартные библиотеки iostream и conio; очищаем экран командой clrscr; описываем переменные S,i целочисленным типом int и вещественным float; присваиваем начальные значения S и I; далее выполняем цикл с предусловием, тело цикла будет считать расстояние, которое проплыл пловец за день и так же считать дни, после будет сравнение S c 5 и если оно больше или равно цикл останавливается и управление передается дальше; команда cout выводит на экран количество дней.

Рисунок 33 - результат выполнения программы

Результаты выполнения программы идентичны. Конструкция цикла c предусловием while так же совпадает с некоторыми отличиями в символах. Если условие сразу оказывается ложным, оператор while не выполняется ни разу. В теле цикла должны быть операторы, которые могут изменить значение условия, сделав его ложным. Иначе цикл будет выполнятся бесконечное число раз. 

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

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

Рисунок 34 – решение задачи в Turbo pascal

Называем программу p6; добавляем модуль uses crt для того чтобы очищать экран вывода; описываем переменные i,S целочисленным типом integer ; очищаем экран clrscr; S и I делаем равным нулю;далее выполняем цикл с постусловием, тело цикла будет считать сумму введенных чисел, после попросит ввести число и проверится условие если не отрицательное цикл повторяется, иначе выводится сумма на экран командой writeln.

Рисунок 35 - результат выполнения программы

Рисунок 36 – решение задачи в Turbo C++

Описание программы:

Подключаем стандартные библиотеки iostream и conio; очищаем экран командой clrscr; описываем переменные S,i целочисленным типом int; присваиваем начальные значения S и I; тело цикла будет считать сумму введенных чисел, после попросит ввести число и проверится условие если не отрицательное цикл повторяется, иначе выводится сумма на экран командой cout.

Рисунок 37 - результат выполнения программы

Результаты выполнения программы идентичны. В pascal и c++ ипользуются разные конструкции цикла с постусловием. В pascal используется repeat…until в с++ используется do…while. Проверка и завершение цикла отличаются. В pascal цикл заканчивается при истинности условия, а в c++ при ложном условии.

Заключение

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

• Алгоритм встречаются не только в программах, но и в нашей жизни. От того какой алгоритм мы создадим, зависит его эффективность. Изображение алгоритма на бумаге повышает наглядность и облегчает создание программы.
• Одной из сложных задач является составление алгоритмических структур в программе. Линейная структура в создании самая легкая, но она не позволяет выполнять условия программы, если такие требуются. На помощь приходят более сложные структуры ветвления и цикла.
• При составлении программ я выяснил, что их код по структуре практически одинаков, отличаются они только словами команд, хотя означают почти тоже самое. Но в таких конструкциях как множественный выбор и цикл с постусловием конструкции существенно отличаются друг от друга. Pascal используется, в основном, для обучения программированию, когда как C++ используется программистами для создания программного обеспечения. Поэтому код C++ более сложен и разнообразен, а также постоянно развивается.

Список используемый источников

1. Удивительная история информатики и автоматики /В.В. Шилов - Издательство: ЭНАС-КНИГА, 2013г. – 7 с.

2. Основы алгоритмизации и программирования. Язык Си 2-е издание /Е.И. Демидович - Издательство: БХВ-Петербург, 2008г.

3. Информатика. Базовый курс./С.В. Симонович - СПб.: Питер, 2001

4. Технология программирования / Ю.Ю.Громов, О.Г. Иванова, М.П. Беляев, Ю.В. Минин – Издательство: ФГБОУ ВПО«ТГТУ», 2013г.

5. Программирование в Turbo Pascal 7.0 и Delphi.- 2-е издание, перераб. и доп.- Спб. / Культин Н.Б. Издательство: БХВ-Петербург,2002.-416 с.;ил.

6. Турбо Паскаль 7.0. Самоучитель. – СПб.: Питер; К.: Издательская группа BHV, 2002.-576 с.

7. Турбо Паскаль. /С.А. Немнюгин - СПб: Издательство «Питер», 2000. – 496 с.: ил.

8. Turbo Pascal для студентов и школьников / Г.Г. Рапаков, С.Ю. Ржеуцкая,  Издательство: БХВ-Петербург, 2005 г.

9. Алгоритмы. Вводный курс /Томас Х. Кормен – Издательство

Вильямс, 2015г.