Алгоритмизация и программирование (лекция № 1)

1.

3. Алгоритмизация и
программирование
3.1 Основы алгоритмизации

2.

Алгоритм – ключевое понятие информатики. Русские слова
«метод», «способ», «рецепт», «план действий» можно считать
близкими словами.
Существуем мнение, что слово «алгоритм» произошло от имени
автора известного арабского учебника по математике – Мухаммед
бен Муса ал–Хорезми. В учебнике были сформулированы правила
четырех арифметических действий в привычном нам виде.
Алгоритм – конечная последовательность команд исполнителю.
Исполнитель – человек, живое существо или автоматическое
устройство, которое способно к восприятию и исполнению команд.
Алгоритм – это точное предписание, которое определяет процесс,
ведущий от исходных данных к требуемому конечному результату.
Алгоритмами, например, являются правила сложения, умножения,
решения алгебраических уравнений, умножение матриц и т.п.

3.

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

4.

Существуют следующие способы описания алгоритмов:
словесно–формульный;
структурный или блок–схемный;
программный.
При словесно–формульном способе алгоритм записывается в виде
текста с формулами по пунктам, определяющим последовательность
действий.
Например:
Начало
1. Налить воды в чайник.
2. Поставить чайник на электроплиту.
3. Включить электроплиту.
4. Подождать, пока вода закипит.
5. Выключить электроплиту.
Конец

5.

При блок–схемном способе описания алгоритм изображается
геометрическими фигурами (блоками), связанными по направлению
линиями (направлениями потока) со стрелками. В блоках записывается
последовательность действий. Совокупность геометрических фигур
образует блок–схему алгоритма.
Наименования
Обозначения
Функции
Пуск – останов
Начало, конец, прерывание процесса обработки данных.
Ввод – вывод
Преобразование данных в форму, пригодную для обработки
(ввод) или отображения результатов обработки (вывод).
Процесс
Предопределен-ный
процесс
Условие
Итерация или цикл
(многократно
повторяемый
участок
программы)
i= i1; i2; i3
тело цикла
Выполнение операции или группы операций, в результате
которых изменяется значение, форма представления или
расположение данных
Использование ранее созданных и отдельно написанных
программ (подпрограмм)
Выбор направления выполнения алгоритма в зависимости от
некоторых переменных условий.
Циклический оператор, где:
i – переменная цикла;
i1– начальное значение;
i2– конечное значение;
i3– шаг цикла.

6.

При программном способе алгоритм записывается с помощью
операторов языка программирования.
Например:
Программа Сумма
Описание
а,в,с: Целый
Конец_описания
а:=5
в:=9
с:=а+в
Вывод (‘сумма= ‘, с)
Конец_Программы

7.

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

8.

Пример. Найти площадь прямоугольника, если известны длины его
сторон. Исходные данные: a – длина прямоугольника, b – ширина
прямоугольника. Выходные данные: S – площадь.
начало
начало
Х:=5
a:=5
b:=8
У:=Х*Х+5
S:=a*b
Вывод(S)
конец

9.

10.

Разветвляющаяся конструкция предполагает выбор шага для
выполнения на основе проверки истинности какого либо условия.
Если условие имеет значение «истина», то дальнейшие выполнение
пойдет по одной ветке, иначе – по другой.
На структурных схемах такие алгоритмы обозначают с помощью
ромба с выходом стрелок по итогам проверки условия на истину или
ложь.

11.

Пример. Вывести значение наибольшего из двух чисел.
Исходные данные: a – первое число, b – второе число.
Выходные данные: вывод наибольшего числа.
Начало
Ввод a, b
Нет
a>b
Вывод b
Да
Вывод a
Конец

12.

13.

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

14.

Пример циклической конструкции с фиксированным количеством
повторений:

15.

Пример циклической конструкции с неопределенным количеством
повторений:

16.

Циклические алгоритмы, где условие завершения:
1) истинность трех условий, 2) истинность составного условия

17.

Циклы могут вкладываться друг в друга, при этом они не должны
пересекаться.
1. Вложенные циклы, границы которых не пересекаются.
2. Недопустимые вложенные циклы.