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

Алгоритмы с ветвлением

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

С точки зрения алгоритмических конструкций может быть полное и неполное ветвление. Условный оператор также может быть полным и неполным.

Алгоритмическая конструкция

Вид условного оператора в Pascal

if <условие> then <оператор 1>;

if <условие> then else <оператор 1>;

if not <условие> then <оператор 1>;

if <условие> then <оператор 1>

else <оператор2>;

if <условие> then

begin

<оператор 1>;

<оператор 2>;

<оператор 3>;

end

else

begin

<оператор 4>;

<оператор 5>;

end;

Условие - это переменная или выражение логического типа. Иногда его называют условным выражением или логическим выражением. Оно может включать в себя переменные, константы, арифметические выражения, связанные между собой операциями отношений и логическими операциями.

Примеры записи условий на языке Pascal:

Условие

Запись на Pascal

x ≠ y

x < > y

5 < x ≤ 20

(x > 5) and (x <= 20)

x > y и x - четное

(x > y) and (x mod 2 = 0)

x  (-∞; 5]  [20; ∞) иначе x 5 или x  20

(x <= 5) or (x >= 20)

x  (-5; 0)  (10; 20)

(x > -5) and (x < 0) or (x > 10) and (x < 20)

x кратно 3 и 5

(x mod 3 = 0) and (x mod 5 = 0)

Основные правила использования условного оператора в Pascal:

• после слов then и else может стоять только один оператор (простой или составной);

• перед словом else точка с запятой не ставится;

• если используются логические операции (not, and, or, xor), то входящие в условие операции отношения заключаются в круглые скобки.

Продемонстрируем особенности программирования алгоритмов с ветвлением на примере решения квадратного уравнения.

Постановка задачи. Решить уравнение ax² + bx + c = 0 для произвольных значений a, b, c.

Для алгоритмизации выберем метод решения с помощью дискриминанта (d). В этом случае у алгоритма будут следующие параметры:

• исходными данными являются коэффициенты а, b, c. Их возможные значения - множество действительных чисел, но коэффициент а при х² не должен равняться нулю;

• совокупность возможных результатов: сообщение, что алгоритм неприменим (если а = 0), один корень (если d = 0), два корня (если d > 0) или сообщение, что решения нет (если d < 0);

• промежуточным результатом является значение дискриминанта;

• правило начала заключается во вводе значений коэффициентов уравнения и проверке, что a  0;

• правила непосредственной обработки данных - соответствующие формулы математики;

• правило окончания - получение одного из возможных результатов;

• правило извлечения (сообщения) результата - вывод полученного результата на экран (можно вывести его в файл или использовать для решения другой задачи).

Блок-схема алгоритма решения квадратного уравнения показана на рисунке 83.

Программа решения квадратного уравнения на языке Pascal:

var a, b, c, d, x1, x2: real;

begin

write('Введите значения коэффициентов a, b, c:'); readln(a, b, c);

if a = 0 then writeln('Для а = 0 применение алгоритма невозможно')

else

begin

d := b*b - 4*a*c;

if d < 0 then writeln('Решения нет')

else

if d = 0 then

begin

x1 := -b/2/a;

writeln('x = ', x1:6:2);

end

else

begin

x1 := (-b + sqrt(d))/2/a;

x2 := (-b - sqrt(d))/2/a;

writeln ('x1 =', x1, 'x2 =', x2);

end;

end;

end.

Замечание

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

if d < 0 then writeln('Решения нет')

if d = 0 then

begin

x1 := -b/2/a;

writeln('x =', x1:6:2);

end;

if d > 0 then

begin

x1 := (-b + sqrt(d))/2/a; x2:= (-b - sqrt(d))/2/a;

writeln('x1 =', x1, 'x2 =', x2);

end;

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

Блок-схема

Формат оператора

Case x of

a: <оператор 1>;

b..c: <оператор 2>;

d, e: <оператор 3>

else

<оператор 4>;

end;

Продемонстрируем применение оператора выбора на примере перевода римских цифр в десятичные числа.

Постановка задачи. От пользователя вводится символ, если это римская цифра, то вывести на экран ее десятичный эквивалент, иначе сообщить, что это не цифра.

Программа:

var r: char; a: integer;

begin

write('Введите римскую цифру:'); readln(r); a := 0;

case r of

′i': a := 1;

'v': a := 5;

'x': a := 10;

′l': a := 50;

'c': a := 100;

'd': a := 500;

'm': a := 1000

else write(r, ′- это не римская цифра′);

end;

if A < > 0 then write(r, ′- это римская цифра. Соответствует числу′ , a);

end.

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

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

Формат неполного условного оператора:

if <условие> then <оператор>;

Формат полного условного оператора:

if <условие> then <оператор 1> else <оператор 2>;

Условие - переменная или выражение логического типа.

Оператором может быть любой допустимый в ЯП оператор, простой или составной.

