II. Разветвляющиеся алгоритмы.

Информатика

Основы алгоритмизации

Класс

Автор Бублик Елена Николаевна

Учитель информатики

ГБОУ гимназия №343

Санкт-Петербург

2012-2013

АЛГОРИТМ И БЛОК-СХЕМА

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

Слово «алгоритм» произошло от латинского слова algorifmi. В IX веке математик Мухаммед ибн Муса ал-Хорезми впервые в истории математики ввёл общие правила решения квадратных уравнений. В Европе при переводе имя автора переделали в Алгоритми. Ссылки на рецепты решений из книги Мухаммеда европейские авторы начинали со слов: "Так говорил Алгоритми...". С течением времени сами рецепты для решения математических задач стали называть алгоритмами.

Точное математическое определение понятия "алгоритм" было выработано лишь в тридцатых годах XX века. Почему же до этого времени математики довольствовались интуитивным понятием алгоритма? Это связано с тем, что обычно понятие алгоритма встречалось в связи с конкретным решением задачи. Об алгоритме говорили лишь тогда, когда предлагался способ решения какого-либо класса задач. В начале XX века в математике накопилось большое количество задач, которые не поддавались решению, несмотря на то, что над ними думали первоклассные ученые. Возникло подозрение, что для некоторых из этих задач вообще не существует разрешающего алгоритма. Утверждение о неразрешимости того или иного класса задач можно было вывести, только имея точное определение алгоритма, надо было знать, не существование чего требуется доказать. Понятие алгоритма является не только центральным понятием теории алгоритмов, не только одним из главных понятий математики вообще, но одним из главных понятий современной науки. Более того, сегодня, с наступлением эры информатики, алгоритмы становятся одним из важнейших факторов цивилизации.

Исполнитель алгоритма - это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.

Исполнителя характеризуют:

· среда;

· элементарные действия;

· система команд;

· отказы.

Среда (или обстановка) — это «место обитания» исполнителя. Например, для исполнителя Робота среда — это бесконечное клеточное поле. Стены и закрашенные клетки тоже часть среды, а их расположение и положение самого Робота задают конкретное состояние среды.

Система команд. Каждый исполнитель может выполнять команды только из некоторого строго заданного списка - системы команд исполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды. Например, команда Робота «вверх» может быть выполнена, если выше Робота нет стены. Ее результат — смещение Робота на одну клетку вверх.

После вызова команды исполнитель совершает соответствующее элементарное действие.

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

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

В информатике универсальным исполнителем алгоритмов является компьютер.

Основные свойства алгоритмов следующие:

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

Дискретность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов).

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

Результативность (или конечность) — алгоритм должен приводить к решению задачи за конечное число шагов.

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

Существует несколько форм представления алгоритмов:

· словесная;

· табличная;

· графическая;

· программа.

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

Словесный способ не имеет широкого распространения, так как такие описания:

· строго не формализуемы;

· страдают многословностью записей;

· допускают неоднозначность толкования отдельных предписаний.

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

Графический способ подразделяется на:

· рисунок;

· граф-схемы;

· блок-схемы.

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

Можно представить алгоритм в виде схемы или графа — вторая,болеестрогая, формализованная форма

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

Граф — геометрический объект, состоящий из вершин и соединяющих вершины линий и дуг.

Наиболее распространенной формой представления алгоритма является блок-схема. Для отображения алгоритма в виде блок-схемы используется стандартный набор графических объектов (блоков).

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

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

Чаще всего используются блоки следующих типов:

 

	начало и конец алгоритма
	выполнение операции
	выбор направления выполнения алгоритма в зависимости от некоторых переменных условий
	ввод/вывод данных

 

 

I. ЛИНЕЙНЫЕ АЛГОРИТМЫ.

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

Блок-схема базовой структуры следование.

вход

выход

Задача 1. По кулинарному рецепту приготовления орехового напитка составьте словесный алгоритм.

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

Продукты: 250 г очищенных грецких орехов,0,8 л молока, 120 г сахара.

1. ____________

2. ____________

3. ____________

4. ____________

5. ____________

Задача 2. Составьте словесный алгоритм деления отрезка пополам с помощью линейки и циркуля.

1._____________

2. ____________

3. ____________

4. ____________

5. ____________

Задача 3. Составьте блок-схему алгоритма, который по двум заданным вещественным числам вычисляет коэффициенты приведенного квадратного уравнения, корнями которого являются эти числа.

Программа: __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________

Задача 4. Данадлина ребра куба. Составьте блок-схему алгоритма нахождения площади грани, площади полной поверхности и объема этого куба.

 

Заполните таблицу значений при а = 3.     Шаг алгоритма Аргу­мент Результаты Пояс­нения а S1 S2 V   2 3 4 5           Программа: __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________

Задача 5. Дано а. Не используя никаких функций и операций, кроме умножения, получить а⁸ за три операции. Заполните шаблон, используя таблицу значений приа = 2

 

 

Шаг алго­ритма Аргу­мент Промежуточные величины Резуль­тат Пояс­нения а b с y                 Вывод 256 Конец Программа: __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________

Задача 6. Составьте алгоритм для нахождения расстояния между двумя пешеходами, идущими навстречу друг другу, начавшими путь одновременно.

