1

Конспекты лекций по курсу

«Введение в информатику и системы программирования», 1 семестр

С.А. Немнюгин, направление «Прикладные математика и физика»)

Лекция 14

Алгоритмы и алгоритмические языки

Алгоритмы

Наивное определение

Алгоритм это описание процесса решения той или иной задачи.

Не такое уж наивное определение

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

Алгоритм должен отвечать следующим требованиям:

наличие ввода исходных данных;

наличие вывода результата выполнения;

однозначность компьютер «понимает» только однозначные инструкции;

общность — алгоритм предназначен для решения не одной задачи, а целого класса задач;

корректность — алгоритм должен давать правильное решение задачи;

конечность — решение задачи должно быть получено за конечное число шагов;

эффективность — для решения задачи должны использоваться ограниченные ресурсы компьютера.

Алгоритм решения некоторого класса задач — вычисление суммы двух чисел

Обозначим эти числа a и b.

Алгоритм можно записать на естественном языке:

1)ввести значение a;

2)ввести значение b;

3)вычислить c = a + b;

4)вывести значение c.

Пошаговая детализация алгоритма

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

Способы записи алгоритмов

Выделяют следующие основные способы записи алгоритмов:

вербальный - алгоритм описывается на естественном языке;

символьный - алгоритм описывается с помощью набора символов;

графический - алгоритм описывается с помощью набора графических изображений.

2

Общепринятыми способами записи являются графическая запись с помощью блок-схем и символьная запись с помощью какого-либо алгоритмического языка.

Поиск максимального элемента

Algorithm LargestNumber

Input: A non-empty list of numbers L. Output: The largest number in the list L. largest ← L0

for each item in the list L≥1, do if the item > largest, then

largest ← the item

return largest

Сортировка методом «пузырька»

Алгоритм Брезенхама

3

Метод деления отрезка пополам

Do While (abs(right - left) > 2*epsilon)

'Calculate midpoint of domain midpoint = (right + left) / 2 'Find f(midpoint)

If ((f(left) * f(mid)) > 0) Then 'Throw away left half

left = midpoint

Else

'Throw away right half right = midpoint

End If

Loop

Return (right + left) / 2

Блок-схемы

4

Алгоритм определения принадлежности точки окружности

Решение квадратного уравнения

5

Приближенное вычисление квадратного корня из x

Вычисление суммы

6

Блок-схемы наглядны Блок-схемы неудобны для записи сложных алгоритмов

Основные алгоритмические конструкции

Линейная последовательность операторов

Бинарное ветвление

7

Цикл