Основные структуры алгоритмов: сравнительный анализ

Содержание:

Введение

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

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

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

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

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

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

Объектом данной курсовой работы является структура алгоритмов и их особенности, а предметом алгоритмы и языки программирования,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Блок, характеризующий начало/конец алгоритма (для

Начало

Конец

подпрограмм - вызов/возврат):

<Действие>

Блок — процесс, предназначенный для описания

отдельных действий:

Блок — предопределенный процесс, предназначенный для обращения к вспомогательным алгоритмам (подпрограммам):

Блок — ввода/вывода с неопределенного носителя:

Блок - ввод с клавиатуры:

Блок — вывод на монитор:

Блок — вывод на печатающее устройство:

Блок — решение (проверка условия или условный блок):

Нет Да

<тело цикла>

Блок, описывающий цикл с параметром:

Блок — границы цикла, описывающий циклические

<тело цикла>

процессы типа: «цикл с предусловием», «цикл

с постусловием»:

Соединительные блоки:

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

Программа — описание структуры алгоритма на языке алгоритмического программирования.

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

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

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

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

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

Рис. 1.1 – Линейный алгоритм

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

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

Условие

Действие 2

Действие 1

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

Рис. 1.2. Полное ветвление

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

Условие

Действия

Истина (Да)

Ложь (Нет)

Рис. 1.3. Неполное ветвление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритмический язык Pascal

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

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

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

Компилятор Паскаля был написан на самом Паскале c использованием метода раскрутки.

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

Тем не менее, первоначально язык имел ряд ограничений: невозможность передачи функциям массивов переменной длины, отсутствие нормальных средств работы с динамической памятью, ограниченная библиотека ввода-вывода, отсутствие средств для подключения функций написанных на других языках, отсутствие средств раздельной компиляции и т. п. Подробный разбор недостатков языка Паскаль того времени был выполнен Брайаном Керниганом в статье «Почему Паскаль не является моим любимым языком программирования» (эта статья вышла в начале 1980-х, когда уже существовал язык Модула-2, потомок Паскаля, избавленный от большинства его пороков, а также более развитые диалекты Паскаля). Некоторые недостатки Паскаля были исправлены в ISO-стандарте 1982 года, в частности, в языке появились открытые массивы, давшие возможность использовать одни и те же процедуры для обработки одномерных массивов различных размеров.

Необходимо заметить, что многие недостатки языка не проявляются или даже становятся достоинствами при обучении программированию. Кроме того, по сравнению с основным языком программирования в академической среде 1970-х (которым был Фортран, обладавший гораздо более существенными недостатками), Паскаль представлял собой значительный шаг вперёд. В начале 1980-х годов в СССР для обучения школьников основам информатики и вычислительной техники академик А.П. Ершов разработал алголо-паскалеподобный «алгоритмический язык».

Наиболее известной реализацией Паскаля, обеспечившая широкое распространение и развитие языка, является Turbo Pascal фирмы Borland, выросшая затем в объектный Паскаль для DOS (начиная с версии 5.5) и Windows и далее в Delphi, в которой были внедрены значительные расширения языка.

Диалекты Паскаля, применяемые в Turbo Pascal для DOS и Delphi для Windows, стали популярны из-за отсутствия других успешных коммерческих реализаций.

Описание каждого элемента языка задается его синтаксисом и семантикой. Синтаксические определения устанавливают правила построения элементов языка. Семантика определяет смысл и правила использования тех элементов языка, для которых были даны синтаксические определения. Паскаль, в его первоначальном виде, представляет собою чисто процедурный язык и включает в себя множество алголоподобных структур и конструкций с зарезервированными словами наподобие if, then, else, while, for, и т. д. Тем не менее, Паскаль также содержит большое количество возможностей для структурирования информации и абстракций, которые отсутствуют в изначальном Алголе-60, такие как определение типов, записи, указатели, перечисления, и множества. Эти конструкции были частично унаследованы или инспирированы от языков Симула-67, Алгол-68, созданного Никлаусом ВиртомAlgolW и предложены Хоаром.

