Алгоритмы циклической структуры

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

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

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

Простым условием (отношением) называется выражение, составленное из двух арифметических выражений или двух текстовых величин, связанных одним из знаков:> (больше), < (меньше), = (равно), <> (не равно), >= (больше или равно), <= (меньше или равно).

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

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

Условие выполняется?

Условие выполняется?

да нет да нет

Действие

Действие 2

Действие 1

Рис. 9.4. Примеры разветвления

Пример 9.3

Дано: квадратное уравнение a + b + c = 0

Найти: корни квадратного уравнения. Алгоритм решения задачи приведен на рис.9.5.

пуск

a,b,c

d=

d<0

да нет

останов

Рис. 9.5. Алгоритм нахождения корней квадратного уравнения

Отладка разветвляющихся алгоритмов

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

Пример № 5.4. процесса отладки разветвляющего алгоритма.

Дано: Х+А, если Х<10;

Y= Х+В, если 10;

Х+ 23<Х

пуск

Найти: Вычислить Y по одной из формул по составленному алгоритму, провести отладку алгоритма (рис.9.6.)

Х,А,В

Y:=Х+А

Х<10

Да

Y:=Х+В  

Х 23

Нет Да

Х+

Y

останов

Рис. 9.6. Алгоритм решения задачи (пример № 9.4.)

Отладка алгоритма

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

Таблица № 9.2. Данные для отладки алгоритма (пример № 9.4.)

Номер выбора	Х	А	В

б). Ручное решение. Решаем с помощью калькулятора и вносим в таблицу № 5.4.

в). Исполнение алгоритма.

Первый ввод данных: Х=5, А=2, В=3

1. Х<10? 5<10 - Да

2. Y=X+A=5+2=7

3. Вывод: Y=7

4.Останов

Второй ввод данных: Х=10, А=2, В=3

1. Х<10? 10<10 - Нет

2. Х<23? 10<23 - Да

3. Y=X+В=10+3=13

4. Вывод: Y=13

5. Останов

Третий ввод данных: Х=15, А=2, В=3

1. Х<10? 15<10 - Нет

2. Х<23? 15<23 - Да

3. Y=X+В=15+3=18

4. Вывод: Y=18

5. Останов

Четвертый и пятый вводы данных проделать самостоятельно!

г) сравнение результатов. Результаты решения задачи вручную и исполнения алгоритма совпали. Вывод: алгоритм верен!

Циклом называется повторение одних и тех же действий. Последовательность действий, которые повторяются в цикле, называют телом цикла. Существует несколько типов алгоритмов циклической структуры (рис.9.7; рис.9.8; рис.9.9, рис.9.10):

- алгоритм с предусловием (условие проверяется до тела цикла, проверяется условие продолжение цикла), рис.9.7;

- алгоритм с постусловием (условие проверяется после цикла, проверяется условие выхода из цикла), рис.9.8;

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

- условный циклический алгоритм с известным числом повторений, рис. 9.10.

усл-е

тело цикла

i=in

Тело цикла

i<=ik

i=in+di

тело цикла

i=in, ik, di

усл-е

тело цикла

Рис.9.7 Рис.9.8 Рис. 9.9 Рис. 9.10

Выполнение безусловного циклического алгоритма начинается с присвоения переменной I стартового значения in. Затем следует проверка, не превосходит ли переменная I конечное значение ik. Если превосходит, то цикл считается завершенным и управление передается следующему за телом цикла оператору. В противном случае выполняется тело цикла и переменная i меняет свое значение в соответствии с шагом di. Безусловный цикл можно заменить любым условным.

Пример 5.5.

Дано: Два натуральных числа А и В.

Найти: наибольший общий делитель этих чисел.

Для решения используем алгоритм Евклида. Большее из чисел уменьшаем на величину меньшего до тех пор, пока оба значения не станут равными (см. таблицу 9.3.).

Таблица 9.3.

Исходные данные	Первый шаг	Второй шаг	Третий шаг	НОД (А.В)=5
А=25	А=10	А=10	А=5
В=15	В=15	В=5	В=5

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

Отладка циклических алгоритмов

пуск

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

А=А-В

В=В-А

А, В

А<>В

А>В

А

останов

Рис. 9.11. Поиск наибольшего общего делителя двух чисел

Отладка циклических алгоритмов

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

Дата добавления: 2014-01-04