Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Реализация циклического алгоритма).pdf

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

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

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

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

Для реализации поставленной цели необходимо выполнить ряд задач:

- Изучить понятие алгоритма и его свойства;

- Рассмотреть основные алгоритмические конструкции;

- Провести обзор программных и аппаратных средств;

- Изучить реализацию циклического алгоритма;

- Рассмотреть реализацию линейного алгоритма и т.д.

Глава 1 Теоретические основы структуры алгоритмов

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

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

Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления, описанными узбекским математиком Муххамедом бен Аль-Хорезми («аль-Хорезми» - человек из города Хорезми; в настоящее время город Хива в Хорезмской области Узбекистана). Слово алгоритм – есть результат европейского произношения слов аль-Хорезми. Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.^[1]

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

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

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

Дискретность (разрывность — противоположно непрерывности) - это свойство алгоритма, характеризующее его структуру: каждый алгоритм состоит из отдельных завершенных действий ("общих шагов").

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

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

Эффективность-свойство любого алгоритма быть конечным (может быть очень большим) числом шагов. Вопрос учета бесконечных алгоритмов-это еще больше, чем теория и алгоритмы.^[2]

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

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

Следующие способы описания алгоритма: словесное описание, псевдокод, схема, программное обеспечение.

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

Нет правил, составьте словесное описание. Алгоритм написан в любой форме, естественной, например, для России. Этот способ описания не является общей, потому что это не совсем официальная ("официальный" означает, что описание полностью подготовлен и будет учитывать все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.

В псевдокоде описания алгоритма приведена структура естественного, частично формализованного языка, позволяющая выявить основные этапы решения задачи, вплоть до точной записи языка программирования. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика.^[3]

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

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

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

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

Разработка линейного алгоритма

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

Линейные вычислительные процессы происходят, например, при вычислении арифметических выражений, когда выполняются определенные числовые данные и соответствующие условия для деятельности задачи. На рисунке 1 приведен пример линейного алгоритма, определяющего процесс, который вычисляется в арифметическом выражении у=(b2-ас):(а+с).

Рисунок 1 – Линейный алгоритм

Разветвляющаяся алгоритмическая конструкция

Разветвляющейся (или ветвящейся) является построение алгоритма, который предлагает выбор между различными альтернативами в зависимости от значения входных данных. Для каждого набора входных данных, алгоритм ветвления сводится к линейной. Различают неполное (если — то) и совершенное (если — то — другое) ветвления. Вся ветвь позволяет организовать две ветви алгоритма (так или иначе), каждая из которых приводит к общей точке их агрегирования, так что алгоритм будет продолжаться независимо от того, какой путь был выбран.^[4]

Ложь (Нет) Истина (Да)

Рисунок 2 - Полное ветвление

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

Истина (Да)

Ложь (Нет)

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

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

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

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

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

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

Алгоритмическая конструкция «Цикл»

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

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

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

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

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

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

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

Арифметика-это циклический процесс, число повторений, которые могут быть определены заранее, т. е. не зависит от результатов тела в течение.

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

На следующих рисунках показаны примеры циклических процессов.

Рисунок 4 - Блок-схема цикла с предусловием

Рисунок 5 - Блок-схема цикла с постусловием

1.3 Обзор программных и аппаратных средств

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

Pascal был создан в 1968 году Никлаусом Виртом, после участия в работе комитета по разработке стандарта языка Алгол-68. Он был выпущен в 1970 году в небольшой и эффективный язык, чтобы способствовать хорошему стилю программирования, использовать структурное программирование и структурированные данные.^[5]

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

Компилятор Pascal был написан на самом Pascal с помощью метода продвижения.

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

В языке оригинала был, однако, ряд ограничений: невозможность панелей, различающихся по длине для ношения, отсутствие каких-либо нормальных инструментов для работы с динамической памятью, ограниченная библиотека ввода / вывода, отсутствие инструментов, сочетающих функции, написанные на других языках, отсутствие инструментов для разделения состоит и т.д. Детальный анализ недостатков языка Паскаль в это время была проведена Брайан kernig в статье "Почему Паскаль не мой любимый язык "" эта статья вышла в начале 1980-х, когда там был уже язык модуль - 2, потомок Паскаля, который был выпущен большинства его пороков, а также развитие диалектов, некоторые из Паскаля исправлены ошибки ИСО 1982 года, в частности языка, были открыты таблицы, стала возможность использовать те же методы для борьбы с одномерных массивов различных размеров.