<<
>>

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

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

Алгоритм такого вычислительного процесса называется алго- ритмом разветвляющейся структуры. На рис. 7.4 приведены раз- личные варианты алгоритмов разветвляющейся структуры.

Рис. 7.4. Алгоритмы разветвляющейся структуры:

в г

— полное ветвление; 6 — неполное ветвление; в — полный выбор; г — непол- ный выбор

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

Такое утверждение может быть выражено как словами, так и формулой. Обычно различают два вида условий; простые и составные.

Простым условием называется выражение, составленное из двух арифметических выражений или двух текстовых величин, связан- ных одним из знаков; < (меньше), (боль- ше), >= (больше или равно), = (равно), о (не равно). Составные условия состоят из двух или более простых, связанных логически- ми операциями: И, ИЛИ, НЕ.

Например: х > 10 И х < 15; а > Ь ИЛИ с =5 ИЛИ у 0) и (Ь > 0) Только одно из чисел а, Ь положи- тельно ((а > 0) и (Ь = 1) и (х 0) и (у > 0)) или ((х> 0) и (у < 0)) Точка (х, у) принадлежит внешности единичного круга с центром в начале координат или его второй четверти (х*х + у*у>1) или((х*х +

+ у*у 0)) Целые числа а и Ь являются взаимно противоположными а--Ь Целые числа а и Ь являются взаимно обратными а*Ь= 1 Число а больше среднего арифмети- ческого положительных чисел Ь, с, d а > (Ь + с + (0/3 Хотя бы одна из логических перемен- ных Л и Л имеет значение «Да» Л или Л Обе логические переменные Л и Л имеют значение «Да» Л и Л Обе логические переменные Л и Л имеют значение «Нет» не Л и не Л Логическая переменная Л имеет зна- чение «Да», алогическая переменная Л имеет значение «Нет» Л и не Л Только одна из логических перемен- ных Л и Л имеет значение «Да» (Л и не Л) илн (Л и не Л)

например: F~ х > 10, тогда при х= 15F= true, а при х = 5F= false.

Логические переменные могут быть связаны логическими опера- циями И, ИЛИ, НЕ.

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

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

Z = х?/у, где у - sin (/lx) + 0,5.

Казалось бы, что решение этой задачи описывает алгоритм линейной структуры. Однако для удовлетворения свойства массо- вости и результативности алгоритма необходимо, чтобы при лю- бых исходных данных был получен результат или сообщение о том, что задача не может быть решена при заданных данных. Дей- ствительно, если у - 0, то задача не может быть решена, так как деление на нуль невозможно. Поэтому в алгоритме необходимо предусмотреть условие у = 0 и выдать в качестве результата ин- формацию «у = 0».

Таким образом, вычислительный процесс имеет две ветви. В од- ной ветви при у - 0 необходимо вычислить и вывести значение переменной z, в другой — вывести текст «у = 0». Такой вычисли- тельный процесс можно описать следующей условной формулой:

Схема алгоритма приведена на рис. 7.5, а.

Пример 2. Упорядочить три числа а, Ь, с по возрастанию таким образом, чтобы переменной а соответствовало самое маленькое число, Ь — среднее, с — самое большое.

Для решения данной задачи используем метод перестановок, при котором последовательно сравниваются значения перемен- ных а < Ь, затем а < с и далее Ь < с. Если первое условие а < Ь выполняется, то сразу осуществляется переход к следующему ус- ловию а < с, в противном случае сначала осуществляется переста- новка значений соответствующих переменных, а затем переход к следующему условию. Напомним, что в ПК каждая величина хра- нится в отдельной ячейке памяти, поэтому нельзя сделать пере- становку а = Ь; Ь = а, так как в этом случае в обоих переменных а и Ь окажется значение Ь. Для перестановки значений двух пере- менных а и Ь используется вспомогательная переменная Л.

Пере- становка осуществляется в следующей последовательности: Л = д, а - Ь, Ь = Л.

б

а — алгоритм решения задачи, представленной в примере 1; б — алгоритм реше- ния задачи, представленной в примере 2

Схема алгоритма представлена на рис. 7.5, б.

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

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

а Ь с
1 2 3
1 3 2
2 3 1
2 1 3
3 1 2
3 2 1

Проверьте самостоятельно, что при любом наборе исходных данных результат будет получен одинаковый: а=1,6 = 2,с=3,т.е. числа будут упорядочены по возрастанию.

7.2.1.

<< | >>
Источник: Калмыкова Е. А.. Информатика. 2012

Еще по теме Алгоритмы разветвляющейся структуры:

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. Алгоритм обработки результатов.
  8. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. СТРУКТУРА
  13. Замечания по структуре материала
  14. Структура