Алгоритмы_Технологии программирования_ООП (1)

Кафедра		Способы записи алгоритмов		Кафедра
информатики				информатики
			УГАТУ				УГАТУ
Запись алгоритма на языке псевдокода						Запись алгоритма на
		нач цел m,k				языке блок-схем
		ввод m
		k := 0
		нц
		m := div(m,10)
		k := k + 1
		кц до (m = 0)
		вывод k
		кон
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	41			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	42
Кафедра		Графический способ записи алгоритмов		Кафедра		Графический способ записи алгоритмов
информатики				информатики
			УГАТУ				УГАТУ
Обозначение некоторых блоков в соответствии с				Предопределенный
	ГОСТ 19.701-90 СХЕМЫ АЛГОРИТМОВ, ПРОГРАММ
				процесс
	ДАННЫХ И СИСТЕМ
Процесс				Вызов вспомогательного алгоритма
					(обращение к подпрограмме)
Арифметический блок, определяющий
	действия, которые необходимо выполнить			Принятие решения
Передача данных				Логический блок, проверяющий истинность
Ввод или вывод информации					или ложность некоторого условия
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	43			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	44

Кафедра		Графический способ записи алгоритмов		Кафедра		Графический способ записи алгоритмов
информатики				информатики
			УГАТУ				УГАТУ
Модификация				Прерывание
Организация циклического процесса при				Начало, конец, пуск, останов, вход в
	известном количестве повторений				подпрограмму
Граница цикла				Комментарий
Начало и конец цикла.				Символ используют для добавления
Условие помешают внутри символа в начале
					описательных комментариев или
	или конце в зависимости от расположения
					пояснительных записей
	операции проверки условия
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	45			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	46
Кафедра		Графический способ записи алгоритмов				Блок-схема вычисления y
информатики
			УГАТУ				УГАТУ
Соединитель
Символ отображает выход из одной части схемы						Прерывание. Начало и конец
						алгоритма
и вход в другую часть этой схемы,						Передача данных.
используется для обрыва линии и продолжения
						Ввод/вывод
ее в другом месте. Символы-соединители
должны содержать одно и то же уникальное
обозначение
Блоки соединяются линиями потока информации.						Процесс. Организация
Внутри блоков записываются выполняемые						вычислений
действия. Линии со стрелками определяют
направление вычислений.
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	47			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	48

			Блок-схема табулирования				Блок-схема НОД
				УГАТУ				УГАТУ
			Модификация
			Организация
			циклического
		y = sin(x)	процесса при				Граница цикла
			известном
			количестве
			повторений
							Принятие решения.
							Проверка истинности или
							ложности некоторого
							условия
			основы алгоритмизации курс 1, 2014 - 2015 г.	49			алгоритмизации курс 1, 2014 - 2015 г.	50
Кафедра		Основные правила применения символов и			Кафедра		Основные правила применения символов и
информатики		выполнения схем согласно ГОСТ			информатики		выполнения схем согласно ГОСТ
				УГАТУ				УГАТУ
•	символы в схеме должны быть расположены				•	потоки данных или управления показываются
						линиями, и если поток имеет направление,
	равномерно;
						отличное от стандартного (слева направо и
•	следует избегать большого числа длинных
						сверху вниз), то стрелки должны указывать это
	линий и пересечений;
						направление;
•	не допускается изменения углов в начертании				•	входящие линии могут объединяться в одну
	символов;
						исходящую линию, при этом место их
•	если объем текста, помещаемого внутри					объединения должно быть смещено;
	символа, превышает его размеры, то следует				•	линии в схемах должны подходить к символу
	использовать символ комментария;
						либо слева, либо сверху, а исходить либо
						справа, либо снизу и направлены к центру
						символа.
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.		51			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	52

Кафедра		Базовые алгоритмические структуры		Кафедра
информатики				информатики
			УГАТУ			УГАТУ
Практически любой сложный алгоритм
представляет собой комбинацию трех типов				В блок-схемах для
базовых алгоритмических структур: линейного,
				записи линейной
разветвляющегося и циклического.
				алгоритмической
