Лекция №1 Алгоритмы ОАП

1.

ОСНОВЫ
АЛГОРИТМИЗАЦИИ
И
ПРОГРАММИРОВАН
ИЯ

2.

Содержание
■ Понятие алгоритма, его свойства. Основные
алгоритмические конструкции
■ Простые и структурированные типы данных
■ Основы программирования

3.

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

4.

Свойства алгоритма:
■ Результативность
■ Определенность
■ Массовость
■ Дискретность

5.

■ Дискретность (разрывность) – это свойство алгоритма,
характеризующее его структуру: каждый алгоритм состоит из
отдельных законченных действий.
■ Массовость – применимость алгоритма ко всем задачам
рассматриваемого типа, при любых исходных данных.
■ Определенность – свойство алгоритма, указывающее на то,
что каждый шаг алгоритма должен быть строго определен и не
допускать различных толкований; также строго должен быть
определен порядок выполнения отдельных шагов.
■ Результативность - конечность действий алгоритма решения
задач, позволяющая получить желаемый результат при
допустимых исходных данных за конечное число шагов.

6.

Способы описания алгоритмов:
■ Словесное описание
■ Псевдокод(школьный алгоритмический язык)
■ Табличный
■ Блок-схема (графический)
■ Программа

7.

Словесное описание представляет
структуру
алгоритма
на
естественном языке.
■ Пример: инструкция по эксплуатации любого прибора бытовой
техники (утюг, телевизор, электрочайник), рецепт блюда,
правила дорожного движения.
Словесная форма имеет ряд недостатков:
-
строго не формализуема;
-
страдает многословностью записей;
-
допускает неоднозначность толкования отдельных
предписаний.
Обычно используется на начальных стадиях разработки
алгоритма.

8.

Псевдокод – пошагово-словесная
запись алгоритма по определенным
правилам или соглашениям.
Пример. Алгоритм сложения двух чисел:
1.Ввод a, b.
2.S=a + b.
3.Вывод S.
4.Конец.

9.

Примером псевдокода является школьный алгоритмический
язык. Основные служебные слова этого языка представлены
в таблице.
Служебные слова школьного алгоритмического языка

10.

Табличный способ описания
(для линейных алгоритмов)
алгоритмов
Алгоритм представляется в виде таблицы, где названия столбцов
(строк) являются командами алгоритма.
Количество столбцов – количество шагов алгоритма, их
последовательность строго определена. Число шагов конечно.
Алгоритм: площадь круга
R
R*R
3,14*R*R
S
1
1
3,14
3,14
2
4
12,56
12,56
Диаметр окружности равен двум радиусам
S = 3,14*R*R

11.

■ Блок-схема – это наглядное графическое
представление алгоритма с помощью
геометрических
фигур,
соединенных
линиями
связями,
показывающими
порядок выполнения инструкций.

12.

Вычислить периметр P
прямоугольника
начало
a, b, P
a+b
*2
P
конец
Блок-схема –
это графическое представление
алгоритма в виде последовательности
связанных между собой блоков

13.

14.

15.

16.

Программа – описание структуры
алгоритма на языке
программирования.

17.

Графический способ представления – блоксхема начало
a, b, S
S := a * b
Графический способ
представления алгоритмов
является более компактным и
наглядным по сравнению со
словесным.
Например: найти S
треугольника
S := S/2
1. Ввести значения катетов
треугольника a,b
S
2. Вычислить площадь по
формуле S=(a*b)/2
конец
3. Вывести полученное
значение S

18.

Базовые алгоритмические
конструкции
Различают:
■ Линейной структуры
■ Разветвляющейся структуры
■ Циклической структуры

19.

Алгоритмы линейной системы
начало
Y, X, A
A := 5*X
A := A + 2
Y := A * 3
Y
конец
Алгоритм линейной структуры –
это алгоритм, в котором блоки
выполняются последовательно
друг за другом, в порядке, заданной
схемой.
Например:
Y = (5*X + 2)*3

20.

Алгоритмы разветвляющейся структуры
начало
Решение задачи
осуществляется по одной
или другой ветви в
зависимости
:2
да
< 10
-5
нет
+ 22
конец
от условия
Полное ветвление

21.

Алгоритмы разветвляющейся структуры
начало
Решение задачи
осуществляется по одной или
другой ветви в зависимости
:2
да
≥ 10
+√4
конец
от условия
нет
Неполное ветвление

22.

Различают два типа циклов: с известным числом
повторений и с неизвестным числом повторений. При
этом в обоих случаях имеется в виду число повторений на
стадии разработки алгоритма.
■ Существует 3 типа циклических структур:
■ Цикл с предусловием;
■ Цикл с постусловием;
■ Цикл с параметром.

23.

Алгоритмическая структура «цикл»
начало
В алгоритмическую структуру «цикл»
входит серия команд, выполняемая
многократно
:2
да
≥ 10
*3
конец
нет
Такая последовательность команд
называется телом цикла

24.

Алгоритмическая структура «цикл»
I ТИП
счетчик
Цикл со счетчиком
Тело цикла выполняется
определенное количество раз

25.

Алгоритмическая структура «цикл»
II ТИП
да
+5
≥ 15
нет
Цикл с условием
Тело цикла выполняется, пока
условие истинно

26.

Виды циклических алгоритмов

27.

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

28.

Задание
■ Линейный алгоритм
■ Разветвляющийся алгоритм
Составить блок-схему расчёта
площади и периметра
прямоугольника по двум
известным сторонам (a, b).
Построить блок-схему алгоритма
проверки чисел на четность.