2020-10-11
948
Лабораторная работа №1
Алгоритмы и блок-схемы
Теоретическое описание:
1. Понятие и свойства алгоритмов
Алгоритм - заранее определенное, точное предписание, которое задает дискретный (пошаговый) процесс, начинающийся определенным образом и приводящий к результату за конечное число шагов.
Свойства алгоритмов
Алгоритм должен быть составлен таким образом, чтобы исполнитель, в расчете на которого он создан, мог однозначно и точно следовать командам алгоритма и эффективно получать определенный результат. Это накладывает на записи алгоритмов ряд обязательных требований, суть которых вытекает из рассмотренного выше неформального понятия алгоритма. Эти требования представляются в виде следующих свойств:
I. Дискретность
Описываемый алгоритмом процесс должен быть разбит на последовательность отдельных шагов. Возникающая в результате такого разбиения запись представляет собой упорядоченную совокупность четко отделенных друг от друга предписаний (директив, команд, операторов), образующих прерывную (дискретную) структуру алгоритма. Таким образом, в начальный момент задаётся исходная ситуация, а после каждого следующего шага ситуация преобразуется на основе данных, полученные за предшествующие шаги обработки. Дискретность алгоритма означает, что он исполняется по шагам: каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
|
|
|
II.Понятность
Алгоритм должен быть понятен не только автору, но и исполнителю. Каждый шаг алгоритма обязательно представляет собой какое-либо допустимое действие исполнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель может понять и исполнить, а какие – нет.
III. Определённость (детерминированность)
Алгоритм не должен содержать предписаний, смысл которых может восприниматься неоднозначно. Запись алгоритма должна быть четкой, полной и детализированной настолько, чтобы у исполнителя не возникло потребности в принятии решений, не предусмотренных составителем алгоритма. Оно означает, что на каждом шаге однозначно определено преобразование объектов среды исполнителя, полученных на предшествующих шагах алгоритма. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной команды исполнителю неясно, какая из команд алгоритма должна исполняться на следующем шаге.
IV. Результативность
Это свойство подразумевает, что каждый шаг (и алгоритм в целом) после своего завершения даёт среду, в которой все имеющиеся объекты однозначно определены. При этом процесс прекращается за конечное число шагов. Если по каким-либо причинам решение получить невозможно, то алгоритм должен сообщать, что решение задачи не существует. Здесь уместно вспомнить, что «Отсутствие результата – тоже результат».
|
|
|
V. Массовость
Оно означает, что имеется некоторое множество данных, которые могут обрабатываться алгоритмом. Массовость предполагает, что алгоритм даст результат для любых исходных данных из некоторого их множества. Наиболее распространены алгоритмы, которые обеспечивают решение не одной конкретной задачи, а некоторого класса задач данного типа.
Такие характеристики – общие свойства вычислительных алгоритмов (численных, экономических, вероятностных и т.д.) и не вычислительных (игровых, информационных, интуитивных и прочих).
2. Понятие «исполнитель»
Каждый алгоритм предназначен для определённого исполнителя.
Исполнитель — это некоторый объект (человек, животное, техническое устройство), способный выполнять определённый набор команд.
Различают формальных и неформальных исполнителей. Формальный исполнитель одну и ту же команду всегда выполняет одинаково. Неформальный исполнитель может выполнять команду по-разному.
Примеры исполнителей
Есть много различных учебных исполнителей, придуманных для занятий по информатике. У них разные, часто забавные названия: Черепашка, Робот, Чертежник, Кенгуренок, Пылесосик, Муравей, Кукарача и др. Одни исполнители создают рисунки на экране, другие складывают слова из кубиков с буквами, третьи перетаскивают предметы из одного места в другое. Все эти исполнители управляются программным путем. Любому из них свойственна определенная среда деятельности, система команд управления, режимы работы. С помощью каждого из таких исполнителей можно учиться строить алгоритмы управления.
Пример 1. Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии.
Система команд Черепашки состоит из следующих команд:
1. Вперёд n (где n — целое число) — вызывает передвижение Черепашки на п шагов в направлении движения — в том направлении, куда развёрнуты её голова и корпус;
2. Направо m (где m — целое число) — вызывает изменение направления движения Черепашки на т градусов по часовой стрелке.
Запись Повтори k [<Команда1> <Команда2>... <Командаn>] означает, что последовательность команд в скобках повторится k раз.
Подумайте, какая фигура появится на экране после выполнения Черепашкой следующего алгоритма.
Повтори 12 [Направо 45 Вперёд 20 Направо 45]
3. Формы представления алгоритмов
В описании формальных языков в представлении алгоритмов можно выделить две основные формы: символьную (строчная, словесная) и графическую.
1. Символьная форма представления алгоритмов
Символьная запись представляет собой последовательность строк, каждая из которых содержит описание одного или нескольких действий. Для человека строчная алгоритмическая запись может быть приближена к естественному языку. Для технического устройства запись производится на специализированном формализованном языке. Недостатком строчной формы представления алгоритма является неудобство целостного восприятия его логической структуры.
Виды символьного представления алгоритма
Пошагово-словесная форма представляет собой пронумерованную последовательность строк, каждая из которых содержит описания конкретных действий на естественном языке. Данная форма применяется в том случае, если исполнителем является человек (кулинарные рецепты, представляющие порядок действий; алгоритм Евклида; действия, предлагаемые программной при установке программы; организация справки по какому-либо программному обеспечению и т.д.).
|
|
|
Пример 1: Алгоритм нахождения наибольшего общего делителя:
1. Если два числа равны, то наибольший общий делитель – их значение.
2. Большее число заменить на разность большего и меньшего
3. Вернуться к пункту 1.
Формула – строчная запись действий, обеспечивающих обработку числовых, символьных или логических данных (электронные таблицы, специализированные программы по обработке математических и статистических данных).
Псевдокод – ориентированный на исполнителя «человек» частично формализованный язык, позволяющий записывать алгоритмы в форме, близкой к языкам программирования высокого уровня.
В псевдокоде строго определены только правила записи управляющих структур, а описание самих действий остается естественным. Псевдокод имеет русскоязычную основу и используется, в основном, при обучении азам программирования. Близость конструкций псевдокода языкам программирования позволяет легко перейти от одного к другому.
Язык программирования – это совокупность набора символов (алфавита) системы, правил пользования (синтаксис) и истолкования конструкций из символов (семантика) для написания программ с использованием символов естественного языка. Язык программированияпредставляет собойискусственный формализованный язык, на котором записываются алгоритмы для исполнителя «компьютер». Языки программирования можно классифицировать по следующим признакам – уровню и функциональному назначению.
По уровню:
Языки низкого уровня:
1. Машинный язык – совокупность команд, интерпретируемых и исполняемых компьютером; каждый оператор программы является машинной командой, а все данные отыскиваются по абсолютным значениям адресов, по которым они располагаются в ОЗУ;
2. Язык ассемблера – язык символического кодирования – операторами языка являются машинные команды, которым приписываются мнемонические обозначения, а в качестве операндов используются не конкретные адреса в ОЗУ, а их символические имена.
Языки высокого уровня – ориентированы на систему операторов, характерных для записи определенного класса алгоритмов.
|
|
|
По функциональному назначению:
Проблемно-ориентированные. Примеры: FORTRAN (FORmula TRANslator) – научные и инженерные задачи; COBOL (Common Business Oriented Language) – экономические и коммерческие задачи; ЛИСП и Пролог – задачи искусственного интеллекта и др.
Универсальные. PASCAL (Philips Automatic Sequence CALculator), BASIC (Beginner ALL-purpose Symbolic Instruction Code), C, C++, Jawa, а также визуальные среды программирования DELPHI, VISUAL BASIC и др.
Пример 2:
| Задание | Решение |
| 1. Определить, что выводится на печать в результате выполнения следующего алгоритма, если А = 2.5; В = 0.5. 1) Начало 2) Список данных: А,В,Х,Y,Z – вещ. 3) Ввод(А,В) 4) Х:=А-В 5) Y:=А+В 6) Z:=Y*X 7) Z:=(10*B-Z)*(Z+1) 8) Вывод(X,Y,Z) 9) Конец | A = 2.5; B = 0.5 X = 2.5 – 0.5 = 2 Y = 2.5 + 0.5 = 3 Z = 2 * 3 = 6 Z = (10 * 0.5 – 6) * (6 +1) = -7 На экране появятся числа: 2, 3, -7 |
2. Определить какие значения примут переменные c и d после выполнения алгоритма, если
a = -5, b = 5.
1) если a*b<0 то c = a-b иначе c = a+b
2) если с<>0 то 
3) d = c*a.
| -5 * 5 < 0 (Да) → с = -5 – 5 = -10 -10 <> 0 (Да) → с = -10 / 10 = -1 d = -1 * (-5) = 5 |
Пример 3:
| Задание | Решение |
| 5. Определить, чему равны значения переменных a, b, s после выполнения приведённого фрагмента программы: a:=1; b:=1; while a+b<8 do begin a:=a+1; b:=b+2; end; s:=a+b; | a = 1; b = 1 1 круг цикла: 1 + 1 < 8 (Да) → a = 1 + 1 = 2; b = 1 + 2 = 3. 2 круг цикла: 2 + 3 < 8 (Да) → a = 2 + 1 = 3; b = 3 + 2 = 5. 3 круг цикла: 3 + 5 < 8 (Нет) → цикл завершился s = 3 + 5 = 8 |
| 6. Определить значения переменных X и Y, которые они получат в результате выполнения фрагмента алгоритма, если A = 3, B = 3, C = 4 if A>B then if B>C then begin X:=C*C; Y:=2*C; end else begin X:=B*B; Y:=B+C; end else begin if A<=C then begin X:=A*A; Y:=A+B-C; end else begin X:=C*C; Y:=C-B-A; end X:=X+1; Y:=Y-1; end; X:=X+2; | 3 > 3 (Нет) → 3<= 4 (Да) → X = 3 * 3 = 9; Y = 3 + 3 – 4 = 2 X = 9 + 1 = 10 Y = 2 – 1 = 1 X = 10 + 2 = 12 |
2. Графическая форма представления алгоритмов
Графическая форма представления называется блок-схема, в которой для представления отдельных блоков алгоритма используется обусловленный набор геометрических фигур. Графическая форма предназначена только для человека и главное достоинство – наглядность; блок-схема позволяет охватить весь алгоритм сразу, отследить различные варианты его выполнения. По блок-схеме гораздо проще осуществляется запись алгоритма на каком-либо формальном языке. Графическое представление конструкций формального языка (условные операторы, циклические операторы и т.д.) осуществляется посредствам синтаксических диаграмм.
Алгоритм решения задачи может быть представлен в виде словесного описания или графически – в виде блок схемы. Последний способ представления имеет ряд преимуществ, поскольку наглядность представления обеспечивает высокую читаемость алгоритма и позволяет программисту лучше уяснить последовательность действий, которые должны быть выполнены для решения, убедится в правильности понимания поставленной задачи.
Блок-схема – это ориентированный граф, указывающий порядок исполнения команд алгоритма.
При изображении алгоритма в виде блок схем стандартными являются специальные конструкции:
 |