L_o - начальное расстояние,

V₁ - скорость первого пешехода,

V₂ - скорость второго пешехода,

Т - время движения,

L₁ - текущее расстояние.

 

1. _______

2. _______

3. _______

4. _______

5. _______

Задача 7. Составьте блок-схему алгоритма вычисленияпериметра и площади прямоугольного треугольникапо длинам двух егокатетов.

Заполните таблицу значений при а = 3, b=4. Шаг алго­ритма Аргументы Промежу-точнаявеличина Результат Пояс­нения     а b с P S                   Программа: __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________

Задача 8. Найти произведение цифр заданного четырехзначного числа n. Заполните шаблон, используя таблицу значений при n = 8341.

 

Шаг	Аргу-	Промежуточные величины	Резуль-	Пояс-
алгоритма	мент		тат	нения
	п	т	а	b	с	d	Р
								Вывод 96
								Конец

 

Блок-схема:

Задача 9. По заданной блок схеме алгоритма заполните таблицу значений (R₁ =3, R₂= 5) и восстановите условие задачи.

R1, R2, π х S1=πR1 S=S2-S1 S2=πR2

Заполните таблицу значений при R1 = 3, R2=5. Шаг алго­ритма Аргументы Промежу-точная величина Результат Пояс­нения ритма   R1 R2 π S1 S2 S                     Программа: __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ Условие: __________________________________________ __________________________________________ __________________________________________ __________________________________________

 

 

II. РАЗВЕТВЛЯЮЩИЕСЯ АЛГОРИТМЫ.

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

Блок-схемы базовых структур.

Развилка полная Вход Выход Да Нет

Развилка неполная Вход Выход Да Нет

 

Задача 1. Составьте словесный алгоритм нахождения максимального числа из двух заданных.

1.________________________________________________ ________________________________

2._________________________________________________ ________________________________

3.________________________________________________ ________________________________

4._________________________________________________ ________________________________

5.________________________________________________ ________________________________

Задача 2. В блок-схеме алгоритма вычисления значения функции

 

Блок-схема х Y:=3 Да Нет S

Программа: __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________ __________________________________________

Задача 3. Кровяное давление у старшеклассников считается нормальным, если верхняя его граница Н < 120, нижняя h> 60 и H-h> 30. Составьте алгоритм, который в зависимости от измеренных значений Н и h выдает одно из следующих значений: «нормальное», «повышенное», «пониженное».

Воспользуйтесь шаблоном.

 

Блок-схема х

Программа: ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ______________________________

Задача 4. Заданы три числа. Известно, что два равны между собой, а третье отлично от них. Составьте блок-схему нахождения числа, отличного от двух других.

Блок-схема

Программа: ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ______________________________

 

 

Задача 5. Какое значение получит переменная Z в результате выполнения следующего алгоритма?

 

 

Блок-схема x,y x>0 y>0 z:=0 z:=1 z:=2 z

Программа: ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ______________________________

 

Задача 6. Заполните шаблон блок-схемы алгоритма исследования квадратного уравнения ах² + bх + с = 0 (а ≠0)

Блок-схема

Программа: ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ______________________________

Задача 7. Определить, принадлежит ли точка (х, у) круговому кольцу с центром в начале координат и внутренним радиусом r, а внешним R.

Заполните таблицу значений для х = 3; у = 4;r= 1,5; R = 3, используя блок-схему алгоритма.

Блок-схема

Программа: ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ______________________________

Шаг	Аргументы	Промежуточная величина	Проверка условий	Результат	Пояснения
X	Y	r	R	S

 

Задача 8. Найти значение;

В шаблоне блок-схемы алгоритма расставьте «да» или«нет» и заполните пустые блоки.

 

Блок-схема	Программа: ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ______________________________
Задача 9.По графику функции составьте блок-схему алгоритма нахождения значений функции.

x y

y=

Блок-схема

Программа: ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ______________________________

Задача 10. По заданной блок-схеме алгоритма нарисуйте график функции.

 

Блок-схема X<0 X ≤2 Y:=-X +3 y Y:=1 Y:= - X X<1 Y:= X X

Программа: ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ ____________________________________________________________ y x

Задача 11. Дан график функции. Восстановите вид функции и составьте блок-схему алгоритма для вычисления ее значений в зависимости от заданного х.

-2 1,5 y y Y=

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

d,m,g

m

m=12

d<28

d=d+1

m=3

m=m+1

g=g+1

d=1

d,m,g

4,6,9,11

Задача 13. Даны произвольные числа а, Ь, с. Составьте блок-схему алгоритма, который выдает значение 0, если нельзя построить треугольник с такими длинами сторон, иначе выдает 3, 2 или 1, в зависимости от того, равносторонний это треугольник, равнобедренный или какой-либо иной.

Заполните таблицу значений при а = 5, b= 4, с = 10;

при а = 5, b = 4, с - 5.

Шаг алгоритма	Аргументы	Результат	Проверка условий	Пояснения
a	b	c	к

Шаг алгоритма	Аргументы	Результат	Проверка условий	Пояснения
a	b	c	к

К=1

К=0

К=2

К=3

да

да

нет

нет