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

конечное число шагов

Алгоритмизация – процесс разработки алгоритма для решения задачи

(шагов)
Детерминированность / определенность - любое действие алгоритма должно быть строго

и недвусмысленно определено в каждом случае
Универсальность / массовость - один и тот же алгоритм можно использовать с разными исходными данными
Результативность / конечность - при точном исполнении всех предписаний алгоритма процесс должен прекратиться за конечное число шагов с получением определенного ответа на вопрос задачи (либо вывода о том, что решения не существует)

задачи и выбор метода решения

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

4 этап: Кодирование описания данных и алгоритма (составление программы на выбранном языке программирования).
5 этап: Отладка и тестирование программы с целью её проверки и доведения её в соответствии с поставленной задачей.
6 этап: Выполнение и поддержка программы (создание новых версий в зависимости от новой техники).

которую он отображает, независимо от текста внутри этого символа.
Стандартное направление

линий - слева направо и сверху вниз. Пересечение и ветвление линий не допускается.
Стрелки на прямых линиях можно не ставить. Если направление отличается от стандартного, то стрелки обязательны.
Линии должны подходить к символу слева, либо сверху, а исходить справа, либо снизу.
Допускается один вход и один выход из символа – кроме символов Модификация и Решение.

ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных, систем»

друг за другом в строгом порядке

Алгоритмы ветвящейся структуры (ветвящиеся алгоритмы) -

последовательность действий с наличием хотя бы двух альтернативных путей выполнения алгоритма

Алгоритмы циклической структуры (циклические алгоритмы) – имеется многократное повторение некоторой группы действий

πR2
2 этап: входные и выходные данные Входные данные: R,π Выходные

данные: S
3 этап: разработка алгоритма:
1 способ - словесное описание:
1) задать значения R,π
2) вычислить S по формуле
3) вывести значение S на экран

2 способ - схема алгоритма:

аx2+bx+c=0
2 этап: входные и выходные

данные a, b, c - входные данные D - промежуточные данные x1, x2 – выходные данные
3 этап: разработка алгоритма:
1 способ - словесное описание:
1) задать значения a, b, c
2) вычислить D по формуле
3) сравнить D с нулем: а) если D < 0, вывести текст «Вещественных корней нет» б) если D >= 0, вычислить x1, x2 и вывести их значения на экран

2 способ -схема алгоритма:

следующей задачи:
1. На экран выводится окно с текстом меню:
Вычисление

площади круга
Вычисление площади квадрата
Вычисление площади трапеции
Выход

Введите номер меню: _

2. С клавиатуры вводится номер меню.
3. В зависимости от введенного номера выполняется один из 4-х пунктов, причем после выполнения 1,2 или 3-го пунктов происходит возврат в окно меню.

формулы площадей:
2

этап: входные данные - R, a, b, h, n выходные данные - S

- тело цикла - условие продолжения цикла
Основные понятия: - параметр

цикла - начальное и конечное значение параметра цикла - шаг цикла

Вычислить и вывести на экран таблицу значений X и Z,

где Z=X2 для 0,2 ≤ X ≤ 1,1 с шагом 0,3

2 этап Входные и выходные данные: X - входные данные (1 ячейка ОЗУ) Z - выходные данные (1 ячейка ОЗУ)

3 этап Разработка алгоритма
1 способ - словесное описание:

Вариант 1
1) X = 0.2
2) вычислить Z = X2
3) вывести X и Z
4) изменить X = X + 0.3
5) если X ≤ 1.1, то перейти к 2) иначе перейти к п. 6)
6) конец

Вариант 2
1) X = 0.2
2) если X ≤1.1, то перейти к п. 3) иначе перейти к п. 7) 3) вычислить Z = X2
4) вывести X и Z
5) изменить X = X + 0.3
6) перейти к п. 2)
7) конец

Цикл со счетчиком

алгоритмов 3-х типов
Здесь X – параметр цикла
…
…

вводится последовательность чисел. Найти сумму чисел до первого введенного «0».
2

этап: входные и выходные данные A - входные данные (одна ячейка ОЗУ для ввода очередного числа) S - выходные данные (одна ячейка ОЗУ для накопления суммы)

3 этап: разработка алгоритма: 1) начальное значение S = 0 2) в циклической части происходит накопление S: рекуррентная формула суммы: S = S + A

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

задачи (например, произведение чисел до первого отрицательного) аналогичный цикл с

постусловием даст неверный ответ.

одного типа, имеющая общее имя.

Элементы массива пронумерованы; обратиться к каждому

элементу можно, указав его индекс (номер)
Количество индексов может быть разным (1, 2, 3,…), в зависимости от этого массивы могут быть одномерные и многомерные

массива
Размерность (ранг) определяется

числом индексов элемента массива (одномерные, двумерные,…)

из 10 целых чисел;

массив R из 15 вещественных чисел
Математическое описание: - массив А: { Аi } i=1,10 или А(10) - элементы массива А: А1 А2 …Аi … А10

