Тема 5_Алгоритмы

Кафедра	ЛЕКЦИИ ПО ИНФОРМАТИКЕ		Кафедра		Тема 4
информатики		УГАТУ	информатики			УГАТУ
	Для студентов факультета АТС
	групп МХ, ММ, СМ, ФМ, АТП, ТМ, ВТ
Составители:					Алгоритмы
доценты Кафедры Информатика
Ахметсафина Римма Закиевна
Карчевская Маргарита Петровна
Рамбургер Ольга Леонардовна
	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	1
Кафедра	Понятие алгоритма		Кафедра	Понятие алгоритма
информатики			информатики
		УГАТУ				УГАТУ
			Алгоритм – конечный набор точных и понятных
Понятие алгоритма является одним из			исполнителю предписаний, позволяющих за
основных понятий современной			конечное число шагов решать конкретную
			задачу из определенного класса однотипных
информатики. Термин алгоритм произошел
			задач.
от латинской формы написания имени
выдающегося математика IX века Аль			Исполнителем может быть человек, группа людей, робот, станок,
Хорезми (algorithmi), который сформулировал			компьютер, язык программирования и т.д. Исполнитель имеет в
			наличии только некоторую совокупность команд (систему команд
правила выполнения четырех
			исполнителя – СКИ), которую может использовать при выполнении
арифметических действий в десятичной			алгоритма для получения необходимого результата.
системе счисления.			Т. е. исполнитель действует формально, отвлеченно от
			содержания поставленной задачи, не вникая в смысл того, что он
			делает, только строго выполняет некоторые правила, инструкции,
			команды
	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	3	Информатика		ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	4

Кафедра		Понятие алгоритма		Кафедра		Понятие алгоритма
информатики				информатики
			УГАТУ			УГАТУ
				Понятие алгоритма связано с понятием исходных данных и
Наличие алгоритма формализует процесс решения					искомого результата, поскольку назначением любого алгоритма
	задачи, исключает рассуждение исполнителя.				является преобразование исходных данных в искомый
					результат. При этом исходные данные выбираются из
Использование алгоритма дает возможность решать					некоторой области, которая называется областью допустимых
	задачу формально, механически исполняя команды				значений исходных данных.
	алгоритма в указанной последовательности.			Преобразование исходных данных в искомый результат
					выполняется на основе знаний о предметной области. Знания,
Целесообразность предусматриваемых алгоритмом					как правило, имеют вид различных естественных законов
	действий обеспечивается точным анализом со				(физических, химических, биологических, экономических и т.д.),
	стороны того, кто составляет этот алгоритм.				либо абстрактных законов (математические формулы, правила
					или теоремы).
				На основе данных знаний при составлении алгоритма
					формируются цепочки действий, приводящих к искомому
					результату.
		Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	5			Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	6
Кафедра		СВОЙСТВА АЛГОРИТМА		Кафедра		СВОЙСТВА АЛГОРИТМА
информатики				информатики
			УГАТУ			УГАТУ
Помимо того, что алгоритм разрабатывается ради того, чтобы из
исходных данных получить искомый результат, алгоритм должен				Подводя итог выше сказанному, можно дать следующее
удовлетворять еще целому ряду свойств:					определение алгоритма.
Дискретность. Означает, что путь решения задачи определен в виде
последовательности шагов – четко разделенных друг от друга предписаний.				Алгоритм – это последовательность
Только выполнив одно предписание, можно приступить к выполнению
следующего.					однозначных предписаний, исполнение
Понятность. Означает, что алгоритм создается в расчете на определенного
исполнителя, т.е. необходимо, чтобы он мог понять и выполнить каждый шаг					которых позволяет с помощью конечного
предписания.
					числа шагов получить искомый
Детерминированность (однозначность). Процесс применения правил к исходным
данным (путь решения задачи) определен однозначно.					результат, однозначно определяемый
Результативность. На каждом шаге процесса применения правил известно, что
считать результатом этого процесса, а сам процесс должен закончиться за					исходными данными.
конечное число шагов.
Массовость. Означает, что алгоритм применим к целому классу однотипных
задач, а при решении конкретной задачи из класса исходные данные могут
меняться в определенных пределах.
		Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	7			Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	8

