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

Краткие теоретические сведения

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

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

Свойства алгоритма:

- понятность – все действия должны входить в систему команд исполнителя, т.е. быть понятны ему;

- дискретность - алгоритм делится на отдельные элементарные шаги;

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

- конечность(результативность) - алгоритм должен завершаться за конечное число шагов.

- массовость – алгоритм позволяет решать целый класс похожих задач.

Способы записи алгоритма:

1. Словесно-формульный

Пример.

Алгоритм деления обыкновенных дробей

 

1. Числитель первой дроби умножить на знаменатель второй;

2. Знаменатель второй дроби умножить на числитель второй;

3. Записать дробь, числитель которой есть результат

выполнения пункта 1, а знаменатель - результат

выполнения пункта 2.

 

2. Графический способ (в виде блок-схемы )

 

Блок схема – это графическое представление алгоритма при помощи стандартных обозначений. Блок схемы составляются в соответствии с ГОСТами. ГОСТы алгоритмов: ГОСТ 19.002-80, ГОСТ 19.003-80. На схемах алгоритмов выполняемые действия изображаются в виде отдельных блоков, которые соединяются между собой линиями связи в порядке выполнения действий. На линиях связи могут ставиться стрелки, причем, если направление связи слева направо или сверху вниз, то стрелки не ставятся. Блоки нумеруются. Внутри блока дается информация о выполняемых действиях.

Таблица 1 – Основные блоки, используемые при составлении алгоритмов

Название	Обозначение	Назначение
Пуск, Останов		Начало-конец алгоритма
Процесс		Любое вычислительное действие
Решение		Проверка условия
Модификатор		Цикл
Ввод-вывод		Ввод-вывод данных
Документ		Вывод на печатающее устройство
Соединитель		Используется на линиях разрыва
Комментарий		Комментарий

3. Запись алгоритма в виде последовательности команд для ЭВМ

Алгоритм, записанный на одном из языков программирования называется программой.

 

Типы вычислительных процессов

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

Линейные алгоритмы

Линейный алгоритм – алгоритм, в котором все команды выполняются последовательно друг за другом.

Пример 1: составить алгоритм обмена значений переменных a и b.

Команды	a	b	c
a=5, b=12			-
c=a
a=b
b=c

 

 

Пример 2: Составить алгоритм обмена значений переменных a и b без использования дополнительной переменной.

 

Команды	a	b
a=3, b=7
a=a+b
b=a-b
a=a-b

 

 

Пример 2: составить алгоритм вычисления a⁸, используя не более 3х действий умножения (возведение в степень не использовать)

a: 2 ->4 ->16 -> 256

a=a*a | a²

a=a*a | a⁴

a=a*a | a⁸

 

Команды	a
a=2
a=a*a
a=a*a
a=a*a

 

Пример 3: Составить алгоритм вычисления a⁶, используя не более трех команд умножения.

Команды	a	b
a=2		-
a=a*a	22	-
b=a	22	22
a=a*a	24	22
a=b*a	26	22

 

 

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

Часто при выполнении алгоритма должны предлагаться различные действия в зависимости от выполнения или невыполнения некоторого условия. Такие алгоритмические структуры называют ветвлением.

Полное ветвление

 

 

Неполное ветвление

Пример 4. Вычислить выражение для введенного x.

Исходные данные: x.

Результат: y, или ‘функция не определена’

проверяемый случай	x>=0	y	результат
x=9	9>=0 да	y=	y=
x=-9	-9>=0 нет	-	функция не определена

 

 

Пример 5. Вычислить выражение для введенного x.

проверяемый случай	x>=0	y	результат
x=9	9>=0 да	y=	y=
x=-9	-9>=0 нет	-	функция не определена

 

Пример 6. Выбрать максимальное из 2х чисел a и b.

1 вариант 2 вариант

 

проверяемый случай	x	y	результат
a=9 b=15	9>15 нет	15>9 да
a=18 b=3	18>3 да	-
a=7 b=7	7>7 нет	7>7 нет	числа равны

 

 

Пример 7. Выбрать максимальное из 3х чисел a, b, c.

 

проверяемый случай	x	max	y	результат
a=9 b=15 c=2	9>15 нет		2>15 нет
a=8 b=3 с=22	8>3 да		22>8 да
a=12 b=9 c=1	17>9 нет		1>17 нет

 

Алгоритмы с циклами

 

Цикл – многократное повторение одних и тех же действий.

Цикл с предусловием

 

Такой цикл называют «пока». Механизм его работы: пока условие истинно, повторять…

 

Пример 8. Вывести все «-» члены арифметической прогрессии -11; -7…

Пусть a – очередной член прогрессии.

a=a₁+4 – следующий член прогрессии.

Пока a<0, повторять a=a₁+4.

 

Цикл с предусловием может не выполниться ни разу, если условие сразу оказалось ложным.

Пример 9. Найти сумму первых десяти натуральных чисел.

S=1+2+…+10

S – сумма

а – очередное слагаемое.

S:=S+a a:=a+1

Выполнять, пока a<=10

 

Цикл с постусловием.

 

 

Механизм работы: повторять, пока условие не станет истинным.

Этот цикл всегда выполняется хотя бы 1 раз.

Пример 10. Найти сумму положительных членов арифметической прогрессии: 17; 11 …

S=a+S a:=a-6

тело цикла повторять до тех пор, пока не выполнится условие a<=0

 

Пример 11. Вычислить n!

F=F*k k=k+1

тело цикла повторять до тех пор, пока не выполнится условие k>N

 

 

Задания для самостоятельной работы

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

Вариант 1:

· По длине ребра куба найти площадь грани, площадь полной поверхности и объем куба.

· Вычисление суммы цифр введенного натурального двухзначного числа.

Вариант 2:

· Найти площадь кольца с радиусами r1 и r2.

· Из чисел A, B, C, D выбрать максимальное.

Вариант 3:

· Вычислить площадь треугольника по трем сторонам (по формуле Герона).

· Вводятся Х и Y. Если Х больше Y, то произвести их обмен.

Вариант 4:

· По координатам трёх вершин некоторого треугольника найти его площадь и периметр.

· Вычислить площадь параллелограмма по двум сторонам и углу между ними, заданному в градусах.

 

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

четные) нечетные)

 

 

нет

нет

да

да