Файл: Особенности и примеры использования массивов при разработке программ.pdf

Введение

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

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

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

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

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

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

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

В соответствии к цели работы поставлены такие основные задания:

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

– проанализировать использование циклических алгоритмов в С++;

– рассмотреть особенности обработки массивов;

– привести примеры базовых алгоритмов для обработки одномерных массивов;

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

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

Основные понятия о циклических алгоритмах

1.1. Алгоритмы, их свойства

В повседневной деятельности постоянно приходится сталкиваться с разными правилами, которые описывают последовательность действий с целью достичь определенного необходимого результата. Данные правила являются многочисленными. Например, мы придерживаемся определенных правил, чтобы позвонить, приготовить лекарство, сварить суп или вычислить какое-то математическое уравнение. Указанные примеры можно объединить понятием «алгоритм». [2]

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

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

Алгоритм является фундаментальным понятием программирования. Ученые выделяют три основных класса алгоритмов: вычислительные, информационные и управляющие [3].

Вычислительные алгоритмы – это алгоритмы, которые работают со сравнительно простыми типами данных, например числами, векторами, матрицами.

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

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

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

Любой алгоритм обладает следующими свойствами:

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

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

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

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

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

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

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

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

Формульно-словесный метод записи алгоритма основывается на инструкциях о выполнении конкретных действий в определенной последовательности с использованием математических символов и выражений пояснениями на естественном языке.[10]

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

Рассмотрим основные геометрические фигуры, применимые в блок-схемах (таблица 1)

Таблица 1.

Основные геометрические фигуры, применимые в блок-схемах

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

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

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

1.2. Базовые структуры алгоритмов. Циклические структуры алгоритмов

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

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

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

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

Действие 1

Действие 2

Действие n

…

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

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

Алгоритм, который осуществляет выполнение тех или иных действий в зависимости от результата проверки условия, называется алгоритмом с разветвлением или разветвляющимся (рисунок 2):[8]

Условие

Действие 1

Действие 2

Да

Нет

Рисунок 2 –Структура разветвляющегося алгоритма

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

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

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

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

Различают две основные разновидности циклов: циклы с предусловием (рисунок 3) и циклы с постусловием (рисунок 4).

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