Кафедра	СПОСОБЫ ЗАПИСИ АЛГОРИТМОВ			Кафедра
информатики			УГАТУ	информатики СПОСОБЫ ЗАПИСИ АЛГОРИТМОВ		УГАТУ
Алгоритм, составленный для некоторого исполнителя,				Для визуального представления алгоритма разработаны
				специальные алгоритмические языки.
можно представить различными способами. Один из
				Они позволяют достаточно наглядно, просто и в удобной для
способов - словесная форма записи алгоритма.
Например, словесное описание алгоритма Евклида для				разработчика форме отображать содержательный смысл алгоритма
				и производить его анализ.
нахождения наибольшего общего делителя (НОД) двух
целых положительных чисел m и n выглядит так:				Алгоритмический язык – это система обозначений
					(символьных и графических), предназначенных для
Шаг 1: Задать числа m и n.					записи алгоритмов.
Шаг 2: Если m больше n, то сделать m равным остатку от деления				Обычно алгоритмический язык дополняется математической
	m на n, иначе сделать n равным остатку от деления n на m.
				символикой и либо графическими компонентами, либо некоторыми
Шаг 3: Если m и n не равны нулю, то перейти к шагу 2.
				формальными конструкциями. В первом случае он называется
Шаг 4: Если m равно нулю, то НОД равен n, иначе НОД равен m.				языком структурных схем или языком блок-схем, во втором случае
				он называется языком псевдокодов или просто псевдокодом.
	Информатика ФАП - 2, ФАТС – 2, 3	курс 1, семестр 2, 2009 г.	9		Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	10
Кафедра	СПОСОБЫ ЗАПИСИ АЛГОРИТМОВ. Псевдокод			Кафедра
информатики				информатики
					СПОСОБЫ ЗАПИСИ АЛГОРИТМОВ. БЛОК-СХЕМЫ
			УГАТУ			УГАТУ
Пример. На языке		нач цел m,n,x,y,f		Графический способ записи предполагает
псевдокодов алгоритм		ввод m,n
					использование определенных графических символов
Евклида для нахождения
наибольшего общего		m:=abs(x); n:=abs(y);			– блоков. Отсюда и вытекает использование
делителя (НОД) двух		нц пока (m>0) и (n>0)			названия блок-схема для графического
целых положительных					представления алгоритма.
чисел m и n выглядит так:		если (m>n)
				Каждый блок предписывает выполнение определенных
		то m:=mod (m,n)
					действий. Совокупность блоков образует схему
		иначе n:=mod(n,m)			алгоритма или блок-схему.
		все;
Формальные		кц		Впервые запись алгоритмов на языке блок-схем ввели российские
конструкции		f:=m+n;		математики А.А.Ляпунов и Ю.Н.Янов в 1956г. В дальнейшем этот способ
	языка			нашел свое отражение в “Единой системе программной документации”, в
псевдокодов		вывод f;		которой установлен единый стандарт записи блок-схем (ГОСТ 19.701 – 90).
		кон
	Информатика ФАП - 2, ФАТС – 2, 3	курс 1, семестр 2, 2009 г.	11		Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	12

Кафедра			Кафедра
информатики			информатики
Графический способ записи алгоритмов			Графический способ записи алгоритмов
		УГАТУ		УГАТУ
Обозначение некоторых блоков в соответствии с
ГОСТ 19.701-90 СХЕМЫ АЛГОРИТМОВ, ПРОГРАММ
ДАННЫХ И СИСТЕМ
			Блоки соединяются линиями потока информации. Внутри блоков записываются
			выполняемые действия. Линии со стрелками определяют направление
			вычислений.
	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	13	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	14
Кафедра Основные правила применения символов и			Кафедра
информатики	выполнения схем согласно ГОСТ		информатикиБазовые алгоритмические структуры
		УГАТУ		УГАТУ
• символы в схеме должны быть расположены равномерно;			Практически любой сложный алгоритм
• следует избегать большого числа длинных линий и пересечений;
			представляет собой комбинацию трех типов
• не допускается изменения углов в начертании символов;
			базовых алгоритмических структур: линейного,
• если объем текста, помещаемого внутри символа, превышает его
размеры, то следует использовать символ комментария;			разветвляющегося и циклического.
• в схемах может использоваться идентификатор символов,
располагаемый слева над символом, который определяет символ			Линейные алгоритмические структуры (следование)
для использования в справочных целях;
			состоят из последовательности операций, выполняющихся
