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

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

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

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

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

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

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

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

Задачи исследования:

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

- исследовать циклические конструкции в языках высокого уровня;

- подготовить литературный обзор источников по теме работы;

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

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

Предмет исследования - циклические конструкции и массивы данных.

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

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

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

ГЛАВА 1. АЛГОРИТМЫ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

1.1. Построение алгоритмов вычислительных процессов

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

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

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

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

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

Из определения алгоритма можно точно определить и его свойства (Рис 1.1).

Рисунок 1.1. – Свойства алгоритма^[5]

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

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

Имеем ряд чисел: . Необходимо определить сумму положительных чисел.

Задача довольно проста, достаточно выбрать положительные числа и суммировать их. Запишем алгоритм в обычном словесном виде (Рис 1.2)

Рисунок 1.2. – Запись алгоритма в словесном виде

Данный способ довольно громоздок и не дает наглядного представления о вычислительном процессе^[6].

Формульно-словесный способ – удобная форма записи алгоритма, поскольку в нем присутствуют математические символы и выражения с необходимыми словесными пояснениями (Рис 1.3)

Рисунок 1.3. – Запись алгоритма в формульно-словесном виде

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

Запишем рассматриваемый алгоритм в виде операторной схемы.

Пусть В – оператор ввода, который вводит данные в компьютер, А – арифметический оператор, предусматривающий выполнение арифметических операций; Р – логический оператор, предусматривающий проверку определенных условий; П – оператор печати результатов; Я – оператор завершения вычислительного процесса. Тогда алгоритм можно записать в виде последовательности операций (Рис 1.4.)

Рисунок 1.4. – Запись алгоритма в виде операторной схемы

Тут каждый оператор имеет свой порядковый номер в соответствии с последовательностью операций в алгоритме.

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

Рисунок 1.5. – Запись на алгоритмическом языке

Графический способ записи алгоритмов, по сравнению с вышеперечисленными способами имеет ряд преимуществ:

он наглядный: на схеме каждая операция отображается определенной геометрической фигурой, в середине которой записывается выполняемая операция;
вид геометрических фигур (символов, блоков), их размеры и выполняемые ими функции определены стандартом, что обеспечивает однозначную запись и схемы чтения алгоритма;
графическое изображение алгоритма дает возможность наглядно показать разветвления в решении задачи в зависимости от выполнения поставленного условия, отобразить многократное повторение отдельных этапов вычислений;
наглядность схемы, целостность ее восприятия, однозначность в отображении вычислительного процесса облегчают чтение алгоритма, проверку его правильности и внесение правок;
графическое отображение алгоритма упрощает написание программы для решения задачи на компьютере^[7].

На рисунке 1.6. показана блок-схема рассматриваемого нами алгоритма.

Рисунок 1.6. - Графическое отображение алгоритма

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

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

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

Такая структура алгоритма отображает вычисление простых арифметических выражений (Рис 1.7).

а) б) в)

Рисунок 1.7. – Алгоритмы линейной структуры^[9]

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

Рисунок 1.8. – Алгоритм разветвленной структуры

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

Рисунок 1.9. – Алгоритм циклической структуры

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

ГЛАВА 2. ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ АЛГОРИТМОВ ЦИКЛИЧЕСКОЙ СТРУКТУРЫ (НА ПРИМЕРЕ С++)

2.1. Общие понятия

Для программирования алгоритмов циклической структуры используют различные операторы цикла. Они обеспечивают повторное выполнение выражений. В языке С++ предусмотрено три вида таких операторов: for, while, do … while. Они отличаются между собой механизмами управления циклом и их размещением. В цикли for количество повторений задается заранее, а цикл управляется счетчиком и логическими выражениями, размещенными в начале цикла. Цикл while используется до тех пор, пока не будет выполнено логическое условие, сформулированное в начале цикла. Как противоположность ему, цикл do…while проверяет условие выхода из цикла в конце.

Набор операторов, которые повторно выполняются, создают тело цикла. В зависимости от местоположения условия выхода из цикла, циклы делятся на циклы с предварительной проверкой условий (for, while) и на циклы с последующей проверкой условия (do…while).