Начало/конец Ввод/вывод Обработка Выбор
Вершины такого графа могут быть одного из трех типов и, в соответствии с введенными обозначениям можем представить их в виде:
1) Функциональная вершина (F), имеющая один вход и один выход;
2) Предикатная вершина (P), имеющая один вход и два выхода, в этом случае функция P передает управление по одной из ветвей в зависимости от значения P («Да» означает, значение P есть истина; «Нет», означает, значение P есть ложь, иногда вместо «Да» пишут «+», вместо «Нет» - «-»);
3) Объединяющая вершина (вершина «слияния») (U), обеспечивающая передачу управления от одного из двух входов к выходу.
Из данных элементарных блок-схем можно построить 4 блок-схемы, имеющих особое значение для практики алгоритмизации:
|
|
Композиция, или следование; альтернатива, или ветвление; итерация, или цикл, с предусловием или постусловием.
Блок-схема альтернатива может иметь и сокращенную форму, в которой отсутствует ветвь F2. Развитием блок-схемы альтернатива является блок-схема выбор. Об этих схемах речь пойдет далее.
На практике при составлении блок-схем удобно использовать и другие графические знаки, например,
 |  |
Типовой процесс (обращение к процедуре) Подготовка к циклическому процессу
| 3. Определить, что выводится на печать в результате выполнения алгоритма, схема которого изображена на рисунке, если n = 5. |
Примеры:
1. Определить, что выводится на печать в результате выполнения алгоритма, схема которого изображена на рисунке, если n = 5
| |||||||
 | |||||||