Линейные алгоритмические структуры				структуры
	(следование) состоят из последовательности
				используется
	операций, выполняющихся только один раз в
	порядке их следования			блок «Процесс».
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	53		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	54
Кафедра		Базовые алгоритмические структуры		Кафедра	Базовые алгоритмические структуры
информатики				информатики
			УГАТУ			УГАТУ
Разветвляющиеся				Подобная структура
алгоритмические				называется также
структуры (ветвление)				«ЕСЛИ – ТО – ИНАЧЕ»,
обеспечивают выбор				или «развилка». Каждый
между двумя				из путей (ТО или ИНАЧЕ)
альтернативами.				ведет к общей точке
Выполняется проверка				слияния, так что
некоторого условия, а				выполнение программы
затем выбирается один				продолжается независимо
из путей продолжения				от того, какой путь был
алгоритма.				выбран.
		Программирование и основы алгоритмизации			Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	56

Кафедра	Базовые алгоритмические структуры					Кафедра	Базовые алгоритмические структуры
информатики						информатики
					УГАТУ			УГАТУ
Для графического						Может оказаться, что для
способа записи						одного из результатов
разветвляющих						проверки ничего
алгоритмов						предпринимать не надо.
						В этом случае можно
используется блок
						применять только один
«Принятие решения»,
						обрабатывающий блок.
внутри которого
						Такие структуры
записывается						называют «Неполное
логическое выражение.						ветвление» или
						«ЕСЛИ – ТО»,
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.				57		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	58
Кафедра	Базовые алгоритмические структуры						Нахождение максимума
информатики
					УГАТУ			УГАТУ
				нач вещ a, b, c, max
Пример.				ввод a, b, c
Найти квадрат				если (a > b)			да
наибольшего из				то max := a
трех заданных				иначе max := b				c
чисел:		a b c		все
		,	, .
				если (c > max)			2
				то max := c
				все
				вывод max2
				кон	59		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	60
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

Кафедра	Базовые алгоритмические структуры			Кафедра			структуры
информатики				информатики
			УГАТУ					УГАТУ
Пример. Даны					R1	R2
действительные числа
x, y – координаты
точки. Определить		R1	R2
принадлежит ли точка
(x, y) области,
заштрихованной на
рисунке.
		x2 + y2 = r2
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.		61		Программирование		алгоритмизации курс 1, 2014 - 2015 г.	62
Кафедра	Базовые алгоритмические структуры			Кафедра	Базовые алгоритмические структуры
информатики				информатики
			УГАТУ					УГАТУ
				Циклические алгоритмические структуры
R1	R2 нач вещ x, y, r1, r2			обеспечивают многократное выполнение одной и
	ввод x, y, r1, r2			той же последовательности действий для
	если (x2+y2 >= r	2) and (x2+y2	<= r 2)	различных значений, входящих в них
	1		2	переменных.
	то вывод “Принадлежит”
	иначе вывод “Не принадлежит”			Различают два типа структур цикла:
	все			- цикл с параметром или с повторением;
	кон			- цикл с условием.
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.		63		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.			64

Кафедра		Базовые алгоритмические структуры		Кафедра	Базовые алгоритмические структуры
информатики				информатики
			УГАТУ			УГАТУ
Основной блок цикла, тело цикла, производит				Циклы с параметром используют тогда, когда
				количество повторов тела цикла заранее
	требуемые вычисления.
				известно.
Остальные блоки организуют циклический				Для графического способа
	процесс:
				записи таких
•	устанавливают начальные и новые значения			алгоритмов
	параметров цикла;			используется блок
				«Модификация», внутри
•	проверяют условия окончания или продолжения
				которого записывается
	циклического процесса.			как изменяется
				параметр цикла .
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	65		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	66
Кафедра		Базовые алгоритмические структуры		Кафедра	Базовые алгоритмические структуры
информатики				информатики
			УГАТУ			УГАТУ
		блок организующий		Пример. Вычислить значения
		циклический процесс		функции y = f(x) некоторой
		тело цикла		переменной х, изменяющейся
		k –параметр цикла,		от начального значения х0 до
				конечного хk с постоянным
		a – начальное значение
				шагом h (протабулировать
		параметра цикла,
				функцию на заданном
		b – конечное значение
		параметра цикла,		промежутке [х0 , хk] с шагом h).
		h – шаг изменения
		параметра цикла.
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	67		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	68

