Тема: Основы алгоритмизации.

РЕСПУБЛИКА КАЗАХСТАН

УНИВЕРСИТЕТ «ТУРАН»

Абуов Е.Э.

Учебно-методический комплекс по дисциплине «Информатика»

Раздел:
«Основы алгоритмизации»

Краткий конспект лекций

Методические материалы для лабораторных занятий

Методические рекомендации по СРСП и СРС

Для студентов специальности 050703 – «Информационные системы»

АЛМАТЫ, 2005

Учебно-методический комплекс составлен старшим преподавателем Абуовым Е.Э. на основании государственного стандарта образования по направлению подготовки специальности 050703-«Информационные системы» в соответствии с рабочим учебным планом специальности, утвержденным
«___» ______________ 2005 г.

Рассмотрено на заседании кафедры информационные технологий.

«___» _________________ 2005 г. Протокол №___.

Зав. кафедрой информационных технологий _______________ Тусупова С.А.

Одобрено на заседании Учебно-методического совета университета.

«___» _________________ 2005 г. Протокол №___.

Председатель _______________ Тазабеков К.А.

Содержание

Краткий конспект лекции №11............................................................................................................. 4

Методические материалы для практического занятия №11............................................................ 14

Методические рекомендации по СРСП №11.................................................................................... 21

Методические рекомендации по СРС №11....................................................................................... 23

Краткий конспект лекции №11

Тема: Основы алгоритмизации.

Количество часов: 1.

Понятие алгоритма

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

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

Само слово " алгоритм" происходит от латинского слова algorithmi, которое является латинским изображением арабского имени хорезмийского математика IX века аль-Хорезми. В Европе это слово отождествлялось с описанной в трактате аль-Хорезми десятичной системой счисления и искусством счета в ней. В настоящее время правила выполнения арифметических операций в десятичной системе счисления являются лишь простейшими примерами вычислительных процессов.

С современной точки зрения слово " алгоритм" означает точное описание некоторого процесса (не обязательно вычислительного), инструкцию по его выполнению.

Исполнители алгоритмов

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

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

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

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

q Дискретность – предусматривает разбиение процесса обработки информации на более простые этапы (шаги выполнения), выполнение которых человеком или компьютером не вызывает затруднений.

q Понятность. В алгоритм можно включать команды только из системы команд данного исполнителя.

q Определенность (или детерминированность) — характеризует однозначность выполнения каждого отдельного шага преобразования информации. Например, робот будет поставлен в тупик командой " Взять две-три ложки песка": что значит " две-три"?, какого песка?

q Результативность (или конечность) – предполагает завершение работы алгоритма в целом за конечное число шагов;

q Массовость – характеризует пригодность алгоритма для решения определенного класса задач.

Этапы решения задачи на компьютере

Процесс решения задачи на компьютере включает в себя следующие основные этапы:

1. Постановка задачи.

2. Выбор метода решения (построение математической модели).

3. Разработка алгоритма.

4. Составление программы.

5. Реализация программы на компьютере.

6. Анализ полученных результатов.

Постановка задачи

Прежде чем решать задачу на компьютере, необходимо четко определить, чем мы располагаем — какие есть исходные данные, каковы ограничения на них, что будет являться решением задачи. Если задача конкретная (например, надо решить уравнение 2х² + 3х + 5 = 0, где коэффициенты уравнения — константы), то под постановкой задачи понимаем ответ на вопросы:

q какие исходные данные известны;

q что требуется определить.

Если задача обобщенная (например, надо решить квадратное уравнение aх² + bх + c = 0), то отвечать при постановке задачи понадобится еще на третий вопрос: какие данные допустимы. Итак, постановка задачи " решить квадратное уравнение aх² + bх + c = 0" выглядит следующим образом:

Дано: a, b, c — коэффициенты уравнения.

Требуется: x₁, x₂ — корни уравнения. Ограничения: a ¹ 0. D = b² - 4ac ³ 0.

Выбор метода решения (построение математической модели)

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

Разработка алгоритма

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

Составление программы

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

Реализация программы на компьютере

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

Анализ полученных результатов

Как определить, что результаты работы программы соответствуют данной задаче? Для этого в зависимости от класса решаемой задачи применяют разные подходы:

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

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

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

Пояснение к алгоритму

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

Запросить значение переменной R

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

< имя переменной> : = < выражение>

Принцип действия команды присваивания: переменной, имя которой стоит слева от знака присваивания «: =», присваивается значение выражения, стоящего справа от знака присваивания. При этом «старое» значение переменной стирается.