Правила:

• перед else точка с запятой не ставится;

• если в условии есть логические операции (not, and, or, xor), то операции отношения заключаются в круглые скобки;

• после then и else может стоять только один оператор (простой или составной).

Формат оператора выбора:

case x of

<значение 1>: <оператор 1>;

<значение 2> .. <значение 3>: <оператор>;

<значение 4>, <значение 5>: <оператор 3>

else <оператор 4>;

end;

Правила:

• выражение-селектор может быть только дискретного типа;

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

• перед else точка с запятой не ставится.

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

Блок-схема

Описание

1.

а) Команда ветвления в сокращенной форме, в которую вложена команда ветвления в полной форме.

2.

б) Команда ветвления в полной форме, в которую вложена команда ветвления в сокращенной форме.

3.

в) Две команды ветвления в полной форме, одна из которых вложена в другую.

Задание 2. Найдите синтаксические и логические ошибки в программах.

a)

var x, y, z: integer;

begin

write(′Введите х и у: ′); readln(x, y);

if x > 0 and x < y then z := sqrt(x);

else z := (x + y)/2;

end.

б)

var x, y: real;

begin;

write(′Введите х и у: ′); readln(y, x);

if x > y then write(′больше′) else write(′меньше′)

if x = y then write(′равные′)

write(′Сумма =′, x = y);

end.

Задание 3. Запишите фрагменты алгоритмов, данных блок-схемами (рис. 84), на языке программирования.

Задание 4. Составьте блок-схемы, соответствующие фрагментам программ.

а)

if x mod 7 = 0 then write(′воскресенье′)

else if x mod 7 = 6 then write(′суббота′)

else write(′рабочий день′);

б)

if x + y > z then

begin

z := x + y; write(z);

end

else if x > y then z := 0; x := x + 1;

в)

w := x mod 7;

case w of

1..5: write(′рабочий день′);

6: write(′суббота′);

0: write(′воскресенье′);

end;

Работа в среде программирования. Знакомство с операторами ветвления

1

Введите и отладьте программы, приведенные в параграфе.

2

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

Задача 1. Считается, что вес, рост и возраст человека должны находиться в соотношении Вес ≈ Рост - 110 + 0,1 * Возраст.

Знак «≈» означает, что допустимы отклонения в 5 - 7 % от точного результата. Определите, ваш вес меньше нормы, в норме или выше нормы.

Задача 2. Известны оценки ученика по трем контрольным. Определите и выведите на экран, как можно назвать ученика: отличник (все три пятерки), двоечник (хотя бы одна двойка), троечник (двоек нет, но хотя бы одна тройка) или хорошист. Вычислите средний балл, полученный учеником.

Задача 3. От пользователя вводится номер месяца. Нужно вывести на экран название времени года (например, для 4 это будет «весна»).

Задача 4. От пользователя вводится какой-либо год ХХ в. Определите, мирным ли был этот год для России, а если нет, то какая война была в этом году.

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

§ 31. Примеры программирования алгоритмов с ветвлением

Задача 1. Для заданного х вычислите значение функции

Блок-схема этой задачи показана на рисунке 85.

Составьте программу можно разными способами.

1-й способ.

var x, y: real;

begin

write(′Введи х:′); readln(x);

if x >= 2 then y := sqrt(x - 2) else y := sqr(x) - 4;

write(′y =′, y);

end.

2-й способ.

Полный условный оператор можно заменить двумя неполными:

if x >= 2 then y := sqrt(x - 2);

if x < 2 then y := sqr(x) - 4;

Замечание

При решении задачи этим способом следует заботиться о том, чтобы условия в условных операторах были противоречащими друг другу (чтобы не осталось «неохваченных вниманием» значений переменной).

3-й способ.

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

true: y := sqrt(x - 2);

false: y := sqr(x) - 4;

end;

Задача 2. Для заданного целого х вычислите значение функции

.

Так как нет никаких условий, то кажется, что это обычная вычислительная задача. На самом деле, поскольку нельзя делить на ноль и нельзя вычислить квадратный корень из отрицательного числа, областью определения данной функции является множество Х = [2; 3) U (3; +). Значение функции y можно вычислить, если х  Х, в противном случае функция не определена.

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

var x: integer;

y: real;

begin

x := random(40) - 20;

write(′Для x =′, x);

if (x >= 2) and (x <> 3) then

begin

y = sqrt(x - 2)/(x*x*x - 27);

writeln(′y =′, y:6:2);

end

else writeln(′Значение функции не определено′);

end.

Блок-схема решения задачи показана на рисунке 86.

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

Обозначения:

name - имя - строка символов;

s- первая буква имени - символ;

Основной вопрос при решении данной задачи: как определить, является ли буква гласной? Можно, конечно, написать сложное условие типа (s = ′А′) or (s = ′Е′) or... (s = ′Я′), но в языке Pascal есть возможность работать с множествами и существует операция проверки вхождения элемента в множество - in.

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