Кафедра		Базовые алгоритмические структуры		Кафедра	Базовые алгоритмические структуры
информатики				информатики
			УГАТУ			УГАТУ
		нач вещ x0, xk, h		Циклы с условием используются тогда, когда
				число повторений цикла заранее неизвестно,
		ввод x0, xk, h		но задано условие окончания цикла.
		нц для x от x0 до xk шаг h		Для графического способа записи таких
		y := f(x)		алгоритмов используется блок «Границы
				цикла».
		вывод y
		кц
		кон
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	69		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	70
Кафедра		Базовые алгоритмические структуры		Кафедра	Базовые алгоритмические структуры
информатики				информатики
			УГАТУ			УГАТУ
Если условие окончания цикла проверяется перед					Значение логического выражения в
выполнением тела цикла, то такие циклические					условии вычисляется перед
структуры называют циклами с предусловием					каждым выполнением тела цикла.
(«Выполнять пока»).					Если оно истинно, то выполняется
	Блок организующий				тело цикла и снова вычисляется
					выражение условия.
	циклический процесс
					Если результат имеет ложное
		Тело цикла			значение, происходит выход из
					цикла.
		Конец цикла		Цикл продолжает свою работу, пока значение
				логического выражения остается истинным.
		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	71		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	72

Кафедра	Базовые алгоритмические структуры		Кафедра	Базовые алгоритмические структуры
информатики			информатики
		УГАТУ			УГАТУ
Если проверка условия происходит после				Вначале выполняется тело
выполнения тела цикла – циклами с
				цикла, затем проверяется
постусловием («Выполнять до тех пор пока не»)
				условие выхода из цикла.
	Начало цикла			Если значение логического
				выражения ложно, тело
	Тело цикла			цикла выполняется еще
				раз, если истинно –
	Блок организующий			происходит выход из
				цикла.
	циклический процесс
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	73		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	74
Кафедра	Базовые алгоритмические структуры		Кафедра	Базовые алгоритмические структуры
информатики			информатики
		УГАТУ			УГАТУ
	Таким образом, цикл			Чтобы циклы с условием
				успешно завершились
	продолжает свою работу,
	до тех пор пока не станет			необходимо, чтобы в
	истинным значение			теле цикла был хотя бы
	логического выражения.			один оператор,
	Тело цикла с постусловием			изменяющий значения
	всегда выполняется хотя
				переменных, входящих в
	бы один раз.
				логическое выражение.
	Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	75		Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.	76

Алгоритм НОД

Кафедра

Базовые алгоритмические структуры

информатики

УГАТУ

УГАТУ

нач цел m,n,d

изменение

ввод m,n

нц

переменных

если (m > n)

если (m=0)

то m := mod (m,n)

то d:=n

иначе

иначе

n := mod(n,m)

d:=m

все

все

вывод d

кц до (m = 0) or (n =0)

кон

условие

алгоритмизации курс 1, 2014 - 2015 г.

77

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

78

Кафедра

Вложенные циклы

Кафедра

Задача. Вычислить произведение

информатики

информатики

УГАТУ

n

m

УГАТУ

i

∏ ∏

=

Если телом цикла является также циклическая

=

= 1 + j 2

i

структура, то такие циклы называют

1 j 1

вложенными. Тип циклов при этом может

1

1

1

быть любым.

×

×K×

×

1 + 12 1 + 22

1 + m2

При построении вложенных циклических

2

2

2

структур всегда следует соблюдать правило:

×

×K×

K×

все блоки внутреннего цикла должны

1 + 12

1 + 22

1 + m2

полностью лежать в теле внешнего цикла.

n

n

n

1 + 12

×

1 + 22

×K×

1 + m2

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

79

Программирование и основы алгоритмизации курс 1, 2014 - 2015 г.

80