Главная

Windows Windows XP Windows 7

Word Word 2003 Word 2007

Excel Excel 2003 Excel 2007

Алгоритмы

Статистика Теория статистики Принцип Парето Диаграмма Парето

Цифровые системы управления

Рефераты

на предыдущую   на следующую

8.2. Разветвляющаяся структура

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

ПРИМЕР 2. Вычислить значение функции y по формуле

 .

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

Исходными данными задачи являются переменные а, х.

Результат задачи - переменная y.

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

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

Разработка алгоритма. Схема алгоритма решения задачи приведена на рис.6.

В блоке 3 проверка:

• если знаменатель равен ну-лю, то на экран выдается сообщение, что при заданных исходных данных функция не существует (блок 4), и решение задачи заканчивается (это одна ветка алгоритма);
• если знаменатель не равен нулю, вычисляем и печатаем значение функции y (блоки 6, 7, 8 - это вторая ветка алгоритма).

Рис. 6.

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

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

• при выборе исходных данных из одной и той же области определения ход выполнения алгоритма всегда один и тот же;
• при выборе исходных данных из разных областей определения ход выполнения алгоритма разный.

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

Выполним трассировку схемы (рис.6). Выберем два разных набора исходных данных:

а=1, х=1. Путь: блоки 1, 2, 3, 4, 5.

а=1, х=2. Путь: блоки 1, 2, 3, 6, 7, 8.

От значения переменной а путь прохождения схемы не зависит, поэтому мы взяли одно и то же число. Выбор разных значений переменной х привел к получению разных путей прохождения схемы. Если взять любое другое значение (например, х=3), то мы получим второй вариант пути. Итак, схема алгоритма имеет 2 разные ветки.

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

ПРИМЕР 3. Найти наибольшее из трех чисел.

Математическая постановки задачи. Введем математические обозначения величин: пусть А, В, С - заданные числа (это исходные данные задачи, их значения будем вводить), М - наибольшее (максимальное) из чисел А, В, С (это искомая величина, результат решения задачи, его значение будем печатать).

Выбор метода решения задачи.

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

Разработка алгоритма.

Схема алгоритма решения задачи приведена на рис.7.

В блоке 3 происходит сравнение чисел А и В. Если А окажется больше В, то управление передается по ветке "да" и в блоке 4 число А сравнивается с числом С.

Рис. 7.

Для полной трассировки схемы подберем 4 набора исходных данных, т.к. на схеме прослеживается 4 разных ветки. Проверим их:

А=1, В=2, С=3.    Путь: 1, 2, 3, 5, 7, 9, 10.
А=1, В=3, С=2.    Путь: 1, 2, 3, 5, 8, 9, 10.
А=2, В=1, С=3.    Путь: 1, 2, 3, 4, 7, 9, 10.
А=3, В=2, С=1.    Путь: 1, 2, 3, 4, 6, 9, 10.

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

Второй вариант. Как правило, любая задача имеет не один способ решения. Даже для этой, на первый взгляд, простой задачи можно предложить еще один вариант. Предположим, что первое число и есть максимальное (присвоим его значение числу М). Затем проверим, не окажется ли следующее число больше числа М. Если это так, то заменим значение М на это число. Такую же проверку проведем и для третьего числа.

Рис. 8

Разработка алгоритма.

Схема алгоритма решения задачи приведена на рис.8. В блоках  4, 5  происходит  возможное уточнение М по результату сравнения со вторым числом В. В блоках 6, 7 происходит возможное уточнение М по результату сравнения с третьим числом С.

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

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

на предыдущую   на следующую

Неизвестный Excel (эл.версия)

Клуб на Миллион в месяц (СТАРТ)