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

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

Первая задача: даны два числа, выбрать наибольшее из них.

Пусть исходными данными являются переменные А и В. Их значения будут задаваться вводом. Значение большего из них должно быть присвоено переменной С и выведено на экран компьютера. Например, если А=5, В=8, то должно получиться: С=8.

Блок-схема для этого алгоритма (с полным ветвлением):

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

Вот как будет выглядеть трассировка нашего алгоритма для исходных значений А=5, В=8.

Шаг	Операция	А	В	С	Проверка условия
1 2 3 4	Ввод А,В А>В С:=В Вывод С	5 5 5 5	8 8 8 8	- - 8 8	5>8, нет (ложь)

Эту же самую задачу можно решить , применяя структурную команду неполного ветвления.

Блок-схема такого алгоритма:

Теперь запишем рассмотренные алгоритмы на языках программирования:

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

2. В Алгоритмическом языке команда ветвления записывается следующим образом:

если <условие>

то <действие1>

иначе <действие2>

кв (конец ветвления)

3. В языке Паскаль имеется оператор ветвления. Другое его название – условный оператор.

Формат полного оператора ветвления следующий:

if <логическое выражение/условие> then <оператор1/действие1>

else <оператор2/действие2>

Здесь if – если, then – то, else – иначе.

4. Примеры программ с полным ветвлением:

↓Алгоритмический язык и Паскаль↓

алг БОЛЬШЕЕ

нач

вещ А, В, С

ввод А, В

если А>В

то С:=А

иначе С:=В

кв

вывод С

кон

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

< меньше

> больше

<= меньше или равно

>= больше или равно

= равно

<> не равно

Для неполного ветвления программы будут следующие:

алг БОЛЬШЕЕ1

нач

вещ А, В, С

ввод А, В

С:=А

если В>А

то С:=В

кв

вывод С

кон

Следующая задача: упорядочить значения двух переменных Х и Y по возрастанию.

Смысл этой задачи следующий: если для исходных значений переменных справедливо отношение X<=Y, то оставить их без изменения; если же X>Y, то выполнить обмен значениями.

Для обмена нужно использовать третью вспомогательную переменную.

Программы:

алг сортировка

нач

вещ X, Y, С

ввод X, Y

если X>Y

то С:=X

X:=Y

Y:=C

кв

вывод X, Y

кон

Этот пример иллюстрирует следующее правило Паскаля: если на какой-то из ветвей оператора ветвления находится несколько последовательных операторов, то их нужно записывать между служебными словами begin и end. Конструкция такого вида:

begin <последовательность операторов> end

называется составным оператором.

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

(Задания подобного типа попытайтесь решить сами, соответственно своему варианту).

ЛОГИЧЕСКИЕ ОПЕРАЦИИ

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

Program BIT3;

var А,Б,С,D: real;

begin

readln(А, В,С);

if (А>=В) and (А>=С) then D:=A;

if (В>=А) and (В>=C) then D:=B;

if (C>=A) and (C>=B) then D:=C;

writeln (D)

end.

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

Операция and называется логическим умножением или конъюнкцией. Ее результат — «истина», если значения обоих операндов — «истина». Очевидно, что если А >В и А > С, то А имеет наибольшее значение и т. д. В Паскале присутствуют все три основные логические операции:

and — И (конъюнкция),

or — ИЛИ (дизъюнкция),

not — НЕ (отрицание).

Сложные логические выражения

Обратите внимание на то, что отношения, связываемые логическими операциями, заключаются в скобки. Так надо делать всегда! Например, требуется определить, есть ли среди чисел А, В, С хотя бы одно отрицательное. Эту задачу решает следующий оператор ветвления:

if (А<0)or(В<0)or(С<0) then write( 'YES ') else write( 'NO ' );

Выражение, истинное для отрицательного числа, может быть записано еще и так:

not(А>=0).

Обратите внимание на то, что перед else символ «;» не ставится, так как этот символ является разделителем операторов!

Выполните задания под буквами «Г» и «Д» соответствующего варианта.