- массив R: { Ri } i=1,15 или R(15)
- элементы массива R: R1 R2 …Ri … R15

Замечание. 1. Размерность массивов А и R одинакова и равна 1.
2. Размер массивов разный ( 10 и 15 элементов)

1 2

3 … 15

Имена ячеек:

R1 R2 R3 … R15

(или части элементов)
Нахождение произведения всех элементов массива (или части элементов)
Подсчет

количества положительных и отрицательных элементов в массиве
Нахождение максимального и минимального элемента в массиве
Сортировка массива (расположение элементов в порядке возрастания или убывания их значений)

- массив А
промежуточные

данные - i
выходные данные - PR

III этап: разработка схемы
PR=1
рекуррентная формула произведения: PR = PR * Ai

Схема алгоритма

массива А (с

3-го по 8-й)

проверки:
единственность максимума
все элементы равны

n=5
1 этап - находим макс. элемент и меняем местами с последним элементом: 2 4 1 3 5
2 этап – (рассматриваем массив на единицу короче n=4) находим макс. элемент и меняем местами с последним элементом в укороченном массиве: 2 3 1 4 5
3 этап – (рассматриваем массив на единицу короче n=3) находим макс. элемент и меняем местами с последним элементом в укороченном массиве 2 1 3 4 5
4 этап – (рассматриваем массив на единицу короче n=2) находим макс. элемент и меняем местами с последним элементом в укороченном массиве 1 2 3 4 5
5 этап – (рассматриваем массив на единицу короче n=1) находим макс. элемент и меняем местами с самим собой 1 2 3 4 5

Вывод: 1) на каждом этапе повторяются одни и те же действия
2) этапы отличаются только количеством элементов массива
3) число этапов равно размеру массива

текущего фрагмента, а во внешнем цикле определяется количество этапов (n-1)

и происходит обмен максимального элемента и последнего элемента текущего фрагмента массива

n=5
1 этап – сравниваем два соседних элемента: если предыдущий больше последующего, то меняем их местами: 4 5 1 3 2 4 1 5 3 2 4 1 3 5 2 4 1 3 2 5
2 этап – (рассматриваем массив на единицу короче n=4) сравниваем два соседних элемента: если предыдущий больше последующего, то меняем их местами: 1 3 2 4 5
3 этап – (рассматриваем массив на единицу короче n=3) сравниваем два соседних элемента: если предыдущий больше последующего, то меняем их местами: 1 2 3 4 5
4 этап – (рассматриваем массив на единицу короче n=2) сравниваем два соседних элемента: если предыдущий больше последующего, то меняем их местами: 1 2 3 4 5
5 этап – (рассматриваем массив на единицу короче n=1) сравнения нет 1 2 3 4 5

Вывод: 1) на каждом этапе повторяются одни и те же действия
2) этапы отличаются только количеством элементов массива
3) число этапов равно размеру массива

2. Размер

массива А - n х m элементов

Словесное описание:
Например, матрица А(n,m) целых чисел
Математическое описание: - матрица А: { Аij } i=1,n j=1,m или А(n х m)
- элементы матрицы А: А11 А12 А13 …А1m
А21 А22 А23 …А2m
А31 А32 А33 …А3m
. …
Аn1 Аn2 Аn3 …Аnm

Обозначения 2-мерных массивов

2.

2. Размер массива А - 12 элементов

1 2 3

4 5 6 7 8 9 10 11 12

Имена ячеек:

А11 А12 А13 А14 А21 А22 А23 А24 А31 А32 А33 А34

матрицы
Подсчет количества элементов, удовлетворяющих условию
Нахождение максимального и минимального элемента в

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

для лекций):

+ Aij

положительных

элементов матрицы А(3х4)

Нет положит. эл-тов

Конец

2. Размер

массива K - 5 х 5 = 25 элементов

Словесное описание: Матрица А(n,n) целых чисел
Математическое описание: матрица А: { Аij } i=1,n j=1,n или А(n х n)
- например, матрица K(5,5): { Kij } i=1,5 j=1,5 или K(5х5)
- элементы матрицы K: K11 K12 K13 K14 K15
K21 K22 K23 K24 K25
K31 K32 K33 K34 K35
K41 K42 K43 K44 K45
K51 K52 K53 K54 K55

Обозначения квадратных матриц

в указанной области, удовлетворяющих условию
Нахождение максимального и минимального элемента в

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

А32 А33 А34 А35
А41 А42 А43 А44 А45
А51 А52

А53 А54 А55

А11 А12 А13 А14 А15
А21 А22 А23 А24 А25
А31 А32 А33 А34 А35
А41 А42 А43 А44 А45
А51 А52 А53 А54 А55

А11 А12 А13 А14 А15
А21 А22 А23 А24 А25
А31 А32 А33 А34 А35
А41 А42 А43 А44 А45
А51 А52 А53 А54 А55

А11 А12 А13 А14 А15
А21 А22 А23 А24 А25
А31 А32 А33 А34 А35
А41 А42 А43 А44 А45
А51 А52 А53 А54 А55