В современных диалектах (Free Pascal) доступны такие операции как перегрузка операторов и функций.

Электронные таблицы Excel

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

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

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

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

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

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

При выполнении задач к данной курсовой работе мы использовали следующие функции Microsoft Excel:

Создавали рабочую книгу .Так же как и в Word, каждая рабочая книга, созданная Excel, основывается на некоторой модели, называемой шаблоном. По умолчанию Excel основывает новую рабочую книгу на шаблоне с именем Книга. Шаблон сохраняет информацию о форматировании ячеек и рабочих листов, а также используемых панелях инструментов.

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

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

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

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

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

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

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

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

Система Mathcad

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

Mathcad 11, в отличие от большинства других современных математических приложений, построен в соответствии с принципом WYSIWYG ("What You See Is What You Get" — "что Вы видите, то и получите"). Поэтому он очень прост в использовании, в частности, из-за отсутствия необходимости сначала писать программу, реализующую те или иные математические расчеты, а потом запускать ее на исполнение. Вместо этого достаточно просто вводить математические выражения с помощью встроенного редактора формул, причем в виде, максимально приближенном к общепринятому, и тут же получать результат Кроме того, можно изготовить на принтере печатную копию документа или создать страницу в Интернете именно в том виде, который этот документ имеет на экране компьютера при работе с Mathcad Создатели Mathcad сделали все возможное, чтобы пользователь, не обладающий специальными знаниями в программировании (а таких большинство среди ученых и инженеров), мог в полной мере приобщиться к достижениям современной вычислительной науки и компьютерных технологий. Для эффективной работы с редактором Mathcad достаточно базовых навыков пользователя. С другой стороны, профессиональные программисты (к которым относит себя и автор этих строк) могут извлечь из Mathcad намного больше, создавая различные программные решения, существенно расширяющие возможности, непосредственно заложенные в Mathcad.

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

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

Со всеми этими (а также некоторыми другими) задачами с успехом справляется Mathcad:

• математические выражения и текст вводятся с помощью формульного редактора Mathcad, который по возможностям и простоте использования не уступает, к примеру, редактору формул, встроенному в Microsoft Word;
• математические расчеты производятся немедленно, в соответствии с введенными формулами;
• графики различных типов (по выбору пользователя) с богатыми возможностями форматирования вставляются непосредственно в документы;
• возможен ввод и вывод данных в файлы различных форматов;
• документы могут быть распечатаны непосредственно в Mathcad в том виде, который пользователь видит на экране компьютера, или сохранены в формате RTF для последующего редактирования в более мощных текстовых редакторах (например Microsoft Word);
• возможно полноценное сохранение документов Mathcad 11 в формате Web-страниц (генерация вспомогательных графических файлов происходит автоматически);
• имеется опция объединения разрабатываемых Вами документов в электронные книги, которые, с одной стороны, позволяют в удобном виде хранить математическую информацию, а с другой — являются полноценными Mathcad-программами, способными осуществлять расчеты;
• символьные вычисления позволяют осуществлять аналитические преобразования, а также мгновенно получать разнообразную справочную математическую информацию.

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

Глава 2. Классификация алгоритмов

Различают три типа базовых структур:

• Следование
• Развилка
• Цикл

Рис. 2.1. Структура следования

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

Структура Развилка обеспечивает выбор одной из двух альтернатив: если < условие 1 > то

< действие 1 >

иначе

< действие 2 >

все

Существует сокращенная форма структуры Развилка, которая позволяет выполнить действие или пропустить его:

если < условие > то < действие >

все

Обобщением структуры Развилка является Множественный выбор:

если Var = Const1 то < действие 1 >

если Var = Const2 то < действие 2 >

если Var = ConstN то < действие N >

все

В зависимости от значения переменной Var выполняется одно из указанных действий, например, если Var = Const3, то выполняется < действие 3 >.

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

• цикл «от до»
• цикл «пока»
• цикл «до»

