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

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

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

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

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

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

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

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

Выполнил: студент 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

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

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

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

Рис. 8

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

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

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

Рис. 9

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

Таблица 3