Команда вывода позволяет вывести данные на внешнее устройство — файл на диске, дисплей, принтер. В данном алгоритме присутствует одна команда вывода:

Вывести значение переменной S

Графическая форма представления (применима для алгоритмов всех типов) основана на замене типичных алгоритмических команд определенными геометрическими фигурами — блоками.

Таблица 2. Основные элементы блок-схемы

БЛОК	НАЗНАЧЕНИЕ
	Начало / Конец
	Действие Этот блок содержит команду присваивания, например:
	Ввод-Вывод Блок ввода изображается в виде параллелограмма, в котором находится знак вопроса и имя переменной, значение которой надо получить. Блок ввода изображается в виде параллелограмма, в котором через запятую перечисляются параметры вывода. В качестве параметров могут выступать константы, переменные и выражения (выводятся значения переменных и выражений). Строковые константы помещаются между знаками апострофа.

Примеры использования

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

Если значение переменной sum было равно 5, то в результате выполнения команды:

будет выведено: Сумма двух чисел равна 5

Алгоритм решения нашей задачи при графической форме представления приведен на Рис. 1.

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

Циклический тип алгоритма. Алгоритм, составленный с использованием многократных повторений одних и тех же действий (циклов), называется циклическим. Такой алгоритм реализует решение очень многих задач. Форма представления для такого алгоритма может быть выбрана как словесная, так и графическая.

На практике чаще всего встречаются алгоритмы как бы смешанного типа, у которых можно выделить участки (блоки), имеющие структуру линейного, ветвящегося или циклического типа. Более того, отметим, что алгоритм любой степени сложности можно построить с помощью блоков основного базового набора, имеющих линейную (последовательную), разветвляющуюся (ветвящуюся) или циклическую структуру. Каждая из этих структур имеет только один вход и только один выход, что позволяет соединять между собой в процессе разработки алгоритма любое количество элементов базовых структур в любой последовательности.

Рис. 1

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

Конец ветвления

Вывести значение переменной у

Конец

Общий вид полной условной конструкции, реализующей ветвление при графическом представлении алгоритма, изображен на Рис. 3. Здесь Q — проверяемое условие; Т — действие, которое должно быть выполнено в случае истинности условия Q (положительная ветвь ветвления); Р — действие, выполняемое, если условие Q ложно (отрицательная ветвь ветвления).

Рис. 3

Рис. 4

При словесном представлении алгоритма полная условная конструкция реализуется командой ветвления вида:

Если Q

то

Иначе

Конец ветвления

Но возможен и другой вариант — неполная условная конструкция (Рис. 4), достаточно часто встречающаяся при решении задач.

При словесном представлении алгоритма ей отвечает команда ветвления:

Если Q

то

Конец ветвления

Циклические алгоритмы

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

Однако " неоднократно" не значит " до бесконечности". Организация циклов, никогда не приводящая к остановке в выполнении алгоритма (так называемое " зацикливание" ), является нарушением требования его результативности — получения результата за конечное число шагов.

Рассмотрим графическое представление циклического блока алгоритма (Рис. 5). В него входят в качестве базовых следующие структуры: логический элемент с проверкой условия Q и блок S, называемый телом цикла. Здесь тело цикла S расположено после проверки условия Q (цикл с предусловием), поэтому может случиться, что при определенных условиях блок S не выполнится ни разу. Такой вариант организации цикла, управляемый предусловием, называется цикл-пока.

Рис. 5

При словесном представлении алгоритма команда, организующая повторение в цикле-пока имеет вид:

Пока Q повторять

Конец цикла

Таким образом, если Q не выполняется, то предусмотрен выход из цикла на команду, записанную после строки " Конец цикла". Здесь условие Q — это условие на продолжение цикла.

Возможен другой случай, когда тело цикла S выполняется, по крайней мере, один раз и будет повторяться до тех пор, пока не выполнится условие Q (Рис. 6). Такая организация цикла, когда тело цикла, расположено перед проверкой условия Q, носит название цикла с постусловием или цикла-до. Истинность условия Q в этом случае — причина окончания цикла. Команда, организующая цикл-до, приведена ниже:

Рис. 6

Повторять S пока не Q Конец цикла

ЛинеЙныЕ алгоритмЫ

Упражнение 1

Задача. Найти сумму двух данных чисел.

Дано: a, b — слагаемые.

Требуется: sum — сумма значений а и b.

Метод решения: sum = a + b.

Словесная форма алгоритма:

Запросить значение переменной а

Запросить значение переменной b