Вот один из способов решения задачи:

var name: string;

s: char;

begin

write(′Как вас зовут?′); readln(name);

s := name[1]; {что равнозначно оператору s := copy(name, 1, 1);}

write(′Первая буква′);

if s in[′A′,′a′,′E′,′e′,′Ё′,′ё′,′И′,′и′,′О′,′о′,′У′,′у′,′Э′,′э′,′Ю′,′ю′,′Я′,′я′]

then write(′гласная′) else write(′согласная′);

end.

Задача 4. От пользователя вводится слово. Добавьте в конец слова один или два восклицательных знака, так чтобы во вновь полученном слове было четное количество символов. Например: «Ура» → «Ура!», «Привет» → «Привет!!».

Обозначения:

old - вводимое слово - строка символов;

new - выводимое слово - строка символов.

Потребуется функция определения длины слова - length(x).

Добавление символов к строке осуществляется с помощью операции «+». Для переменных строкового типа этот знак означает операцию «склеивания» строк.

var old, new: string;

begin

write(′Введите слово′); readln(old);

if length(old) mod 2 = 0 then new := old + ′!!′ else new := old + ′!′;

writeln(new);

end.

Задача 5. По номеру года определите, високосный ли он.

Год считается високосным, если его номер кратен 4. Но если номер года кратен 100 (1800, 1900 и т. п.), то год не считается високосным за исключением того случая, когда номер года кратен 400 (1600, 2000 и т. п., которые тоже считаются високосными).

Обсуждение алгоритма. Это пример алгоритма, в котором порядок проверки условий (кратен ли номер года 4, 100 или 400) крайне важен. Ведь число, кратное 100, будет кратно и 4, а число, кратное 400, будет кратно и 100.

В алгоритмизации есть такой прием: ввод переменной-признака (иногда ее называют «флаг»). Пусть какая-нибудь переменная (в нашем случае priznak) может принимать только 2 значения. Например, priznak = 0 будет означать, что год не високосный, а priznak =1 - что високосный. Проверяя условия на кратность года тому или иному числу, устанавливаем соответствующее значение переменной признака.

Программа может иметь вид:

var god, priznak: integer;

begin

write(′Введите номер года′); readln(god);

if god mod 4 = 0 then priznak := 0 else priznak := 1;

if god mod 100 = 0 then priznak := 1; {отменяем предыдущее}

if god mod 400 = 0 then priznak := 0; {значение признака}

if priznak = 1 then write(′не′); write(′високосный год′);

end.

Замечание

Обратите внимание, как организован вывод результата: слова «високосный год» выводятся в любом случае, а частица «не» выводится, только когда признак равен 1.

Задача 6. Вычислите значение функции

Блок-схема решения показана на рисунке 87.

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

var x: real; y: integer;

begin

write(′Введи х:′); readln(x);

if x < 0 then y := -1

else if x = 0 then y := 0

else y := 1;

writeln(′y =′, y);

end.

Основную часть алгоритма (вычисление значения y) можно реализовать следующим образом:

if x < 0 then y := -1;

if x = 0 then y := 0;

if x > 0 then y := 1;

Но нельзя написать так:

if x < 0 then y := -1;

if x = 0 then y := 0 else y := 1;

Ошибка состоит в том, что для всех значений х, меньших 0, первый оператор действительно присвоит переменной y значение -1, но выполнение второго оператора изменит это значение на +1 (так как отрицательное число не равно 0).

Запомните

Если при решении задачи вам нужно предусмотреть выбор одного варианта из трех возможных, то можно использовать конструкцию:

if <условие 1> then <выбор 1>

else if <условие 2> then <выбор 2>

else <выбор 3>;

или конструкцию:

if <условие 1> then <выбор 1>;

if <условие 2> then <выбор 2>;

if <условие 3> then <выбор 3>;

Причем, условия 1 - 3 должны «перекрывать» все возможные значения переменной.

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

1

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

2

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

Задача 1. Составьте блок-схему и напишите программу, которая позволяла бы «угадать», какого персонажа сказки «Репка» задумал пользователь. Какое минимальное количество условий потребуется проверить?

Задача 2. Вычислите значение выражения для произвольных х и у.

Задача 3. Определите, в какой координатной четверти или на какой оси находится точка с координатами (х, у).

Например, точка (-2, 5) находится во второй четверти, а точка (1, 0) - на оси х.

Задача 4. Даны три числа. Определите, можно ли построить треугольник с такими длинами сторон, а если можно, то:

а) определите какого он будет вида - прямоугольным, тупоугольным или остроугольным;

б) проверьте, является ли треугольник равнобедренным или равносторонним.

Задача 5. От пользователя вводятся три имени. Расположите их в алфавитном порядке и вывести на экран.