Цикл «от до» управляет повторением выполнения действия с помощью переменной цикла:

цикл от I:= N1 до N2

< действие >

кц

Здесь I - переменная цикла, N1, N2 - начальное и конечное значения переменной цикла, вычисляются один раз при входе в цикл. Переменная цикла пробегает все следующие друг за другом в порядке возрастания значения от начального до конечного. Изменение значения переменной цикла происходит автоматически после каждого выполнения действия, указанного внутри цикла. В зависимости от соотношения N1 и N2 цикл может не выполниться ни разу (N1>N2) или выполниться (N2-N1+1) раз.

В цикле «пока» управление внутри цикла осуществляется с помощью логического условия:

цикл пока < условие>

< действие >

кц

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

Третий тип структуры цикл «до» имеет вид:

цикл

< действие > до < условие>

кц

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

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

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

• линейные
• разветвляющиеся
• циклические.

2.1 Линейная алгоритмическая структура. Типовые примеры

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

Покажем общую структуру линейного алгоритма в виде блок-схемы.

начало

Обработка данных

Ввод данных

Вывод результата

конец

Рис. 2.2. Блок схема

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

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

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

Операторы ввода данных:

• INPUT - оператор ввода данных с клавиатуры. Данные задаются в виде переменных. Переменная – это величина, значение которой может меняться в процессе выполнения программы. Для обозначения переменной используются их имена (идентификаторы) – последовательность до 40 латинских букв и цифр, начинающаяся с буквы. Данные могут быть следующих основных типов:
• целые INTEGER (Y%) – 2 байта в памяти (от -32768 до 32767),
• длинные целые LONG (Y&) – 4 байта (от -2³¹ до 2³¹-1),
• вещественные SINGLE (Y) – 6 знаков после , -4 байта (от -3.4Е+38 до 3.4Е+38),
• вещественные удвоенной точности DOUBLE (Y#) -16 знаков после ,– 8 байт (от -Е+308 до Е+308),
• символьные STRING (Y$) – последовательность символов до 32767 символов длиной.

Например: INPUT a,b или INPUT “Введите два числа”;a,b

• DATA, READ – операторы ввода данных из блока памяти. Например: DATA 3,4 : READ a,b

Оператор присваивания может быть использован как для ввода данных (Например: a=3 : b=4), так для вычисления выражений. (Например: S=a*b). Оператор присваивания вычисляет выражение, расположенное справа от символа присваивания (=) и результат присваивается переменной, расположенной слева от символа присваивания. При записи арифметического выражения используются арифметические операции и функции. Приоритет выполнения арифметических операций сохраняется. Функции можно использовать стандартные (встроенные) COS(X), SQR(X) … и задаваемые самим пользователем. (Например: Y=3*SQR(X)^2)

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

Например: PRINT S или PRINT “Площадь”;S или PRINT a,b,S

Для окончания программы используется оператор END. В начале программы можно использовать оператор очистки экрана – CLS.

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

CLS

INPUT “Введите две стороны прямоугольника”; a,b

S = a * b

PRINT “Площадь”; S

END

2.2. Разветвляющая алгоритмическая структура. Основные операторы циклов. Типовые примеры

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

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

начало

Ввод a,b,c

D=b*b-4*a*c

d>0

X₁=(-b+SQR(d))/(2*a)

Корней нет

Вывод Х₁, Х₂

конец

X₂=(-b-SQR(d))/(2*a)

да

нет

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

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

Для описания разветвляющегося алгоритма существуют операторы:

1. условный

блочной структуры:

IF условие THEN

блок действий 1

ELSE

блок действий 2

ENDIF

линейной структуры:

IF условие THEN блок 1 ELSE блок 2

Обе структуры могут быть использованы как в полной форме так и в усеченной – без блока ELSE.

При работе условного оператора сначала проверяется выполнение условия. Если условие выполняется (истинное), то реализуется блок 1, в противном случае – блок 2. Условие – это логическое выражение, использующее операции сравнения (=, <, > <=, >=, <>) и логические операции (AND, OR).

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

CLS : INPUT A,B,C : D=B^2-4*A*C

IF D>0 THEN

X1=(-b+SQR(d))/(2*a) : X2=(-b-SQR(d))/(2*a) : PRINT X1,X2

ELSE

PRINT ”Решенией нет”

ENDIF

1. выбора (выражением может быть список через запятую 1,3,4 диапазон значений 1 TO 9; операция сравнения IS >=).

SELECT CASE выражение

CASE условие 1

блок операторов 1

CASE условие 2

блок операторов 2

CASE ELSE

блок операторов n

END SELECT

CLS : INPUT A,B,C : D=B^4*A*C

SELECT CASE D

CASE IS >0

X1=(-b+SQR(d))/(2*a)

X2=(-b-SQR(d))/(2*a) : PRINT X1,X2

CASE ELSE

PRINT ”Решенией нет”

END SELECT

END

2.3 Циклические алгоритмические структуры. Основные операторы ветвления. Типовые примеры

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

Циклы бывают с определённым количеством, неопределённым числом вычислений.

I = I_Н , I_K , h

тело цикла

условие

тело цикла

тело цикла

условие

да

да

нет

нет

I – параметр цикла

I_Н – начальное значение параметра

I_K – конечное значение параметра

h – шаг изменения параметра (приращение)

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

Оператор цикла с параметром:

FOR I = I_Н TO I_K STEP h

тело цикла

NEXT I

Оператор цикла с предусловием:

DO WHILE условие продолжения вычислений (UNTIL условие прекращения вычислений)

тело цикла

LOOP

Оператор цикла с постусловием:

DO

тело цикла

LOOP WHILE условие продолжения вычислений (UNTIL условие прекращения вычислений)

Глава 3. Языки программирования

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

Язык программирования служит двум связанным между собой целям: он дает программисту аппарат для задания действий, которые должны быть выполнены, и формирует концепции, которыми пользуется программист, размышляя о том, что делать. Первой цели идеально отвечает язык, который настолько "близок к машине", что всеми основными машинными аспектами можно легко и просто оперировать достаточно очевидным для программиста образом. Второй цели идеально отвечает язык, который настолько «близок к решаемой задаче», чтобы концепции ее решения можно было выражать прямо и коротко.

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

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

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

Можно писать программы непосредственно на машинном языке, хотя это и сложно. На заре компьютеризации(в начале 1950-х г.г.), машинный язык был единственным языком, большего человек к тому времени не придумал. Для спасения программистов от сурового машинного языка программирования, были созданы языки высокого уровня (т.е. немашинные языки), которые стали своеобразным связующим мостом между человеком и машинным языком компьютера. Языки высокого уровня работают через трансляционные программы, которые вводят "исходный код" (гибрид английских слов и математических выражений, который считывает машина), и в конечном итоге заставляет компьютер выполнять соответствующие команды, которые даются на машинном языке. Существует два основных вида трансляторов:

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

3.1 Интерпретаторы

Одно, часто упоминаемое преимущество интерпретаторной реализации состоит в том, что она допускает "непосредственный режим". Непосредственный режим позволяет вам задавать компьютеру задачу вроде PRINT 3.14159*3/2.1 и возвращает вам ответ, как только вы нажмете клавишу ENTER (это позволяет использовать компьютер стоимостью 3000 долларов в качестве калькулятора стоимостью 10 долларов). Кроме того, интерпретаторы имеют специальные атрибуты, которые упрощают отладку. Можно, например, прервать обработку интерпретаторной программы, отобразить содержимое определенных переменных, бегло просмотреть программу, а затем продолжить исполнение.

Больше всего программистам нравится в интерпретаторах возможность получения быстрого ответа. Здесь нет необходимости в компилировании, так как интерпретатор всегда готов для вмешательства в вашу программу. Введите RUN и результат вашего самого последнего изменения оказывается на экране.

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

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

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

3.2 Компиляторы

Компилятор-это транслятор текста на машинный язык, который считывает исходный текст. Он оценивает его в соответствии с синтаксической конструкцией языка и переводит на машинный язык. Другими словами, компилятор не исполняет программы, он их строит. Интерпретаторы невозможно отделить от программ, которые ими прогоняются, компиляторы делают свое дело и уходят со сцены. При работе с компилирующим языком, таким как Турбо-Бейсик, вы придете к необходимости мыслить о ваших программах в признаках двух главных фаз их жизни: периода компилирования и периода прогона. Большинство программ будут прогоняться в четыре - десять раз быстрее их интерпретаторных эквивалентов. Если вы поработаете над улучшением, то сможете достичь 100-кратного повышения быстродействия. Оборотная сторона монеты состоит в том, что программы, расходующие большую часть времени на возню с файлами на дисках или ожидание ввода, не смогут продемонстрировать какое-то впечатляющее увеличение скорости.

3.3. Эволюция и классификация языков программирования

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

- высокое качество создаваемых программ (компактность и скорость выполнения);

- возможность использования конкретных аппаратных ресурсов;

- предсказуемость объектного кода и заказов памяти;

- для составления эффективных программ необходимо знать систему команд и особенности функционирования данной ЭВМ;

- трудоемкость процесса составления программ ( особенно на машинных языках и ЯСК), плохо защищенного от появления ошибок;

- низкая скорость программирования;

- невозможность непосредственного использования программ, составленных на этих языках, на ЭВМ других типов.

Машинно-ориентированные языки по степени автоматического программирования подразделяются на классы.

Машинный язык. Отдельный компьютер имеет свой определенный Машинный язык (далее МЯ), ему предписывают выполнение указываемых операций над определяемыми ими операндами, поэтому МЯ является командным. Однако, некоторые семейства ЭВМ (например, ЕС ЭВМ, IBM/370/ и др.) имеют единый МЯ для ЭВМ разной мощности. В команде любого из них сообщается информация о местонахождении операндов и типе выполняемой операции.

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

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

Использование символических адресов – первый шаг к созданию ЯСК. Команды ЭВМ вместо истинных (физических) адресов содержат символические адреса. По результатам составленной программы определяется требуемое количество ячеек для хранения исходных промежуточных и результирующих значений. Назначение адресов, выполняемое отдельно от составления программы в символических адресах, может проводиться менее квалифицированным программистом или специальной программой, что в значительной степени облегчает труд программиста.

Автокоды. Есть также языки, включающие в себя все возможности ЯСК, посредством расширенного введения макрокоманд - они называются Автокоды.

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

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

Обе указанных системы используют трансляторы с ЯСК и набор макрокоманд, которые также являются операторами автокода.

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

Макрос. Язык, являющийся средством для замены последовательности символов описывающих выполнение требуемых действий ЭВМ на более сжатую форму - называется Макрос (средство замены).

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

Макрос одинаково может работать, как с программами, так и с данными.

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

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

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

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

Проблемных языков очень много, например:

Фортран, Алгол – языки, созданные для решения математических задач;

Simula, Слэнг - для моделирования;

Лисп, Снобол – для работы со списочными структурами.

Универсальные языки. Универсальные языки были созданы для широкого круга задач: коммерческих, научных, моделирования и т.д. Первый универсальный язык был разработан фирмой IBM, ставший в последовательности языков Пл/1. Второй по мощности универсальный язык называется Алгол-68. Он позволяет работать с символами, разрядами, числами с фиксированной и плавающей запятой. Пл/1 имеет развитую систему операторов для управления форматами, для работы с полями переменной длины, с данными организованными в сложные структуры, и для эффективного использования каналов связи. Язык учитывает включенные во многие машины возможности прерывания и имеет соответствующие операторы. Предусмотрена возможность параллельного выполнение участков программ.

Программы в Пл/1 компилируются с помощью автоматических процедур. Язык использует многие свойства Фортрана, Алгола, Кобола. Однако он допускает не только динамическое, но и управляемое и статистическое распределения памяти.

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

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

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

Одним из примеров диалоговых языков является Бэйсик. Бэйсик использует обозначения подобные обычным математическим выражениям. Многие операторы являются упрощенными вариантами операторов языка Фортран. Поэтому этот язык позволяет решать достаточно широкий круг задач.

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

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

Табличные методы легко осваиваются специалистами любых профессий.

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

Заключение

Изобретение языка программирования высшего уровня позволило нам общаться с машиной, понимать её (если конечно Вам знаком используемый язык), как понимает американец немного знакомый с русским языком древнюю азбуку Кириллицы. Проще говоря, мы в нашем развитии науки программирования пока что с ЭВМ на ВЫ. Но если мы обратим внимание на темпы роста и развития новейших технологий в области программирования, то можно предположить, что в ближайшем будущем, человеческие познания в этой сфере, помогут произвести на свет языки, умеющие принимать, обрабатывать и передавать информации в виде мысли, слова, звука или жеста. Так и хочется назвать это детище компьютеризированного будущего: «языки программирования "высочайшего" уровня». Возможно, концепция решения этого вопроса проста, а ближайшее будущее этого проекта уже не за горами.

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

Единственный способ изучать новый язык программирования – писать на нём программы.

Список литературы

1. Белов П.М. Основы алгоритмизации в информационных системах: Учебн. Пособие.- Спб.: СЗТУ, 2003. – 85с. Режим доступа: http://www.ict.edu.ru/ft/005406/nwpi225.pdf
2. Гудман, С. Введение в разработку и анализ алгоритмов / С. Гудман, С. Хидетние-ми-М.: Мир, 1981.-366 с.
3. Красиков, И.В. Алгоритмы. Просто как дважды два / И.В.Красиков, И.Е. Красико-ва,- 2-е изд.- М.: Эксмо, 2007 — 256 с.
4. Левитин А.В. Алгоритмы: введение в разработку и анализ. – М.: Издательский дом «Вильямс», 2006. – 576 с.
5. Макаров В.Л. Программирование и основы алгоритмизации.: учебн. пособие.-Спб., СЗТУ, 2003, - 110с. Режим доступа: http://window.edu.ru/resource/126/25126/files/nwpi223.pdf
6. Макконнелл Дж. Основы современных алгоритмов. 2-е изд., доп. – М.: Техносфера, 2004. – 368 с.
7. Основы алгоритмизации и программирования: учеб. пособие / Т.А. Жданова, Ю.С. Бузыкова. – Хабаровск : Изд-во Тихоокеан. гос.ун-та, 2011. –56 с. Режим доступа: http://pnu.edu.ru/media/filer_public/2013/02/25/book_basics.pdf.
8. Основы алгоритмизации и программирования : учебное пособие / Г.Р. Кадырова. – Ульяновск : УлГТУ, 2014. – 95 с. . Режим доступа: http://venec.ulstu.ru/lib/disk/2014/137.pdf
9. Основы алгоритмизации и программирования. Курс лекций. Режим доступа: http://lib.ssga.ru/fulltext/UMK/исходные%20для%20Кацко/заменить%20полностью/Информатика/лекции/13%20Основы%20алгоритмизации%20и%20программирования.pdf
10. Основы алгоритмизации и программирования: Метод. указ. / Сост.: И.П. Рак, А.В. Терехов, А.В. Селезнев. Тамбов: Изд-во Тамб. гос. техн. ун-та. Режим доступа: http://www.ict.edu.ru/ft/004758/terehov.pdf.
11. Программирование и основы алгоритмизации: Для инженерных специальностей технических университетов и вузов. /А.Г. Аузяк, Ю.А. Богомолов, А.И. Маликов, Б.А. Старостин. Казань: Изд-во Казанского национального исследовательского технического ун-та - КАИ, 2013, 153 с. Режим доступа: http://au.kai.ru/documents/Auzyak_Progr_osn_alg_C_2013.pdf.