Записать в переменную sum значение выражения a+b

Вывести значение переменной sum

Блок-схема:

Упражнение 2

Задача. Даны два числа, являющиеся величинами катетов некоторого прямоугольного треугольника. Вычислить длину гипотенузы этого треугольника.

Дано: x и y — катеты прямоугольного треугольника.

Требуется: z — гипотенуза прямоугольного треугольника.

Метод решения: z = .

Словесная форма алгоритма:

Запросить значение переменной x

Запросить значение переменной y

Вывести значение переменной z

Блок-схема:

РазветвляющиЕСЯ алгоритмЫ

Упражнение 3

Задача. Найти максимум из двух чисел.

Дано: a, b — заданные числа.

Требуется: max — максимум из чисел а и b.

Метод решения: если a> b, то max присвоить a, иначе b.

Словесная форма записи алгоритма:

Запросить значение переменной a

Запросить значение переменной b

Если a > b, то max : = a, иначе max: = b

Вывести значение переменной max

Блок-схема:

Упражнение 4

Задача. Найти максимум из трех чисел.

Дано: Переменные a, b, с.

Требуется: max — максимум из чисел а, b, с.

Метод решения. Если a> b, то max: =a, иначе max: =b. Если c> max, то max: =c.

Словесная форма записи алгоритма:

Запросить значение переменной a

Запросить значение переменной b

Запросить значение переменной c

Если a > b, то max: = a, иначе max : = b

Если c > max, то max : = c

Вывести значение переменной max

Блок-схема:

ЦиклическиЕ алгоритмЫ

Упражнение 5

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

Дано: n — количество первых натуральных чисел.

Требуется: S = 1 + 2 + …+ n — сумма первых n натуральных чисел.

Метод решения: S_n = S_n_-1 + n.

Словесная форма записи алгоритма:

Запросить значение переменной n

i: =1

S: =0

Пока i< =n повторять

S: = S+i

i: = i+1

Конец цикла

Вывести значение переменной S

Блок-схема:

Тестирование алгоритма

Зададим количество суммируемых первых натуральных чисел n = 5. Мы должны получить значение суммы первых пяти натуральных чисел S = 15. Проведем трассировку алгоритма и запишем значения переменных i и S на каждом шаге в таблицу.

До входа в цикл:	S: =0	i: =1
РАБОТА ЦИКЛА
iна входе в тело цикла	Условие цикла	S	iна выходе из тела цикла
1	1≤ 5? ДА	S: =S+i	0+1 = 1® S	i: =i+1	1 +1=2® i
	2≤ 5? ДА	S: =S+i		i: =i+1
1+2 = 3® S	2 +1 =3® i
	3≤ 5? ДА	S: =S+i		i: =i+1
3+3 = 6 ® S	3 +1 =4® i
	4≤ 5? ДА	S: =S+i		i: =i+1
6+4 = 10® S	4 +1 =5® i
	5≤ 5? ДА	S: =S+i		i: =i+1
10+5 = 15® S	5 +1 =6® i
	6≤ 5? НЕТ	ВЫХОД ИЗ ЦИКЛА

Упражнение 6

Задача.Дано n чисел. Найти их сумму.

Дано: n — количество чисел; х₁, х₂, ..., х_n — числа, вводимые пользователем

Требуется: S = x₁ + x₂ + …+ x_n — сумма n чисел.

Метод решения: S_n = S_n_-1 + x_n.

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

Словесная форма записи алгоритма:

Запросить значение переменной n

i: =1

S: =0

Пока i < = n повторять

Запросить x

S : = S + x

i : = i +1

Конец цикла

Вывести значение переменной S

Блок-схема:

Методические рекомендации по СРСП №11

РЕСПУБЛИКА КАЗАХСТАН

УНИВЕРСИТЕТ «ТУРАН»

Абуов Е.Э.

Учебно-методический комплекс по дисциплине «Информатика»

Раздел:
«Основы алгоритмизации»

Содержание

Краткий конспект лекции №11............................................................................................................. 4

Методические материалы для практического занятия №11............................................................ 14

Методические рекомендации по СРСП №11.................................................................................... 21

Методические рекомендации по СРС №11....................................................................................... 23

Краткий конспект лекции №11

Тема: Основы алгоритмизации.

Количество часов: 1.

Понятие алгоритма

Исполнители алгоритмов

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

q Понятность. В алгоритм можно включать команды только из системы команд данного исполнителя.

q Массовость – характеризует пригодность алгоритма для решения определенного класса задач.

12 3 4 5 Следующая ⇒