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

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

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

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

Предметом исследования служат общие принципы построения алгоритмов.

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

Задачи курсовой работы:

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

Отметим, что в работе были использованы языки программирования Pascal и С++, так как первый из них чаще всего используется в России в качестве учебного языка программирования, а С++ является одним из самых популярных современных универсальных языков программирования высокого уровня.

Алгоритмы — основа программирования

Общие принципы построения алгоритмов

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

Алгоритм – это последовательность действий, которые необходимо выполнить для достижения поставленной цели или решения некоторой задачи [10]. С алгоритмами мы постоянно встречаемся в нашей обыденной жизни, порой даже не задумываясь об этом. Например, программа проведения конференции является таким алгоритмом. Также, примером алгоритма может быть правила перехода по пешеходному переходу. Сначала пешеходу необходимо посмотреть налево, чтобы убедиться, что проезжающие машины заметили его и готовы остановиться, чтобы пропустить его. Тогда можно идти до второй половины проезжей части. На второй половине также необходимо становиться и посмотреть направо, пропускают ли вас машины, едущие по данной полосе. После этого можно завершить переход. Инструкция по эксплуатации бытовой техники, например, телевизора, также содержит множество алгоритмов. Алгоритмы включения различных функций и режимов, алгоритмы действий при неисправностях.

Современное определение понятия «алгоритм» появилось в середине XX век на основании работ Тьюринга, Маркова, Винера и некоторых других.

Слово «алгоритм» происходит от имени среднеазиатского учёного Абу Абдуллаха Мухаммеда ибн Муса аль-Хорезми. Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления [5].

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

Можно также привести пример алгоритма вычисления значения некоторой вещественной функции вещественной переменой в заданной точке. Например, пусть функция задана уравнением:

и необходимо вычислить значение данной функции в точке x=2.

Алгоритм выполнения таких вычислений может быть таким.

Вычислить значение функции в точке x=2. Для этого мы должны трижды умножить число 2 на само себя. Получаем значение 8.

Далее к полученному в пункте 1) значению мы должны прибавить число 3.
8+3=11;

В качестве ответа приводим полученное в предыдущем пункте значение. Записываем ответ y(3)=11.

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

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

Выполнение операции возведения числа x в куб (для этого число x трижды умножается на само себя) и прибавление к результату числа 3.

Вывод на экран результата вычислений в пункте 2.

Этот алгоритм обладает свойством массовости [12] (он позволяет вычислять значение функции y(x) в любой точке из множества вещественных значений). Для решения конкретной, более узкой задачи по вычислению значения данной функции в точке x=2 необходимо в пункте 1) алгоритма ввести в память компьютера число 2. Далее обсудим свойства алгоритмов.

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

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

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

Массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения не одной конкретной задачи, а целого класса подобных задач. Или, другими словами, один и тот же алгоритм можно использовать с разными исходными данными [4] .

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

Конечность – алгоритм в целом и любая его часть должны выполняться за конечное число шагов.

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

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

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

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

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

Любая часть приведенного алгоритма может быть выполнена за конечное число шагов, так как за конечное число шагов может быть выполнены соответствующие команды [3].

Формы описания алгоритмов

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

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

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

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

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

Например, конструкции псевдокода, используемые в статьях, как минимум могут зависеть от того языка (естественного) на котором они написаны. Обычно, в псевдокоде, для стандартных команд (начало алгоритма, конец алгоритма, условные операторы) используют слова естественного языка, на котором написана статья вообще. Хотя это является совсем необязательным. Одним из частых применений псевдокода является разработка алгоритма программы до кодирования (записи программы на конкретном языке программирования)[6].

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

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

Алгоритмические структуры

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

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

Если в алгоритме действия выполняются одно за другим, то такие алгоритмы называют линейным. Блок-схема таких алгоритмов представлена на рисунке 1.

Рисунок — Линейная алгоритмическая конструкция

Начало

Действие 1

...

Действие 2

Конец

Для того, чтобы иметь возможность выбора, какое действие выполнить в зависимости от некоторых условий используют ветвящиеся алгоритмы (или алгоритм с условием). Схема таких алгоритмов представлена на рисунке. Сначала происходит проверка условия. В случае, если условие выполняется. Происходит выполнение одной группы действий. В случае, если условие не происходит выполнение другой группы. Отметим, что обе ветви схемы в любом встречаются. Это означает, что линейная группа, помещенная сразу после точки соединения двух ветвей, будет выполнена в любом случае. Это необходимо учитывать при составлении алгоритмов [7].

Начало

Действие 1

…

Действие 2

условие

…