Виды алгоритмов и их представление при решении задач различных структур

Размещено на http://www.allbest.ru/

МИНИСТЕРСВО СЕЛЬСКОГО ХОЗЯЙСТВА

КАЗАХСКИЙ АГРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ имени С. СЕЙФУЛЛИНА

КАФЕДРА КСиПО

СПЕЦИАЛЬНОСТЬ Компьютерная Инженерия

Курсовая работа

по дисциплине Алгоритмы и структуры данных

на тему: «Виды алгоритмов и их представление при решении задач различных структур»

Выполнил: студент 2 курса

Т?рехан Олжас Н?рлан?лы

Нур-Султан 2021

Содержание

Введение

1. Алгоритмы и операторы

1.1 Виды алгоритмов

1.2 Способы записи алгоритмов

1.3 Графический способ

1.4 Програмный способ

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

2.1 Примеры линейных алгоритмов

3. Разветвляющий алгоритм

4. Циклические алгоритмы

5. Вспомогательный алгоритм

Список используемой литературы

Введение

Понятие алгоритма такое же основополагающее для информатики, как и понятие информации. Именно поэтому нужно в этом разбираться.

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

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

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

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

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

1. Алгоритмы и операторы

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

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

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

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

1. Дискретность (от лат. discretus -- разделенный, прерывистый) - это разбиение алгоритма на ряд отдельных законченных действий.

2. Детерминированность (от лат. determinate -- определенность, точность) - любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае.

3. Массовость - один и тот же алгоритм можно использовать с разными исходными данными.

4. Результативность - алгоритм должен приводить к достоверному решению.

Основная цель алгоритмизации - составление алгоритмов для ЭВМ с дальнейшим решением задачи на ЭВМ.

Примеры алгоритма:

1. Любая мебель, купленная в магазине, снабжается инструкцией по его сборке. Данная инструкция и является алгоритмом для правильной сборки мебели.

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

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

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

1. словесная (запись на естественном языке);

2. псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);

3. графическая (блок-схемы);

4. программная (тексты на языках программирования - код программы).

1.1 Виды алгоритмов

С понятием - алгоритм, вроде разобрались. Алгоритм в программировании -- это программа. Каждая программа способна решать собственную задачу по-своему. Возможно ли такое, что разные скрипты или программы решают одну и ту же задачу в программировании, но разными путями? Возможно. Каждый такой путь -- это и будет отдельный алгоритм в программировании.

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

Но все многообразие алгоритмов можно разделить на 4 основных типа:

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

2. Разветвляющийся алгоритм.

3. Циклический алгоритм.

4. Вспомогательный алгоритм.

1.2 Способы записи алгоритмов

Выделяют три наиболее распространенные на практике способа записи алгоритмов:

· словесный (запись на естественном языке);

· графический (запись графическими символами);

· программный (тексты на языках программирования).

Словесный способ :

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

Примера словесного способа записи алгоритма рассмотрим алгоритм нахождения площади прямоугольника

S=a*b,

где S - площадь прямоугольника; а, b - длины его сторон.

Очевидно, что a, b должны быть заданы заранее, иначе задачу решить невозможно.

Словесный способ записи алгоритма выглядит так:

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

· Задать численное значение стороны a.

· Задать численное значение стороны b.

· Вычислить площадь S прямоугольника по формуле S=a*b.

· Вывести результат вычислений.

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

1.3 Графический способ описания алгоритмов

Для более наглядного представления алгоритма используется графический способ. Существует несколько способов графического описания алгоритмов. Наиболее широко используемым на практике графическим описанием алгоритмов является использование блок-схем. Несомненное достоинство блок схем - наглядность и простота записи алгоритма.

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

Таблице 1

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

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

Правила оформления программы:

1. любой алгоритм имеет название;

2. алгоритм начинается с открывающей скобки “{“ и заканчивается закрывающей скобкой “}”;

3. в алгоритм могут входить только те команды, которые есть в СКИ исполнителя;

4. каждая команда заканчивается знаком “;”, который обозначает конец команды;

5. для того, чтобы нам было легче разбираться в программах, используют комментарии, которые начинаются знаками “/*” и заканчиваются знаками “*/”; исполнитель не обращает внимания на комментарии в алгоритме.

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

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

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

Теперь про графическую форму линейного алгоритма.

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

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

Блок начала-конца:

Блок ввода-вывода данных (отображает список вводимых и выводимых переменных):

Арифметический блок (отображает арифметическую операцию/группу операций):



Условный блок (позволяет описать условие). Алгоритмы с таким блоком используются при графической визуализации алгоритмов с ветвлением:

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

Рис. 1

А вот, как решается задача по нахождению площади треугольника по формуле Герона. Здесь a, b, c - это длины сторон, S - площадь треугольника, P - периметр.

Рис. 2

Следует обратить внимание, что запись «=» -- это не математическое равенство, а операция присваивания. В результате этой операции переменная, стоящая слева от оператора, получает значение, которое указано справа. Значение не обязательно должно быть сразу определено (a = 3) -- оно может вычисляться посредством выражения (a = b + z), где b = 1, a z = 2.

2.1 Примеры линейных алгоритмов

Рассмотрев примеры решения на языке Pascal, увидим следующую картину:



Рис. 3

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

Рис. 4

3. Разветвляющийся алгоритм

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

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

Рис. 5

Пример: Известны коэффициенты и с квадратного уравнения. Составить алгоритм вычисления корней квадратного уравнения.

Рис. 6

Входные данные: a, b, c.

Выходные данные:x₁, x₂.

4. Циклические алгоритмы

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

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

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

Рис. 7

Цикл с предусловием (иначе цикл пока) имеет вид:

Таблица 2

Форматы записи операторов алгоритма	Блок-схема	Форматы записи операторов на Паскале
Пока (условие) нц серия команд кц		while условие dobegin серия команд; end;

Где условие - выражение логического типа.

Пример: Вычислить если x изменяется от 0 до 2 с шагом 0,1.

Решение: Схема алгоритма имеет вид:

Рис. 8

Пример. Вычислить произведение чисел от 1 до 5 используя различные варианты цикла

Математическая модель: Р= 1· 2· 3· 4· 5=120

Составим алгоритм в виде блок-схемы.

Рис. 9

Для проверки правильности алгоритма заполним трассировочную таблицу.

Таблица 3

Шаг	Операция	Р	i	Проверка условия
1	P:=1	1
2	i:=1;	1	1
3	i<=5P:=P*Ii:=i+1	1	1	1<=5, да (истина)
4	i<=5P:=P*Ii:=i+1	2	2	2<=5, да (истина)
5	i<=5P:=P*Ii:=i+1	6	3	3<=5, да (истина)
6	i<=5P:=P*Ii:=i+1	24	4	4<=5, да (истина)
7	i<=5P:=P*Ii:=i+1	120	5	5<=5, да (истина)
8	i<=5P:=P*Ii:=i+1			6<=5, нет (ложь)

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

Шаг первый: Р присваивается значение один.

Шаг второй: i присваивается значение один.

Шаг третий: при i равном единице проверяем условие один меньше или равен пяти, да, условие истинно, значит Р присваивается значение один умноженное на один, будет два. Для i: один плюс один, будет два.

Шаг четвертый: при i равном двум проверяем условие два меньше или равен пяти, да, условие истинно, значит Р присваивается значение 2 умноженное на один, будет 2. Для i: два плюс один, будет три.

Шаг пятый: при i равном трем проверяем условие три меньше или равен пяти, да, условие истинно, значит Р присваивается значение два умноженное на три, будет шесть. Для i: три плюс один, будет четыре.

Шаг шестой: при i равном четырем проверяем условие четыре меньше или равен пяти, да, условие истинно, значит Р присваивается значение шесть умноженное на четыре, будет двадцать четыре. Для i: четыре плюс один, будет пять.

Шаг седьмой: при i равном пяти проверяем условие пять меньше или равен пяти, да ,условие истинно, значит Р присваивается значение двадцать четыре умноженное на пять, будет сто двадцать. Для i: пять плюс один, будет шесть.

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

Program Pr1;Var i: integer;BeginP:=1;i:=1;While i<=5 do begin P:=P*i; i:=i+1; end;Write (`P=', P);end.

Для цикла с постусловием построим блок-схему и трассировочную таблицу.

В результате получаем последнее значение равное сто двадцати на седьмом шаге

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

В результате получаем последнее значение равное сто двадцати на шестом шаге

5. Вспомогательный алгоритм

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

Пример. У нас есть вспомогательный алгоритм factorial, который вычисляет значение факториала целого числа k. Составить блок-схему алгоритма вычисления значения выражения 1! + 2! + … + n!. Вспомним, что k! = 1 * 2 * … * k.

Рис. 10

Пример:

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

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

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

Рис. 11

Процедура имеет имя Sort и два формальных параметра: n - длина массива, z - имя массива. Сортировка осуществляется при помощи структуры вложенных циклов. Наружным циклом являются блоки 2 - 8. Внутренний цикл образован блоками 3 - 7. Один виток наружного цикла представляет собой отдельный проход по массиву при сортировке. Внутренний блок предназначен для перебора соседних пар массива при таком проходе.

В начале наружного цикла в блоке 2 логической переменной b присваивается значение true. Под этим мы будем понимать, что до прохода по парам, мы предполагаем, что массив отсортирован. Далее выполняется внутренний цикл блоков 3 - 7. В нем переменная цикла i меняется от 1 до n-1, поскольку, если число элементов равно n, то соседних пар будет n-1. Для каждой текущей пары соседних элементов z[i] и z[i+1] проверяется условие 4. Если оно выполняется, то значит эту пару надо переставлять и зафиксировать тот факт, что массив оказался неотсортированным, что фиксируется оператором блока 5. Перестановка пары происходит в блоке 6 посредством обращения к процедуре Perm. Если же условие не выполнилось, то пара отсортирована и операторы фиксации и перестановки надо обойти и уйти в конец цикла к блоку 7, который вернет управление к началу цикла 3. После выхода из цикла 3 - 7 в блоке 8 осуществляется проверка значения переменной b. Если она истинна, то в цикле не было перестановок, то есть массив отсортирован, и процедуру следует закончить. Если же b ложно, то имели место перестановки, и нужно совершать новый проход по парам, для чего следует отправить управление процессом на блок 2. Таким образом, за несколько проходов по массиву, он будет отсортирован.

Рис. 12

В данном алгоритме сначала вводятся длины массивов n и m, затем сами массивы x и y. В блоке 3 обращением к процедуре Sort сортируется массив x, а в блоке 8 - массив y. В блоке 5 массивы выводятся на печать.

алгоритм циклический блок-схема

Список используемой литературы

1. «Современные информационные технологии» авторы преподаватели центра «Турбо»

2. «Алгоритмы и исполнители» Поляков К.

3. «Основы алгоритмизации и программирования» Т.А. Жданова; Ю.С. Бузыкова

4. С и С++: Алгоритмы и приемы программирования: пер с англ. / А. Фридман, Л. Кландер, М. Михаэлис, Г. Шилдт; под ред. В. Тимофеева. -- М.: Бином: Бином-пресс, 2003. -- 560 с.

Размещено на Allbest.ru