| |||||||
| |||||||
| |||||||
| 2. Определить, что выводится на печать в результате выполнения алгоритма, схема которого изображена на рисунке, если X = -6. |
 | |||||
 | |||||
| |||||
| |||||
3. Определить, что выводится на печать в результате выполнения алгоритма, схема которого изображена на рисунке, если x =
|
 | |||||
| |||||
| |||||
| |||||
3. Базовые алгоритмические конструкциии
а) Линейные алгоритмы
Линейный – несколько функциональных блоков выполняются последовательно, кроме того, каждый блок обязательно выполняется и не более одного раза.
Пример 1: Навстречу друг другу бежали две антилопы гну. Скорость одной антилопы 60 км/ч, а скорость другой 55 км/ч. Через сколько часов они встретятся, если первоначальное расстояние между ними равно 230 км?
(V1=70, 320, 50; V2=60, 450, 55; S=1300, 1540, 315)
Составить алгоритм решения задачи.
Решение:
1. Найти сумму скоростей
2. Разделить данное расстояние на сумму скоростей
В алгоритмическом языке линейным является алгоритм, состоящий из последовательности простых команд (ввода/вывода и присваивания). В записи алгоритма они располагаются в том порядке, в каком должны быть выполнены предписываемые им действия. Такой порядок выполнения называется естественным. Последовательность команд образует составную команду «цепочка», которая в записи псевдокодом и блок-схемой имеет вид:
|
Команда 2
…
|
 |
|
В математике к линейным алгоритмам относятся алгоритмы, представленные формулами.
