Разветвляющиеся алгоритмы (развилка)

Конспект лекций по информатике и программированию

для специальности 3514

Автор доц., к.т.н. Каширская Е.Н.

 

Москва, 2001

Часть 3. ОРГАНИЗАЦИЯ ДАННЫХ В ЭВМ И ОСНОВЫПРОГРАММИРОВАНИЯ

ВВЕДЕНИЕ В ПРОГРАММИРОВАНИЕ

1.1. Основные этапы решения задач на ЭВМ:

· постановка задачи;

· построение математических моделей;

· разработка методики решения задач;

· разработка алгоритма решения задачи;

· составление программы по разработанному алгоритму;

· ввод программы в ЭВМ;

· отладка программы (поиск и исправление ошибок);

· проведение расчетов по программе;

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

· анализ результатов.

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

Само слово «алгоритм» означает правило выполнения арифметических действий с использованием арабских цифр.

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

Слово «алгоритм» происходит от латинской формы написания имени математика IX века Аль-Хорезми, автор учебника арифметики, который сформулировал правила выполнения арифметических действий.

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

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

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

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

Пять характеристик алгоритмов:

1) вход алгоритма;

2) выход алгоритма;

3) определенность шагов алгоритма;

4) выполнимость шагов;

5) конечность.

Пример невыполнимого шага: присвоить Х значение, равное наибольшему вещественному числу, меньшему 1.

Это невозможно сделать, какое бы значение для Х мы не выбрали, всегда можно составить большее, добавив к десятичной части числа любую цифру: 0,999→0,9994 и т.д.

Пример. Алгоритм сложения столбиком: 315

⁺ 48

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

Шаг 1. Ввод – любых двух слагаемых (из класса объектов, к которым применим алгоритм).

Шаг 2. Сложить цифры, стоящие в разрядах единиц; единицы полученного результата записать в разряд единиц суммы.

Шаг 3. Сложить цифры, стоящие в разрядах десятков и прибавить к ним единицу, если результат шага 2 не меньше десяти.

Шаг 4. То же для разряда сотен и т.д., пока не закончатся разряды слагаемых.

Шаг N. Вывод – значение суммы.

Схемы алгоритмов

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

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

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

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

Параллелограмм (блок ввода-вывода) содержит информацию о входных и выходных данных.

Овал означает начало или окончание вычислительного процесса.

Блок сравнения, в отличие от остальных, имеет 2 выхода – “да” и “нет”. Если условие, записанное внутри блока, выполняется, выход из него происходит по стрелке “да”, в противном случае – по стрелке “нет”.

Наиболее часто употребляемые символы схем алгоритмов

 

 

 

 

Ручное управление

 

 

Магнитный диск

 

 

 

 

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

Ниже приведены графические обозначения (обозначения на блок-схемах) ОАС.

Структура Полная развилка Неполная

“следование” развилка

 

Цикл с предусловие Цикл с постусловием Цикл с параметром

(цикл ПОКА) (цикл ДО)

 

На схемах СЕРИЯ обозначает один или несколько любых операторов; УСЛОВИЕ есть логическое выражение (ЛВ) (если его значение ИСТИНА, переход происходит по ветви ДА, иначе — по НЕТ). На схеме цикла с параметром использованы обозначения: ПЦ — параметр цикла, НЗ — начальное значение параметра цикла, КЗ — конечное значение параметра цикла, Ш — шаг изменения параметра цикла.

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

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

Линейные алгоритмы

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

 

Общий вид линейного участка:

Пример 1. Пешеход шел по пересеченной местности. Его скорость движения по равнине v1 км/ч, в гору — v2 км/ч и под гору — v3 км/ч. Время движения соответственно t1, t2 и t3 ч. Какой путь прошел пешеход?

1. Ввести v1, v2, v3, t1, t2, t3. 2. S1:= v1 * t1. 3. S2:= v2 * t2. 4. S3:= v3 * t3. 5. S:= S1 + S2 + S3. 6. Вывести значение S. 7. Конец.

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

Пример 2. Дано натуральное трехзначное число n, в записи которого нет нулей. Составить алгоритм, который возвращает значение ИСТИНА, если верно утверждение: "число n кратно каждой своей цифре", и ЛОЖЬ — в противном случае.

1. Ввести число n 2. A:= n mod 10 {разряд единиц} 3. B:= n div 100 {разряд сотен} 4. C:= n div 10 mod 10 {десятки} 5. L:= (n mod A=0) and (n mod B=0) and (n mod C=0) 6. Вывод L 7. Конец

На приведенной выше схеме DIV и MOD соответственно операции деления нацело и получения остатка от целочисленного деления. В фигурных скобках записаны пояснения (комментарии) к операторам.

Разветвляющиеся алгоритмы (развилка)

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

Общая структура ветвления:

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

Пример 1. Вычислить значение функции

1. Ввести x. 2. Если x£–12, то y:=–x2 3. Если x<0, то y:=x4 4. y:= x–2 5. Вывести y 6. Конец

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

Пример 2. Дано натуральное число n. Если число нечётное и его удвоение не приведет к выходу за 32767 (двухбайтовое целое число со знаком), удвоить его, иначе — оставить без изменения.

Чтобы удовлетворить условию удвоения, число n должно быть нечетным и меньше 16384.

1. Ввести число n 2. Если число n нечетное и меньше 16384, то n:= n * 2 3. Вывод n 4. Конец

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