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


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
ОСНОВНЫЕ
АЛГОРИТМИЧЕСКИЕ
КОНСТРУКЦИИ

ЭТАПЫ РЕШЕНИЯ ЗАДАЧ НА ЭВМ :

постановка задачи;

математическое описание задачи;

выбор и обоснование метода решения;

алгоритмизация вычислительного
процесса;

составление программы;

отладка программы;

решение задачи на ЭВМ и анализ
результатов.

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

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

произошло от латинской формы имени
величайшего среднеазиатского математика
МУХАММЕДА ИБН
МУСА АЛ
-
ХОРЕЗМИ
(
Alhorithmi
), жившего в 783

850 гг.

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

В XII веке эта книга была переведена на латынь и получила
широкое распространение в Европе.

С 1747 г. вместо слова
алгоризм

стали употреблять
алгорисмус
,
смысл которого состоял в комбинировании четырех операций
исчисления: «+» «
-
» «/» «*»

К 1950 г.
алгорисмус

стал
алгорифмом
. Смысл
алгорифма

чаще
всего связывался с
алгорифмами

Евклида


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

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

СВОЙСТВА
АЛГОРИТМА

дискретность

определенность

результативность

массовость

набор объектов, составляющих совокупность возможных исходных данных,
промежуточных и конечных результатов;

правило начала;

правило непосредственной переработки информации (описание
последовательности действий);

правило окончания;

правило извлечения результатов.

ДЛЯ ЗАДАНИЯ АЛГОРИТМА НЕОБХОДИМО ОПИСАТЬ СЛЕДУЮЩИЕ
ЕГО ЭЛЕМЕНТЫ:


СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ:

словесно
-
формульный (на естественном языке)

структурный (графический)
-

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

псевдокоды

программный

ОПИСАНИЕ АЛГОРИТМА СТРУКТУРНЫМ
(ГРАФИЧЕСКИМ) ПОДХОДОМ

Каждая геометрическая фигура называется блоком.

Внутри блока записывается действие (операция), которую этот блок отождествляет.

Основное направление потока информации сверху вниз, в порядке исполнения.

Порядок выполнения этапов решения задачи от блока к блоку указывается стрелками,
соединяющими блоки.

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

Каждый алгоритм начинается и заканчивается специальными блоками


«Начало» и «Конец».

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

Для начертания пояснений к определенным местам схемы алгоритма
применяют комментарий.

БЛОК
-
СХЕМУ АЛГОРИТМА
-

ТЕКСТОВЫЙ
РЕДАКТОР
MS

WORD

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

1. Выяснить исходные данные, результаты, назначить им имена.

2. Выбрать метод (порядок) решения задачи.

3. Разбить метод решения задачи на этапы (с учетом возможностей
ЭВМ).

4. Изобразить каждый этап в виде соответствующего блока схемы
алгоритма и указать стрелками порядок их выполнения.

5. В полученной схеме при любом варианте вычислений:

а) предусмотреть выдачу результатов или сообщений об их
отсутствии;

б) обеспечить возможность после выполнения любой операции так
или иначе перейти к блоку «Конец» (к выходу схемы).

МОЖНО ВЫДЕЛИТЬ ПЯТЬ ПРОСТЕЙШИХ СТРУКТУР:


следование (последовательность двух или более операций);


ветвление (выбор направления);


повторение (цикл «пока», цикл «до», цикл с параметром);


обход;


множественный выбор.

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


СООТВЕТСТВЕННО, ВЫЧИСЛИТЕЛЬНЫЕ ПРОЦЕССЫ,
ВЫПОЛНЯЕМЫЕ НА ЭВМ ПО ЗАДАННОЙ ПРОГРАММЕ, МОЖНО
РАЗДЕЛИТЬ НА ТРИ ОСНОВНЫХ ВИДА:



ЛИНЕЙНЫЕ


ВЕТВЯЩИЕСЯ


ЦИКЛИЧЕСКИЕ


ЛИНЕЙНЫЕ ПРОЦЕССЫ

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

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

На схеме блоки, отображающие эти операции, располагаются в
линейной последовательности.

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

ВЕТВЯЩИЕСЯ ПРОЦЕССЫ

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

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

Каждое отдельное направление процесса обработки
данных является отдельной ветвью вычислений.

Признаком разветвляющегося алгоритма
является наличие операций проверки условия.
Различают два вида условий
-

простые и
составные.

Простым условием (отношением) называется
выражение, составленное из двух
арифметических выражений или двух текстовых
величин (иначе их еще называют операндами),
связанных одним из знаков: <, >, <=, >=, <>, =

ЦИКЛИЧЕСКИЕ ПРОЦЕССЫ

Цикл ПОКА

(с предварительным условием)

Цикл ДО

(с последующим условием)

Цикл ДЛЯ

(с параметром)

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

Цикл с последующим условием
(ДО) действует следующим
образом:

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

Циклическая часть программы
выполняется повторно для каждого
значения параметра цикла
i

от его
начального значения
m
1 до
конечного значения до
m
2
включительно.

Чаще всего параметр цикла
i

используется как переменная целого
типа, а шаг его изменении равен +1
или
-
1. Если значение параметра
цикла возрастает, то шаг его
изменения +1. Если значение
параметра уменьшается, то шаг его
изменения
-
1.

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

повторяющиеся
вычисления
записываются всего
лишь один раз;

вход в цикл возможен
только через его начало;

переменные оператора
цикла должны быть
определены до входа в
циклическую часть;

необходимо
предусмотреть выход из
цикла

Совокупность

величин,

с

которыми

работает

компьютер,

принято

называть

данными
.


Всякая

величина

занимает

свое

определенное

место

в

памяти

ЭВМ,

иногда

говорят



ячейку

памяти
.

Любая

величина

имеет

три

основных

свойства
:

имя,

значение

и

тип
.

В

алгоритмах

и

языках

программирования

величины

подразделяются

на

константы

и

переменные
.


Константа



неизменная

величина,

и

в

алгоритме

она

представляется

собственным

значением,

например
:

15
,

34
.
7
,

k
,

True
и

др
.


Переменные

величины

могут

изменять

свои

значения

в

ходе

выполнения

программы

и

представляются

в

алгоритме

символическими

именами



идентификаторами,

например
:

X
,

S
2
,

cod
15

и

др
.



Приложенные файлы


Добавить комментарий