Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ ПРОГРАММ).pdf

ВВЕДЕНИЕ

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

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

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

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

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

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

Предмет исследования данной темы – основные структуры алгоритмов: сравнительный анализ и примеры их использования

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

ГЛАВА I. ОСНОВЫ АЛГОРИТМИЗАЦИИ

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

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

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

Термин «алгоритм (алгорифм)» появился в Средние века, когда европейцы знакомились со способами выполнения арифметических действий в десятичной системе счисления по книге узбекского математика Абу Джафара Муххамада ибн Мусы аль-Хорезми (783–850 г.) «Арифметика индусскими цифрами», получившей широкую известность. Слово «алгоритм» есть результат европейского произношения слов «аль-Хорезми» («аль-Хорезми» – человек из города Хорезми; в настоящее время город Хива в Хорезмской области Узбекистана).

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

Алгоритм (по Д. Э. Кнуту) – это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность.

Алгоритм (по А. Н. Колмогорову) – это система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

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

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

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

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

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

Алгоритм характеризуется следующими свойствами: дискретностью, массовостью, определенностью, результативностью, формальностью.

• Дискретность. Алгоритм должен представлять процесс решения задачи как последовательность выполнения простых действий (шагов, этапов). При этом для выполнения каждого действия алгоритма требуется время.
• Детерминированность (Однозначность). Каждое действие (шаг, этап) должно быть четким, однозначным, исключающим произвольное толкование и не оставляющим места для двусмысленности. Выполнение алгоритма носит, по сути, механический характер и не требует никаких дополнительных указаний.
• Результативность. Алгоритм должен приводить к решению задачи или сообщению, что задача решений не имеет за конечное число шагов.
• Конечность. Каждое отдельное действие, как и весь алгоритм должны иметь возможность реального исполнения. Поэтому алгоритм имеет придел, т. е. конечен.
• Массовость. Алгоритм разрабатывается в общем виде так, чтобы его можно было применять для класса задач, различающихся только исходными данными. При этом исходные данные выбираются из некоторой области, которая называется областью применяемости алгоритма. Например, для решения квадратного уравнения ax+2 +bx+c=0, коэффициенты действительные числа, а ≠ 0, и а, в, с – различные.
• Определенность (детерминированность, точность) – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов.
• Формальность — это свойство указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции.

1.3 Типы алгоритмов

Алгоритмы бывают линейные, разветвляющиеся и циклические.

Линейный алгоритм – это алгоритм, в котором действия выполняются только один раз и строго в том порядке, в котором они записаны.

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

Линейные алгоритмы в математике – это, например, вычисление площадей фигур.

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

В блок-схемах разветвляющихся алгоритмов всегда есть логический блок.

Циклический алгоритм (цикл) – это алгоритм, в котором группа операторов выполняется несколько раз подряд. Блок-схема цикла обязательно содержит логический блок.

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

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

Для реализации процесса обработки данных используется оператор присваивания.

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

ГЛАВА II. АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ

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

Существует 3 типа основных алгоритмических структур:

следование;

развилка;

цикл.

Следование представляет собой последовательное выполнение операций и представляется алгоритмически последовательностью блоков «Процесс»:

Развилка, в свою очередь, делится на:

неполную развилку;

полную развилку;

ветвление.

Развилка представляет собой блок выбора (проверка условия).

Неполная развилка выполняет последовательность операций только по одной из веток.

Условие?

Блок операций

Реализация неполной развилки в С имеет вид:

1. if (условие)
2. {
3. операции;
4. }

Полная развилка выполняет последовательность операций по каждой из двух веток (при выполнении или невыполнении условия):

Условие?

нет

да

Блок операций 2

Блок операций 1

Реализация полной развилки в C имеет вид:

1. If (условие)
2. {
3. операции блока 1;
4. }
5. else
6. {
7. операции блока 2;
8. }

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

Выражение

1

Блок операций 1

Блок операций 2

2

...

Блок операций n

n

Блок операций по умолчанию

Реализация ветвления в C имеет вид:

1. switch (выражение)
2. {
3. case 1:
4. блок операций 1;
5. break;
6. case 2:
7. блок операций 2;
8. break;
9. ...
10. case n:
11. блок операций n;
12. break;
13. default:
14. блок операций по умолчанию;
15. }

Существует 3 основных вида циклов:

цикл с предусловием;

цикл с постусловием;

параметрический цикл.

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

Цикл

Условие?

Блок операций

Цикл

Реализация цикла с предусловием на C:

1. while (условие)
2. {
3. операции;
4. }

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

Цикл

Блок операций

Цикл

Условие?

Реализация на С цикла с поступлением:

1. do {
2. операции;
3. } while (условие);

Параметрический цикл — это цикл с заданным числом повторений.

Цикл

Для П от НЗ до КЗ шаг Ш

Блок операций

Цикл

Реализация параметрического цикла на Си (П — параметр, НЗ — начальное значение, КЗ — конечное значение (в общем случае — условие продолжения цикла), Ш — шаг):

1. for (П = НЗ; П !=КЗ; П +=Ш)
2. {
3. операции;
4. }

2.2 Языки программирования

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

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

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