i=1 j=1,2,3,4,5
i=2 j=2,3,4,5
i=3 j=3,4,5
i=4 j=4,5
i=5 j=5

i=1 j=1
i=2 j=1,2
i=3 j=1,2,3
i=4 j=1,2,3,4
i=5 j=1,2,3,4,5

1. Выше главной диагонали

2. Ниже главной диагонали

i=1 j=1,2,3,4,5
i=2 j=1,2,3,4
i=3 j=1,2,3
i=4 j=1,2
i=5 j=1

i=1 j=5
i=2 j=4,5
i=3 j=3,4,5
i=4 j=2,3,4,5
i=5 j=1,2,3,4,5

3. Выше побочной диагонали

4. Ниже побочной диагонали

A(5,5) i = 1, 5, 1
j = i, 5, 1

A(n,n) i = 1, n, 1
j = i, n, 1

A(5,5) i = 1, 5, 1
j = 1, i, 1

A(n,n) i = 1, n, 1
j = 1, i, 1

A(5,5) i = 1, 5, 1
j = 1, 6-i, 1

A(n,n) i = 1, n, 1
j = 1, n+1-i, 1

A(5,5) i = 1, 5, 1
j = 6-i, 5, 1

A(n,n) i = 1, n, 1
j = n+1-i, n, 1

А33 А34 А35
А41 А42 А43 А44 А45
А51 А52 А53

А54 А55

А11 А12 А13 А14 А15
А21 А22 А23 А24 А25
А31 А32 А33 А34 А35
А41 А42 А43 А44 А45
А51 А52 А53 А54 А55

А11 А12 А13 А14 А15
А21 А22 А23 А24 А25
А31 А32 А33 А34 А35
А41 А42 А43 А44 А45
А51 А52 А53 А54 А55

А11 А12 А13 А14 А15
А21 А22 А23 А24 А25
А31 А32 А33 А34 А35
А41 А42 А43 А44 А45
А51 А52 А53 А54 А55

5. Верхний треугольник

6. Нижний треугольник

7. Левый треугольник

8. Правый треугольник

i=1 j=1,2,3,4,5
i=2 j=2,3,4
i=3 j=3

j=1 i=1,2,3,4,5
j=2 i=2,3,4
j=3 i=3

i=3 j=3
i=4 j=2,3,4
i=5 j=1,2,3,4,5

j=3 i=3
j=4 i=2,3,4
j=5 i=1,2,3,4,5

A(5,5) i = 1, 3, 1
j = i, 6-i, 1

A(n,n) i = 1, n/2, 1
j = i, n+1-i, 1

A(5,5) i = 3, 5, 1
j = 6-i, i, 1

A(n,n) i = n/2, n, 1
j = n+1-i, i, 1

A(5,5) j = 1, 3, 1
i = j, 6-j, 1

A(n,n) j = 1, n/2, 1
i = j, n+1-j, 1

A(5,5) j = 3, 5, 1
i = 6-j, j, 1

A(n,n) j = n/2, n, 1
i = n+1-j, j, 1

каждого столбца в заштрихованной области матрицы X(7,7)

III этап: Словесное описание
Просматривать

по столбцам элементы заштрихованной области. В начале просмотра столбца присвоить Dj=0. Если рассматриваемый элемент Xij положительный, то увеличить Dj на 1.

X11 X12 X13 X14 X15 X16 X17
X21 X22 X23 X24 X25 X26 X27
X31 X32 X33 X34 X35 X36 X37
X41 X42 X43 X44 X45 X46 X47
X51 X52 X53 X54 X55 X56 X57
X61 X62 X63 X64 X65 X66 X67
X71 X72 X73 X74 X75 X76 X77

-1 5 6

Задача:
Сформулировать постановку задачи
Нарисовать все состояния ячеек ОЗУ
Определить значения

выходных данных

ветвление и т.п.):
Что выводится (выходные данные)?
Какие начальные значения?
Как вычисляются выходные

данные?
Выписать все переменные, задействованные в задаче; нарисовать ячейки ОЗУ
Определить состояния ячеек ОЗУ (ввод данных, каждый шаг каждого цикла вычислений, вывод данных)
Записать значения выходных данных

индексами:
- заменить на 0 все элементы от 0 до 4

и посчитать количество таких элементов,
- определить сумму элементов, не принадлежащих этому интервалу.
Вывести массив, сумму и количество.

Ввод n

Ввод массива {Mi}, i=1..n

S=0, K=0

i=1,n,2

0

S=S+Mi

Mi=0
K=K+1

Вывод M{i}, S, K

Начало

Конец

Да

Нет

и K

K
2. (продолжение)
Не пишем!

После вывода








Примечание:
В зависимости от среды и языковой конструкции,

используемой при программировании алгоритма, возможны следующие значения переменной i после выполнения цикла:
i=8 (конечное значение в цикле)
i не определено (и др.)

0 -2 0 -1 5 6
S = 1
K = 2