КРИТЕРИИ СРАВНЕНИЯ АЛГОРИТМОВ

Задача «неразмышляющему» исполнителю: вычислить

85 × 85.

Алгоритм

Алгоритм 3

Алгоритм 4

Алгоритм 1

Угадывать

2

По формуле

По

последовате

Умножение

(8 × (8 + 1)) × 100

вычисленной

ль-

ранее

ным

«в столбик».

+ 5 × 5.

таблице

перебором

Требуется

Вычисления –

умножения

чисел

оперативная

устный счет.

100×100,

из [101, 10

память для

имеющейся у

000] до

записи

исполнителя.

«победного

промежуточ

конца».

ныхрезульта

Оценивается объем используемой

тов.

оперативной памяти

Алгоритм 1 – лучший.

• Объём внешней памяти. Оцениваются привлекаемые

ресурсы внешней памяти, например, при сравнении

алгоритмов сортировки массива.

Алгоритм 4 - самый затратный, расширенная

таблица умножения хранится во

внешней памяти.

• Оценка сложности алгоритма (число шагов, число

операций)

в среднем — оценивается временные характеристики (число

шагов, число операций) исполнения алгоритма.

Наиболее предпочтительны алгоритмы 3 и 4: в №3- 5 операций, в №4 –локализация11 в

http://rain.ifmo.ru/cat/viewтаблице.php/theory/sc.

Начал

о

Стоп

Площа

дь

круга

начало алгоритма

завершение алгоритма

выполнение

операции

обработки

данных функция (подпрограмма).

Команды, отделенные от основной

программы, выполняются в случае их вызова из основной программы.

ветвление, проверка условия

начало цикла с параметром, задание закона изменения

параметра цикла

операции ввода и вывода

данных

http://inf1.info

РАЗРАБОТКА

АЛГОРИТМА

Разработка алгоритма решения задачи - это разбиение задачи на дискретные этапы (последовательные или параллельные), причем результаты выполнения предыдущих этапов могут использоваться при выполнении последующих.

Разработанный алгоритм можно записать несколькими способами:

•на естественном языке;

•в виде блок-схемы;

•на языке разработки приложений.

ГРАФИЧЕСКОЕ ИЗОБРАЖЕНИЕ СТРУКТУРЫ АЛГОРИТМА

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

Алгоритм изображается в виде

последовательности связанных

между собой функциональных блоков. Каждый блок выполняет

одно или несколько действий. Каждому типу действий

соответствует геометрическая

фигура.

БЛОК-СХЕМА

- ориентированный граф, указывающий порядок исполнения команд алгоритма.

Типы вершин:

Действ		Ложь				Истина
ие					Услов
					ие

функциональ	предикатная	вершина
ная вершина	вершина	слияния

БАЗОВЫЕ КОНСТРУКЦИИ АЛГОРИТМА

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

Поэтому

линейную, ветвящуюся и циклическую

конструкции называют базовыми.

АЛГОРИТМИЧЕСКИЕ

СТРУКТУРЫ

Следование предполагает последовательное выполнение команд сверху вниз.

Если алгоритм состоит только из структур следования, то он является линейным.

Действие 1

Действие 2

http://inf1.info

АЛГОРИТМИЧЕСКИЕ

Ветвление СТРУКТУРЫ

Выполнение программы идет по одной из двух,

нескольких или множества

ветвей.

Выбор ветви зависит от

условия на входе ветвления

и поступивших сюда

данных.

Неполное

ветвление

http://inf1.info

АЛГОРИТМИЧЕСКИЕ

Цикл.

СТРУКТУРЫ

Предполагает возможность многократного повторения

определенных действий. Количество повторений зависит от условия цикла. Цикл с параметром (арифметический

цикл ): число повторений тела цикла

заранее известно или определено.

Итерационный цикл (цикл с пред- /

постусловием), если число повторений тела цикла заранее

неизвестно, а зависит от значений переменных, участвующих в вычислениях.

http://inf1.info

АЛГОРИТМИЧЕСКИЕ

СТРУКТУРЫ

Расположение циклов

последователь вложенные ные

некорректные