• потоки данных или управления показываются линиями, и если
			только один раз в порядке их следования
поток имеет направление, отличное от стандартного (направление
потока слева направо и сверху вниз считается стандартным), то
стрелки должны указывать это направление;
• входящие линии могут объединяться в одну исходящую линию, при
этом место их объединения должно быть смещено;
• линии в схемах должны подходить к символу либо слева, либо
сверху, а исходить либо справа, либо снизу и направлены к центру
символа.
	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	15	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	16

Кафедра				Кафедра
информатикиБазовые алгоритмические структуры			УГАТУ	информатикиБазовые алгоритмические структуры		УГАТУ
				Разветвляющиеся
				алгоритмические структуры
				(ветвление) обеспечивают
В блок-схемах для записи				выбор между двумя
				альтернативами. Выполняется
линейной алгоритмической
				проверка, а затем выбирается
структуры используется
				один из путей.
блок «Процесс».
				Подобная структура называется
				также «ЕСЛИ – ТО – ИНАЧЕ»,
				или «развилка». Каждый из
				путей (ТО или ИНАЧЕ) ведет к
				общей точке слияния, так что
				выполнение программы
				продолжается независимо от
				того, какой путь был выбран.
Информатика ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2,	2009 г.	17	Информатика ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2, 2009 г.	18
Кафедра				Кафедра
информатикиБазовые алгоритмические структуры			УГАТУ	информатикиБазовые алгоритмические структуры		УГАТУ
Для графического способа записи
разветвляющих алгоритмов
алгоритмов используется блок
«Принятие решения», внутри				Пример. Найти квадрат
которого записывается
				наибольшего из трех
логическое выражение .
				заданных чисел: a, b, c.
Может оказаться, что для одного из
результатов проверки ничего
предпринимать не надо. В этом
случае можно применять только
один обрабатывающий блок. Такие
структуры называют «Неполное
ветсвлените» или «ЕСЛИ – ТО»,
Информатика ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2,	2009 г.	19	Информатика ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2, 2009 г.	20

Кафедра					Кафедра
информатикиБазовые алгоритмические структуры				УГАТУ	информатикиБазовые алгоритмические структуры			УГАТУ
Задача. Даны действительные числа x, y – координаты точки.					Циклические алгоритмические структуры обеспечивают
					многократное выполнение одной и той же последовательности
Определить принадлежит ли точка (x, y) области, заштрихованной на					действий для различных значений, входящих в них
рисунке.					переменных.
					Основной блок цикла, тело цикла, производит требуемые
					вычисления. Остальные блоки организуют циклический
R1	R2				процесс: устанавливают начальные и новые значения данных,
					проверяют условия окончания или продолжения циклического
					процесса.
					Циклический алгоритм позволяет компактно описать большое
					число одинаковых вычислений над разными данными для
					получения необходимого результата.
					Различают два типа структур цикла:
					- цикл с параметром или с повторением;
					- цикл с условием.
Информатика		ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2, 2009 г.	21	Информатика	ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2, 2009 г.	22
Кафедра					Кафедра
информатикиБазовые алгоритмические структуры				УГАТУ	информатикиБазовые алгоритмические структуры			УГАТУ
Циклы с параметром используют тогда, когда						Выполняется базовая циклическая структура типа
количество повторов тела цикла заранее известно.
						«Цикл с параметром» следующим образом:
Для графического способа записи таких алгоритмов используется						1. Параметру цикла k присваивается начальное
блок «Модификация», внутри которого записывается как						значение a и сравнивается с конечным значением b.
изменяется параметр цикла .						Если начальное значение параметра цикла
						превышает (при положительном шаге цикла) конечное
		блок организующий циклический процесс				значение, то тело цикла ни разу не выполнится;
						2. Выполняется тело цикла;
		тело цикла			3. Текущее значение параметра цикла k увеличивается (или уменьшается)
					на значение шага h. Результат операции k+h присваивается параметру
					цикла k, старое значение при этом теряется;
		K –параметр цикла, a – начальное значение			4. Проверяется условие окончания цикла: текущее значение параметра
		параметра цикла,			сравнивается с конечным значением b. Если значение параметра цикла
		b – конечное значение параметра цикла,			становится больше конечного (при положительном шаге h), то
		h – шаг изменения параметра цикла.			происходит выход из цикла, иначе происходит переход к пункту 2.
