Файл: Разветвляющийся алгоритм С++.pdf

ВВЕДЕНИЕ

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

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

Для осуществления обозначенной цели служат следующие задачи:

1. Изучение понятий алгоритмизации;
2. Получение знаний об основах реализации алгоритмов в программирование.
3. Получение знаний об основных типах данных языка С++
4. Получение знаний об основных арифметических и логических операторах языка С++
5. Изучение способов реализации разветвляющихся алгоритмов в языке C++.
6. Получение навыков по применению разветвляющихся алгоритмов на практике.

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

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

1. АЛГОРИТМЫ

Определение понятия алгоритм. Свойства алгоритмов. Формы записи алгоритмов.

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

Название "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783—850 гг. В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними "столбиком", знакомые теперь каждому школьнику. В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.

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

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

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

2. ОСНОВНЫЕ СВОЙСТВА АЛГОРИТМОВ

Основными свойствами алгоритмов являются:

1. Дискретность:

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

1. Определенность (детерминированность):

каждый шаг алгоритма должен однозначно определять действие;

1. Конечность (результативность):

- конечное число шагов должно приводить к решению задачи;

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

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

результатов;

1. Массовость:

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

1. Корректность (правильность):

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

3. ОБЩИЕ ПРИНЦИПЫ РАЗРАБОТКИ АЛГОРИТМОВ

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

1) линейный (последовательный) алгоритм, который

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

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

заданного условия;

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

действий; совокупность действий, образующих тело цикла, может

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

Существуют два типа циклов:

1) цикл с параметром (со счетчиком, арифметический цикл) – это цикл, как правило, с заранее известным количеством повторений тела цикла; условие выполнения цикла проверяется до исполнения его тела (если условие истинно, цикл работает, иначе – завершается), поэтому цикл с параметром относится к циклам с предусловием;

2) итерационный цикл – цикл с заранее не известным количеством повторений тела цикла; число повторений определяется условием выполнения или завершения цикла; если условие проверяется до тела цикла, то такой цикл будет с предусловием, если условие проверяется после тела цикла, то с постусловием.

4. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ

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

1. Словесный способ – описание на естественном языке – доступная форма представления алгоритма, ориентированного на выполнение независимо от его подготовки. В данном пособии словесный способ используется в качестве описательного алгоритма.
2. Графический способ в виде структурных схем (блок-схем) требует знаний правил построения графических символов, поэтому необходимо ознакомиться со стандартами графических изображений блоков алгоритмов.
3. Способ описания алгоритмов на псевдокоде (алгоритмическом языке) использует служебные слова и специальные правила записи отдельных действий; в псевдокоде приняты жесткие синтаксические правила записи команд, что стандартизирует и облегчает запись алгоритма на стадии его проектирования, а также дает возможность расширения системы команд,

рассчитанных на абстрактного исполнителя.

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

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

Наибольшее распространение благодаря наглядности получил графический способ описания алгоритмов.

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

Виды графических символов для построения блок-схемы алгоритма:

- начальный символ (терминатор – пуск): не имеет входа и имеет только один выход;

- конечный символ (терминатор – останов): не имеет выхода и имеет только один вход;

- вычислительный символ (процесс): имеет один вход и один выход;

- условный символ (решение): имеет один вход и два выхода, которые можно обозначать «+» («1», «да», «true») и «–» («0»,«нет», «false»);

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

ГОСТ 19.701-90(ИСО 5807-85) ЕСПД (Единая система программной документации) предусматривает основные символы схем алгоритмов.

1. Терминатор (пуск-останов): начальный символ отображает начало алгоритма, конечный – его конец (рис. 1).

Рис. 1

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

Рис.2

1. Решение: условный символ или символ выбора (переключатель), имеющий один вход и, в случае условного символа, два альтернативных выхода («+», если условие истинно, и «–», если ложно) или, в случае символа выбора, несколько альтернативных выходов («+», если есть равное значение из перечисленных заданному, и «–», если нет), один из которых может быть активизирован (рис. 3).

Рис.3

1. Граница цикла: единый блок для обозначения различных циклов – символ, отображающий начало и конец цикла; условия для инициализации, приращения, завершения или продолжения цикла помещается внутри символа в начале или в конце в зависимости от расположения операции, проверяющей условие(рис. 4).

Рис.4

1. Подготовка: символ отображает модификацию (изменение) команды или группы команд; в данном пособии используется как символ отображения структуры цикл с параметром (рис. 5).

Рис.5

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

Рис. 6

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

Рис. 7

1. Данные: символ отображает данные, носитель которых не определен; (рис. 8).

Рис.8

1. Соединитель: символ прерывания блок-схемы отображает указание связи между прерванными линиями потока, связывающими символы; соответствующие символы-соединители должны содержать одно и то же уникальное обозначение (рис. 9).

Рис.9

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

Рис.10

5. РАЗВЕТВЛЯЮЩИЙСЯ АЛГОРИТМ С++

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

5.1. РЕАЛИЗАЦИЯ АЛГОРИТМОВ НА ЯЗЫКАХ ПРОГРАММИРОВАНИЯ

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