Презентация по теме "Алгоритмы"

Тема: Понятие алгоритма

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

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

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

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

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

Свойства алгоритма

1. Дискретность характеризует структуру: каждый алгоритм состоит из отдельных законченных действий, говорят: «Делится на шаги».

Свойства алгоритма

2. Массовость - применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных.

Свойства алгоритма

3. Определенность (детерминированность, точность) —каждый шаг алгоритма должен быть строго определен и не допускать различных толкований.

Свойства алгоритма

4. Результативность —любой алгоритм должен завершаться за конечное (может быть очень большое) число шагов.

Свойства алгоритма

5. Формальность — любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т.е. отвлекается от содержания поставленной задачи и лишь строго выполняет инструкции

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

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

2. Псевдокод - описание структуры алгоритма на естественном, частично формализованном языке, с использованием некоторых формальных конструкций и общепринятой математической символики. Строгих синтаксических правил для записи псевдокода не существует.

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

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

Элементы блок-схем

В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур.

Начало и конец алгоритма

описание действия

обращение к вспомогательным алгоритмам (подпрограммам)

ввод/вывод с неопределенного носителя

ввод с клавиатуры

вывод на монитор

вывод на печатающее устройство

проверка условия или условный блок

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

Блок — границы цикла, описывающий циклические процессы типа: «цикл с предусловием», «цикл с постусловием»

А

А

Соединительные блоки

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

Элементарные шаги алгоритма можно объединить в следующие алгоритмические конструкции:

• линейные (последовательные),

• разветвляющиеся,

• циклические,

• рекурсивные.

Линейная алгоритмическая конструкция

Линейной называют алгоритмическую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого i-го действия (шага) выполняется (i+1)-е действие (шаг), если i-е действие - не конец алгоритма.

Пример 1: Описать алгоритм сложения двух чисел с использованием псевдокода и в виде блок-схемы

Псевдокод:

Блок-схема:

• Ввод двух чисел а, b.

2. Вычисляем сумму S = а + b.

3. Вывод S.

4. Конец.

Разветвляющаяся алгоритмическая конструкция

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

Различают неполное (ЕСЛИ — ТО) и полное (ЕСЛИ — ТО — ИНАЧЕ) ветвления.

Полное ветвление позволяет организовать две ветви в алгоритме (ТО или ИНАЧЕ), каждая из которых ведет к общей точке их слияния, так что выполнение алгоритма продолжается независимо от того, какой путь был выбран.

Неполное ветвление предполагает наличие некоторых действий алгоритма только на одной ветви (ТО), вторая ветвь отсутствует, т.е. для одного из результатов проверки никаких действий выполнять не надо, управление сразу переходит к точке слияния.

Полное ветвление

Неполное ветвление

b, ТО «выводим a», ИНАЧЕ «выводим b» . 3. Конец. 19 " width="640"

Пример 2: Вывести значение наибольшего из двух чисел

Псевдокод:

Блок-схема:

• Ввод двух чисел а, b.

2. ЕСЛИ а b, ТО «выводим a», ИНАЧЕ «выводим b» .

3. Конец.

19

Пример 3: Найти значение наименьшего из трёх чисел

Блок-схема:

Заданные числа обозначим: а,b,с; результирующее наименьшее — min.

Команда «Выбор»

Часто при выборе одного из возможных вариантов действий приходится проверять значение выражения на принадлежность заданному набору данных. Для этого существует команда «Выбор».

При ее исполнении сначала вычисляется значение некоторого выражения Z . Затем последовательно проверяются условия V1 , V2 , ..., Vn относительно Z , начиная с первого, до тех пор, пока не встретится условие, принимающее значение ИСТИНА.

Далее выполняется соответствующее этому условию действие (или серия действий), после чего команда выбора завершается. Если ни одно из условий не является истинным, то выполняется действие (или набор действий), идущее по ветви ЛОЖЬ для каждого из условий.

Блок-схема команды «Выбор» для n = 3

Алгоритмическая конструкция «Цикл»

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

Группа повторяющихся действий на каждом шагу цикла называется телом цикла.

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

• цикл с параметром (арифметический цикл)



• цикл с предусловием

итерационные

• цикл с постусловием

Арифметический цикл

В арифметическом цикле число его шагов (повторений) однозначно определяется правилом изменения параметра, которое задается с помощью начального (N) и конечного (К) значений параметра и шагом (h) его изменения. Т.е., на первом шаге цикла значение параметра равно N, на втором - N + h, на третьем - N + 2h и т.д. На последнем шаге цикла значение параметра не больше К, но такое, что дальнейшее его изменение приведет к значению, большему, чем К.

Правило изменения  параметров i:

i = N, K, h         означает

1-й шаг цикла

    i = N

2-й шаг цикла

    i = N + h

3-й шаг цикла

и т.д.

    i = N + 2h

последний шаг

    i = K

Пример : Вывести 10 раз слово «Привет!»

Параметр цикла обозначим i, он будет отвечать за количество выведенных слов.

При i = 1 будет выведено первое слово, при i = 2 будет выведено второе слово и т.д.

Так как требуется вывести 10 слов, то последнее значение параметра i = 10.

Блок-схема:

Цикл с предусловием

Количество шагов цикла заранее не определено и зависит от входных данных задачи. В данной структуре сначала проверяется значение условного выражения (условие) перед выполнением очередного шага цикла. Если значение условного выражения истинно, исполняется тело цикла. После чего управление вновь передается проверке условия и т.д. Эти действия повторяются до тех пор, пока условное выражение не примет значение ЛОЖЬ. При первом же несоблюдении условия цикл завершается.

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

с помощью условного блока а

с помощью блока границы цикла б.

Особенность цикла с предусловием:

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

Цикл с постусловием

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

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

а

б

с помощью условного блока а

с помощью блока границы цикла б.