Информатика		ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2, 2009 г.	23	Информатика	ФАП - 2, ФАТС – 2, 3 курс 1,	семестр 2, 2009 г.	24

Кафедра	Базовые алгоритмические структуры		Кафедра	Базовые алгоритмические структуры
информатики		УГАТУ	информатики		УГАТУ
Пример. Вычислить			Циклы с условием используются тогда, когда
			число повторений заранее неизвестно, но
значения функции y = f(x)
некоторой переменной х,			задано условие окончания цикла.
изменяющейся от
начального значения х0 до			Для графического способа записи таких алгоритмов
конечного хk с постоянным
			используется блок «Границы цикла».
шагом h (протабулировать
функцию на заданном
промежутке [х0 , хk] с шагом
h). Записать алгоритм
решения задачи с помощью
блок-схемы
	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	25		Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	26
Кафедра	Базовые алгоритмические структуры		Кафедра
информатики		УГАТУ	информатикиБазовые алгоритмические структуры		УГАТУ
Если условие окончания цикла проверяется перед выполнением			Если проверка условия происходит после выполнения тела цикла –
тела цикла, то такие циклические структуры называют циклами с
			циклами с постусловием («Выполнять до тех пор пока не»)
предусловием («Выполнять пока»)
				Тело цикла
	Блок организующий циклический процесс
	Тело цикла			Блок организующий циклический процесс
	Значение логического выражения в условии вычисляется			Вначале выполняется тело цикла, затем проверяется
				условие выхода из цикла.
	перед каждым выполнением тела цикла.
				Если значение логического выражения ложно, тело
	Если оно истинно, то выполняется тело цикла и снова
				цикла выполняется еще раз, если истинно –
	вычисляется выражение условия.
				происходит выход из цикла.
	Если результат имеет ложное значение, происходит
	выход из цикла.		Таким образом, цикл продолжает свою работу, пока значение логического
Таким образом, цикл продолжает свою работу, пока значение логического			выражения остается ложным.
выражения остается истинным.			Тело цикла с постусловием выполняется всегда хотя бы один раз.
	Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	27		Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	28

Кафедра			Кафедра	Базовые алгоритмические структуры
информатикиБазовые алгоритмические структуры		УГАТУ	информатики						УГАТУ
			Пример.
Чтобы циклы с условием успешно			Графическая форма
завершились необходимо, чтобы в теле			представление
			алгоритма Евклида
цикла был хотя бы один оператор,
			для нахождения
изменяющий значения, входящих в			наибольшего
логическое выражение переменных.			общего делителя
			(НОД) двух целых
			положительных
			чисел m и n.
Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	29		Информатика	ФАП - 2, ФАТС – 2, 3		курс 1,	семестр 2, 2009 г.	30
Кафедра	Вложенные циклы		Кафедра		Вложенные циклы
информатики			информатики
		УГАТУ							УГАТУ
Если телом цикла является циклическая			Пример. Вычислить
				произведение
структура, то такие циклы называют
вложенными. Тип циклов при этом				n	m	i
				∏ ∏
может быть любым.
				i=1	j =1 1 + j 2
При построении вложенных циклических
структур всегда следует соблюдать				Внутренний
				блок
