Цель работы : изучение графического способа описания алгоритма решения задачи.
Задачи работы :
ознакомиться с основными способами представления алгоритмов;
освоить графический способ описания алгоритмов.
1.1. Порядок выполнения работы
Изучите теоретические сведения по теме данного раздела (п. 1.2)
Ознакомьтесь с постановкой задачи (п. 1.3). Вариант задания соответствует вашему номеру в списке группы.
Разработайте блок-схему алгоритма решения поставленной задачи.
Ответьте на контрольные вопросы.
Подготовьте отчет о выполнении практической работы, который должен содержать:
цель практической работы;
блок-схему алгоритма решения поставленной задачи;
ответы на контрольные вопросы;
выводы по практической работе.
1.2. Общие сведения
Одним из наиболее трудоемких этапов решения задачи на ЭВМ является разработка алгоритма.
Под алгоритмом понимается точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату.
Основы программирования. Алгоритмы и блок-схемы. Урок 6 [GeekBrains]
Основными характерными свойствами алгоритма являются:
детерминированность (определенность) – при заданных исходных данных обеспечивается однозначность искомого результата;
массовость – пригодность для задач данного типа при исходных данных, принадлежащих заданному подмножеству;
результативность – реализуемый вычислительный процесс выполняется за конечное число этапов с выдачей осмысленного результата;
дискретность – возможность разбиения алгоритма на отдельные этапы, выполнение которых не вызывает сомнений.
Выделяют следующие типы вычислительных процессов :
Линейный вычислительный процесс.
Для получения результата необходимо выполнить некоторые операции в определенной последовательности.
Разветвленный вычислительный процесс.
Конкретная последовательность операций зависит от значений одного или нескольких параметров. Например, если дискриминант квадратного уравнения не отрицателен, то уравнение имеет два корня, а если отрицателен, то действительных корней нет.
Циклический вычислительный процесс
Для получения результата некоторую последовательность действий необходимо выполнить несколько раз. Например, для того, чтобы получить таблицу значений функции на заданном интервале изменения аргумента с заданным шагом, необходимо соответствующее количество раз определить следующее значение аргумента и посчитать для него значение функции.
В свою очередь, существуют также несколько типов циклического вычислительного процесса , а именно:
Счетные циклы (циклы с заданным количеством повторений) – это циклические процессы, для которых количество повторений известно.
Итерационные циклы – это циклические процессы, завершающиеся по достижении или нарушении некоторых условий.
Поисковые циклы – это циклические процессы, из которых возможны два варианта выхода:
Выход по завершению процесса;
Урок по работе с Visio
Досрочный выход по какому-либо дополнительному условию.
По типу вычислительного процесса, реализуемого алгоритмом, различают:
Алгоритмы линейной структуры;
Алгоритмы разветвленной структуры;
Алгоритмы циклической структуры.
Алгоритмы решения практических задач обычно имеют комбинированную структуру, то есть включают в себя все три типа вычислительных процессов.
К изобразительным средствам описания алгоритмов относятся следующие основные способы их представления:
Словесный (записи на естественном языке);
Структурно-стилизованный (записи на алгоритмическом языке и псевдокод);
Графический (изображение схем и графических символов);
Программный (тексты на языках программирования).
Словесный способ описания алгоритма представляет собой описание последовательных пронумерованных этапов обработки данных и задается в произвольном изложении на естественном языке.
Алгоритм сложения двух чисел (a и b).
Спросить, чему равно число a.
Спросить, чему равно число b.
Сложить a и b, результат присвоить с.
Сообщить результат с.
Достоинством данного способа является простота описания, а к недостаткам можно отнести то, что такой подход многословен и не имеет строгой формализации, поэтому допускает неоднозначность толкования отдельных предписаний, в силу чего словесный способ представления алгоритма не имеет широкого распространения.
Для строгого задания различных структур данных и алгоритмов их обработки требуется иметь такую систему формальных обозначений и правил, чтобы смысл всякого используемого предписания трактовался точно и однозначно. Соответствующие системы правил называются языками описаний . К ним относятся алгоритмические языки (псевдокоды), блок-схемы и языки программирования.
Структурно-стилизованный способ описания алгоритма основан на записи алгоритмов в формализованном представлении предписаний, задаваемых путем использования ограниченного набора типовых синтаксических конструкций, называемых часто псевдокодами.
Достоинством псевдокодов является близость к языкам программирования, а недостатками, в свою очередь, являются сложность освоения и невозможность непосредственного ввода алгоритма для решения на ЭВМ, т.е. необходимость перевода на язык программирования.
Графический способ описания алгоритма предполагает, что для описания структуры алгоритма используется совокупность графических изображений (блоков), соединяемых линиями передачи управления. Такое изображение называется методом блок-схем .
Блок-схема алгоритма – это графическое представление хода решения задачи. Блок-схема состоит из блоков, соединенных линиями, а блоки изображаются в виде геометрических фигур, называемых символами. Внутри символов записываются указания о выполняемых блоком функциях – формулы, текст, логические выражения.
Вид символов и правила выполнения блок-схем стандартизированы – ГОСТ 19.701-90 содержит перечень символов, их наименования, отображаемые функции, формы и размеры, а также правила выполнения схем. При разработке алгоритма каждое действие обозначают соответствующим блоком, показывая их последовательность линиями со стрелками на конце. Названия, обозначения и назначение элементов блок-схем приводится на рис. 1.1.
Рисунок 1.1 – Основные блоки
Следует упомянуть некоторые основные правила выполнения блок-схем, которыми надлежит руководствоваться при графическом описании алгоритмов. Начало алгоритмов отмечается символом «Терминатор», из которого выходит одна линия. В нем записывается слово «Пуск» («Начало»). Конец алгоритма отмечается этим же символом, в котором записывается слово «Останов» («Конец»).
В этом случае данный символ не имеет ни одной выходной линии, а на него может замыкаться одна или более линий. Символ “Процесс” может иметь одну или несколько входных линий и только одну выходную. Внутри символа может быть записано несколько предписаний – в этом случае они выполняются в порядке записи. Представление отдельных операций достаточно свободно. Для обозначения вычислений можно использовать математические выражения, для пересылки данных – стрелки, для других действий – пояснения на естественном языке, например, А: = Х + 4; i: = i + 1, ––> B.
Линии потока должны быть параллельны сторонам листа. Основные направления линий потока – сверху вниз и слева направо – стрелкой не обозначаются. В других случаях на конце линии потока ставится стрелка, а в месте слияния линий ставится точка. Если блок-схема не умещается на одном листе, используют соединители. При переходе на другой лист или получении управления с другого листа в комментарии указывается номер листа, например «с листа 3» «на лист 1».
Для записи алгоритма любой сложности достаточно трех базовых структур :
следование — обозначает последовательное выполнение действий (рис. 1.2, а);
ветвление — соответствует выбору одного из двух вариантов действий (рис. 1.2, б);
цикл-пока — определяет повторение действий, пока не будет нарушено условие, выполнение которого проверяется в начале цикла (рис. 1.2, в).
Рисунок 1.2 – Базовые алгоритмические структуры
Кроме этого, при описании алгоритмов используются дополнительные алгоритмические структуры , производные от базовых, каждая из которых может быть реализована через базовые структуры:
выбор — выбор одного варианта из нескольких в зависимости от значения некоторой величины (рис. 1.3, а, б);
цикл-до — повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле (рис. 1.3, в, г);
цикл с заданным числом повторений (счетный цикл ) – повторение некоторых действий указанное число раз (рис. 1.3, д, е).
Рисунок 1.3 – Реализация дополнительных алгоритмических структур
через базовые структуры
Рассмотрим примеры графического описания алгоритмов различных типов: линейного, разветвляющегося, циклического и комбинированного (рис. 1.4 – 1.7).
Пример 1.2. Линейный алгоритм.
Алгоритм вычисления значения выражения K=3b+6а (рис. 1.4) .
Рисунок 1.4 – Пример блок-схемы линейного алгоритма
Пример 1.3. Разветвляющийся алгоритм.
Алгоритм, определяющий, пройдет ли график функции y=3x+4 через точку с координатами x1,y1 (рис. 1.5).
Рисунок 1.5 – Пример блок-схемы разветвляющегося алгоритма
Пример 1.4. Циклический алгоритм.
Алгоритм, определяющий факториал натурального числа n (рис. 1.6):
n ! = 1*2*3*….*(n -1)* n
Рисунок 1.6 – Пример блок-схемы циклического алгоритма
Пример 1.5. Комбинированный алгоритм.
Необходимо определить наибольший общий делитель двух натуральных чисел А и В.
Для решения поставленной задачи используем алгоритм Евклида, который заключается в последовательной замене большего из чисел на разность большего и меньшего, пока числа не станут равны. Рассмотрим данный алгоритм на двух примерах.
Пример (а): А=225, В=125. Применяя алгоритм Евклида, получаем для А и В наибольший общий делитель, равный 25.
Пример (б): А=13, В=4. В этом случае наибольший общий делитель А и В равен 1.
Блок-схема алгоритма Евклида для нахождения наибольшего общего делителя двух натуральных чисел показана на рис. 1.7.
Рисунок 1.7 – Пример блок-схемы комбинированного алгоритма
Блок-схема алгоритма детально отображает все особенности разработанного алгоритма, но иногда такой высокий уровень детализации не позволяет выделить суть алгоритма. В этих случаях для описания алгоритма используют псевдокод . Псевдокод базируется на тех же основных структурах, что и структурные схемы алгоритма (табл. 1.1).
Пример 1.6. Описание алгоритма Евклида на псевдокоде .
Алгоритм Евклида:
цикл-пока А ≠ В
иначе В:= В — А
Конец алгоритма.
Таблица 1.1 – Пример псевдокода для записи базовых алгоритмических структур
Источник: redcomrade.ru
Основные алгоритмические структуры: следствие, ветвление, цикл
Основные алгоритмические структуры : следствие (линейный алгоритм), ветвление, цикл.
Другие примеры программ можно рассмотреть в презентации на тему – Блок-схемы алгоритмов и примеры программ на языке программирования
1. Линейный алгоритм – это такой, в котором все операции выполняются последовательно одна за другой (рис. 1.).
2. Разветвляющий алгоритм – это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий (рис.2).
3. В алгоритмической структуре “цикл” серия команд (тело цикла) выполняется многократно.
Цикл – составная команда алгоритма, в которой в зависимости от значения логического выражения возможно многократное выполнение действия (рис.3).
Характерной особенностью базовых структур является наличие в них одного входа и одного выхода.
Базовые структуры алгоритмов:
Неполная форма алгоритма ветвления выглядит следующим образом:
ЕСЛИ ТО
IF THEN
Полная форма алгоритма ветвления выглядит следующим образом:
ЕСЛИ ТО ИНАЧЕ
IF THEN ELSE
Если в комнате темно, тогда надо включить свет.
ЕСЛИ хочешь быть здоров, ТО закаляйся
ИНАЧЕ можешь часто болеть.
рис.3
Цикл с предусловием (иначе цикл пока) имеет вид:
Форматы записи операторов алгоритма
Блок-схема
Форматы записи операторов на Паскале
Пока (условие)
нц
серия команд
кц
while условие do
begin
серия команд;
end;
Цикл с постусловием (иначе цикл до) имеет вид:
Форматы записи операторов алгоритма
Блок-схема
Форматы записи операторов на Паскале
В алгоритмическом языке нет команды, которая могла бы описать данную структуру, но ее можно выразить с помощью других команд (Например, ветвления).
repeat серия команд
until условие
Цикл с параметром (иначе цикл для) имеет вид:
Форматы записи операторов алгоритма
Блок-схема
Форматы записи операторов на Паскале
Приведём примеры алгоритмов в виде блок-схем:
Пример: Алгоритм «Погода»
Словесная форма
Блок-схема
- определить температуру воздуха
- если температура ниже 0, то надеть шубу, иначе надеть куртку
конец
Вся программа состоит из команд (операторов). Команды бывают простые и составные (команды, внутри которых встречаются другие команды). Составные команды часто называют управляющими конструкциями.
Источник: anna-pavlovna.ru
Блок-схемное программирование. (Тема 1)
1.
Понятие алгоритма. Его свойства.
2.
Этапы решения задач на ЭВМ.
3.
Основы составления блок-схем.
4.
Алгоритмизация линейных процессов.
5.
Алгоритмизация разветвляющихся процессов.
6.
Алгоритмизация циклических процессов
7.
Задачи на обработку массивов
3. Вопрос 1. Понятие алгоритма. Его свойства
1.1. Понятие алгоритма
Алгоритм – (от лат. algorithmi) латинской формы написания имени
великого математика IX в. Аль Хорезми, который сформулировал правила
выполнения арифметических действий.
Алгоритм – это точное предписание о выполнении в определенном порядке
некоторой системы операций для получения решения данной задачи.
Алгоритмизация – процесс разработки алгоритма (плана действий) для решения
задачи
СПОСОБЫ
СПОСОБЫ
ЗАДАНИЯАЛГОРИТМОВ
АЛГОРИТМОВ
ЗАДАНИЯ
Словесный
Словесный
(многословность,
(многословность,
неоднозначность)
неоднозначность)
Табличный
Табличный
(физика,химия,
химия,…)
…)
(физика,
Граничный
Граничный
(блок-схемы)
(блок-схемы)
4.
1.2. Свойства алгоритма
Свойстваалгоритма
алгоритма
Свойства
Однозначностьалгоритма
алгоритма- -единственность
единственностьтолкования
толкованияисполнителем
исполнителемправила
правилапостроения
построениядействий
действий
Однозначность
порядоких
ихвыполнения.
выполнения.
иипорядок
Конечностьалгоритма
алгоритма- -обязательность
обязательностьзавершения
завершениякаждого
каждогоиз
издействий,
действий,составляющих
составляющихалгоритм,
алгоритм,ии
Конечность
завершимостьвыполнения
выполненияалгоритма
алгоритмаввцелом.
целом.
завершимость
Результативность алгоритма
алгоритма — -предполагающая,
предполагающая, что
что выполнение
выполнение алгоритма
алгоритма должно
должно завершиться
завершиться
Результативность
получением
определённых
результатов.
получением определённых результатов.
Массовость — — т.т. е.е. возможность
возможность применения
применения данного
данного алгоритма
алгоритма для
для решения
решения целого
целого класса
класса задач,
задач,
Массовость
отвечающихобщей
общейпостановке
постановкезадачи.
задачи.
отвечающих
Правильность алгоритма
алгоритма — — под
под которой
которой понимается
понимается способность
способность алгоритма
алгоритма давать
давать правильные
правильные
Правильность
результаты
решения
поставленных
задач.
результаты решения поставленных задач.
Эффективность — — для
для решения
решения задачи
задачи должны
должны использоваться
использоваться ограниченные
ограниченные ресурсы
ресурсы компьютера
компьютера
Эффективность
(процессорноевремя,
время,объём
объёмоперативной
оперативнойпамяти
памятииит.т.д.).
д.).
(процессорное
5. Вопрос 2. Этапы решения задач на ЭВМ
Этап1.1.
Этап
Математическаяпостановка
постановказадачи
задачи
Математическая
Этап2.2.
Этап
Алгоритмизацияииблок-схема
блок-схема
Алгоритмизация
Этап3.3.
Этап
Написаниепрограммы
программы
Написание
Этап4.4.
Этап
Отладкапрограммы
программы
Отладка
Этап5.5.
Этап
Проверкаправильности
правильностиполученных
полученныхрезультатов
результатов
Проверка
Этап6.6.
Этап
Проведениевычислений
вычислений
Проведение
6. Вопрос 3. Основы составления блок-схем
Блок-схема – графическое изображение алгоритма.
Перечень основных графических блоков
0,5a
Блок начала, конца блок-схемы
b
a
Блок ввода/вывода
b
0.25
а
a
Блок вычислений
b
a
Логический блок
(блок разветвляющегося процесса)
b
a
Блок итераций
(блок циклического процесса с известным числом повторений)
b
7.
Вопрос 4. Алгоритмизация линейных процессов
Линейный процесс – процесс, действия в котором происходят
последовательно, друг за другом.
y 2
Пример 1. Составить блок-схему для вычисления величины:
начало
ввод a, b, c, x
y=2*(a*x+2*b)/(c*x+2*b)
вывод y
конец
ax 2b
cx 2b
8.
Пример 2. Вычислить Х, Y. Исходные данные: А = 557, B = 3, C = -20
X
A C B
C 2 B2
2
A C
,
B A
Y B2 X
C3
A B
C
3
Вывести значения Х, Y.
начало
А = 557
В=3
С = -20
X = abs(A+C+B)/(C*C+B*B)+(A+C*C)/(A+B)
Y=B*B*X+abs(C*C*C)/(A+B)+abs(C)*abs(C)*abs(C)
вывод
X, Y
.
конец
9.
Вопрос 5. Алгоритмизация разветвляющихся процессов
Разветвляющийся процесс – процесс, действия в котором происходят
по одной или другой ветви, в зависимости от условия.
Пример 3. Вычислить Z, если известно условие:
1 sin x , если x 0,5;
Z
1 x 3 , если x 0,5.
начало
Вывести значения в виде x, Z.
ввод x
+
x > 0,5
Z = abs(1 — sin(x))
–
Z = 1 + sqr(x*x*x)
вывод x, Z
конец
10.
1 sin x , если x 0,5;
Z 1 x 3 , если x 0,5;
x
2, если x 0,5.
1 x
Пример 4. Вычислить Z, если известно условие:
Вывести значения в виде x, Z.
начало
ввод x
+
x > 0,5
–
+
Z = abs(1 — sin(x))
Z = 1 + sqr(x*x*x)
вывод x, Z
конец
x < 0,5
–
Z = x/(1+x) + 2
11.
Вопрос 6. Алгоритмизация циклических процессов
Циклический процесс – процесс, действия в котором многократно
повторяются с изменением или без изменения параметров цикла.
Видыпеременных
переменныхцикла
цикла
Виды
Простые,для
длякоторых
которых
Простые,
существуютрекуррентные
рекуррентные
существуют
формулы
формулы
Простые,для
длякоторых
которыхне
не
Простые,
существуютрекуррентные
рекуррентные
существуют
формулы
формулы
Индексированные
Индексированные
переменные––элементы
элементы
переменные
массива
массива
Видыциклических
циклическихпроцессов
процессов
Виды
Циклсспредусловием
предусловием
Цикл
Циклсспостусловием
постусловием
Цикл
Циклссизвестным
известнымчислом
числом
Цикл
повторений
повторений
12.
6.1. Цикл с предусловием
1. Блок подготовки переменных цикла
–
2. Блок
конца
цикла
+
3. Арифметический блок
4. Блок изменения переменных цикла
13.
Пример 5. Вычислить:
H
Y
8
A H i
, где A = 5, K = 15, H = 0,2
K
i 1
2
i 1
Ход решения
Вводим замену
A H i , тогда
S
2
K
i 1
i 1
Y
H
S
8
Переменные
цикла
Начальные
значения
переменных
Рекуррентные формулы
для вычисления
накопления
Рекуррентные
формулы для
вычисления счетчика
S
S=0
A H i
S S
—
i
i=1
—
i=i+1
—
блок 1
блок 3
блок 4
2
i 1
14.
Блок-схема
начало
A =5; K = 15; H = 0,2
S =0; i = 1
i блок 1
–
+
S = S + (A+H*H)*i/(i+1)
блок 3
i=i+1
блок 4
Y=H/8*S
вывод Y
конец
15.
6.2. Цикл с постусловием
1. Блок подготовки переменных цикла
3. Арифметический блок
4. Блок изменения переменных цикла
2. Блок конца
цикла
–
+
16.
Пример 6. Вычислить Y, если известно условие:
ln x A, если x 2;
Y
e x 2 , если x 2 .
Вывести значения в виде x, Y.
x 4;4 ;
x 0,5;
A 2.
17.
Блок-схема
начало
A =2; x = 0.5; x = -4
+
x >= 2
–
y = sqr(exp(x)+2)
y = sqr(ln(x)) +A
вывод x, y
x = x + x
x>4
–
конец
+
18.
6.2. Цикл с блоком итераций ( с заданным числом повторений)
1. Блок подготовки переменных цикла
2. Блок итераций
3. Арифметический блок
19.
Пример 7. Вычислить W:
2
a
z
j
5
6
gk
W k 1
y
j 2
g k , a j – известные, y = 5, z = 3
z
Ход решения
Водим замены
6
S gk
k 1
Тогда
и
5
P a j z2
j 2
.
S P
W
y z
20.
Блок-схема
начало
ввод
gk , aj
1
P=1
y =5; z = 3
j = 2,5
S=0
P = P * (aj + z*z)
k = 1,6
S = S + gk
W=S/y+P/z
вывод W
конец
1
21.
Вопрос 7. Задачи на обработку массивов
7.1. Одномерные массивы
Массив – это пронумерованная последовательность величин одинакового
типа, обозначаемая одним именем, где каждый элемент имеет свой номер.
Например, задана массив А состоящий из 10 элементов.
A1 , A2 , A3 , A4 , A5 , A6 , A7 , A8 , A9 , A10
1 элемент
массива А
7 элемент
массива А
Краткая запись элементов массива
Ai , i 1,10
i-ый элемент
массива А
22.
Пример 8. Задан массив Ai i 1,5 . Определить и распечатать среднее
арифметическое
значение
всех
отрицательных
элементов.
Значения
элементов массива задать самостоятельно и вывести на печать.
Ход решения
Водим обозначения
S
C
K
S
5
Ai
i 1
Ai 0
K
5
1
i 1
Ai 0
где
С – среднее арифметическое всех отрицательных элементов;
S – сумма всех отрицательных элементов;
K – количество всех отрицательных элементов.
23.
Блок-схема
I. Ввод элементов массива А
II. Основная часть вычислений
начало
III. Вывод элементов массива А
i = 1,5
I
ввод Ai
1
S = 0, K = 0
C=S/K
i = 1,5
+
S = S + Ai
K=K+1
Ai 0
вывод C
–
II
i = 1,5
вывод Ai
1
конец
III
24.
7.2. Многомерные массивы
Матрица – двумерный массив.
A11 A12 A13 A14
A21 A22 A23 A24
A
A
A
A
32
33
34
31
Пример 9. Задан массив
Aij i 1,3, j 1,4
Aij i 1,5; j 1,6 . Определить и распечатать среднее
арифметическое значение всех отрицательных элементов. Значения элементов
массива задать самостоятельно и вывести на печать.
25.
Блок-схема
I. Ввод элементов массива А
II. Основная часть вычислений
начало
III. Вывод элементов массива А
i = 1,5
j = 1,6
I
ввод Aij
1
S = 0, K = 0
C=S/K
i = 1,5
вывод C
j = 1,6
+
Aij < 0
–
II
i = 1,5
j = 1,6
S = S + Aij
K=K+1
вывод Aij
1
конец
III
26.
Пример 9. Задан массив
Aij i 1,5; j 1,6
. Определить и распечатать
минимальный элемент массива и максимальный из положительных.
Значения элементов массива задать самостоятельно и вывести на печать.
Блок-схема
начало
i = 1,5
j = 1,6
ввод Aij
1
Ввод элементов
массива А
27.
Нахождение значения
минимального элемента
Нахождение значения
максимального элемента
из всех положительных
1
2
min = A1,1
max = A1,1
i = 1,5
i = 1,5
j = 1,6
j = 1,6
–
+
min > Ai,j
min = Ai,j
+
max < Ai,j
Ai,j>0
max = Ai,j
вывод min
2
вывод max
3
–
Источник: ppt-online.org