правило: все блоки внутреннего цикла
должны полностью лежать в теле			Внешний
внешнего цикла.
				блок
Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	31		Информатика	ФАП - 2, ФАТС – 2, 3		курс 1,	семестр 2, 2009 г.	32

	Кафедра	Массивы		Кафедра	Массивы
	информатики			информатики
			УГАТУ			УГАТУ
	Многие задачи связаны с обработкой больших объемов			Массив — это упорядоченная совокупность однотипных
	информации, представляющей совокупность данных,			данных, с каждым из которых связан упорядоченный набор
				целых чисел, называемых индексами.
	объединенных единым математическим содержанием
				Работа с массивом сводится к действиям над его элементами.
	или связанных между собой по смыслу. Такие данные
	удобно представлять в виде линейных или			Индексы определяют положение элемента в массиве.
	прямоугольных таблиц.			Число индексов определяет размерность массива. Элемент
	В линейной таблице каждому ее элементу соответствует			одномерного массива обозначается переменной с одним
	порядковый номер. Для элемента прямоугольной			индексом. Элемент двумерного массива обозначается
	таблицы должны быть указаны два номера:			переменной с двумя индексами. Первый индекс обозначает
	номер по вертикали (номер строки) и номер по			номер строки, а второй – номер столбца.
				Таким образом, для обращения к конкретному элементу
	горизонтали (номер столбца).
	В алгоритмах для представления таких данных			массива необходимо указать имя массива и значения
	используются массивы.			индексов:	Ai ; Bi, j
	Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	33	Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	34
	Кафедра	Массивы		Кафедра Языки программирования как разновидность
	информатики			информатики	алгоритмических языков
			УГАТУ			УГАТУ
	Задача. В одномерном массиве чисел аi (i = 1, 2, …, N) найти			Для того чтобы с помощью ЭВМ можно было решить
	сумму чисел с нечетными индексами (s1) и среднее
	арифметическое чисел с четными индексами (s2)			конкретную задачу, недостаточно составить алгоритм
				ее решения, необходимо записать данный алгоритм
		Формирование одномерного массива		на одном из языков программирования.
				Языки программирования также как и алгоритмические
		Обработка одномерного массива		языки относятся к формальным языкам, более того,
				языки программирования можно рассматривать как
				некоторую разновидность алгоритмических языков.
				Общим для языков программирования и
				алгоритмических языков является возможность
				представления с их помощью некоторого алгоритма в
				форме, понятной исполнителю.
				В данном случае исполнителем алгоритма будет
				компьютер.
	Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	35	Информатика	ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	36

	Кафедра Языки программирования как разновидность							Кафедра
	информатики							Этапы подготовки и решения задач на компьютере
		алгоритмических языков						информатики
				УГАТУ					УГАТУ
			Dim m as integer, n as integer					Процесс решения любой практической
	Представление		m = Val(InputBox("m ?"))
	алгоритма Евклида		n = Val(InputBox("n ?"))					задачи на компьютере включает в себя
	для нахождения
	наибольшего общего		Do					три основных этапа:
	делителя (НОД) двух		If m > n Then
	целых							- Постановка задачи;
			m = m Mod n
	положительных чисел
	m и n.		Else					- Составление алгоритма ее решения;
	на языке		n = n Mod m
	программирования		End If					- Составление программы ее решения
			Loop While (m <> 0) And (n <> 0)					на ПК.
			If m = 0 Then d = n Else d = m
			Print "НОД="; d
	Информатика ФАП - 2, ФАТС – 2, 3		курс 1, семестр 2, 2009 г.	37				Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	38

Кафедра	Этапы подготовки и решения задач на компьютере	Кафедра	Этапы подготовки и решения задач на компьютере
информатики		информатики
	УГАТУ		УГАТУ

Постановка задачи			Составление алгоритма
Этот этап решения задач начинается со словесного или содержательного			После завершения этапа постановки задачи приступают
описания задачи.
			к выбору метода решения задачи и
Далее приступают к формальной или математической постановке
			непосредственному составлению алгоритма, в
решаемой задачи. Математическая формулировка заключается в
			процессе его выполнения устанавливается
записи условия задачи с помощью математических обозначений,
формул, зависимостей, в определении исходных данных и формы			необходимая последовательность арифметических и
выдачи результатов вычислений. Задача должна быть сформулирована			логических действий с помощью которых может быть
четко и однозначно.
			реализован выбранный метод.
Формальную или математическую постановку задачи всегда начинают с
четкого выяснения, какие конкретно исходные данные и знания следует			Составленный алгоритм может быть представлен в виде
использовать, какие конкретно результаты требуется получить.			словесного описание хода решения (на языке
Так в задачах вычислительного характера исходные данные чаще всего
			псевдокодов) или в виде блок-схемы, графически
представляются в виде чисел, искомые результаты также в виде			иллюстрирующий процесс решения.
набора чисел, таблиц, графиков или рисунков.
Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	39		Информатика ФАП - 2, ФАТС – 2, 3 курс 1, семестр 2, 2009 г.	40