Презентация "Типы алгоритмов и формы их записи"

Типы алгоритмов и формы их записи.

Алгоритм

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

Типы алгоритмов

линейные

ветвящиеся

циклические

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

графическая

(блок-схема)

табличная

словесная

Линейные алгоритмы.

Линейные алгоритмы

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

Задача 1. Вычислить сумму двух чисел.

На примере решения этой задачи рассмотрим все три формы записи алгоритма .

Решение любой задачи начинается с I этапа

Постановка задачи :

Дано: a – первое число;

b – второе число.

Найти: с – сумму чисел a и b.

II этап

Математическая формализация

Связь: с=a+b.

III этап

Составление алгоритма

Табличная форма

! Применяется только для линейных вычислительных алгоритмов.

a

1

b

c=a+b

3

-2

4

5

-6

-8

-9

-4

Словесная форма

! Применима для всех типов вычислительных алгоритмов.

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

• Начало алгоритма.
• Прочесть (ввести) значение первого числа - a .
• Прочесть (ввести) значение второго числа - b .
• Сложить значения a и b .
• Записать полученный в предыдущей команде результат как значение c.
• Конец алгоритма.

Если использовать оператор присваивания( :=) , то словесная форма представления этого же алгоритма станет более компактной:

• Начало алгоритма.
• Прочесть (ввести) значение первого числа - a .
• Прочесть (ввести) значение второго числа - b .
• c := a + b .
• Вывести полученный результат - c .
• Конец алгоритма.

Графическая форма

(блок-схема)

! Применима для всех типов вычислительных алгоритмов.

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

Блок начала и конца алгоритма . В овале пишут слова «начало» и «конец».  

Блок ввода и вывода информации . В блоке ввода перечисляют имена данных,

подлежащих вводу в алгоритм, в блоке вывода – выводу из алгоритма.

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

Блок изменения параметров . Используется, например, в блок-схемах

циклических алгоритмов со счетчиком.

Блок «решение». Проверяет выполнение какого-либо условия: выход да при

выполнении условия, выход нет – при его невыполнении ( да и нет иногда

заменяют на 0 и 1 или + и – соответственно).

нет

да

?

Тогда графическая форма (блок-схема) записи алгоритма вычисления суммы двух чисел выглядит следующим образом:

начало

a

b

c:=a+b

c

конец

Задача 2.

Вычислить время просмотра фильма.

Дано: t1 – начальное время просмотра;

t2 – конечное время просмотра.

Найти: t – общее время просмотра фильма.

Связь: t:=t2-t1.

Словесная форма

Табличная форма

• Начало алгоритма.
• Ввести начальное время просмотра – t1 .
• Ввести конечное время просмотра – t2 .
• t := t2 – t1.
• Вывести полученный результат - t .
• Конец алгоритма.

t1

t2

13

t:=t2-t1

15

12

2

16

20

4

21

1

Графическая форма (блок-схема)

начало

t1

t2

t:=t2-t1

t

конец

Ветвящиеся алгоритмы.

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

Алгоритм с ветвлением

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

Ветвление

полное

неполное

-

+

-

+

?

?

действие 1

действие 2

действие 1

B А больше В A = B А больше или равно В A B А не равно В " width="640"

Операции сравнения

A

А меньше В

A

А меньше или равно В

A = B

А равно В

A B

А больше В

A = B

А больше или равно В

A B

А не равно В

Задание

• Составьте блок-схему алгоритма перехода дороги, в зависимости от сигнала светофора.

конец

Сигнал светофора зеленый?

начало

Подойти к дороге и остановиться

Начать движение

Да

Ждать зеленого сигнала

Нет

начало

Подойти к дороге и остановиться

Нет

Да

Сигнал светофора зеленый?

Начать движение

Ждать зеленого сигнала

конец

b. Решение задачи оформим в соответствии с 1, 2 и 3 ЭРЗ на компьютере.   Дано: a – первое число; b – второе число. Найти: с. Связь: c=a+b, если a≤b и c=a-b, если ab или " width="640"

Задача 3. Вычислить значение величины с, определяемое по формулам: c=a+b, если a≤b и c=a-b, если ab.

Решение задачи оформим в соответствии с 1, 2 и 3 ЭРЗ на компьютере.

 

Дано: a – первое число;

b – второе число.

Найти: с.

Связь: c=a+b, если a≤b и

c=a-b, если ab

или

Алгоритм решения данной задачи составим в графической форме. Он организуется при помощи полной формы ветвления.

начало

a

Протестируем алгоритм и оформим результат в виде таблицы:

b

Тест

a

1.

2.

5

b

4

Проверка условия

3.

2

3

4.

5≤2

4

Результат проверки условия

(+ или -)

0

Действия

4≤4

-3

5.

-

c=5-2

с

3≤-3

0

11

6.

+

c=4+4

0≤0

-9

-

7

3

8

c=3-(-3)

-3

?

+

c=0+0

?

6

0

-

+

a≤b

c:=a-b

c:=a+b

c

конец

Задача 4. Вычислить значение величины с, определяемое по формулам: c=a+b, если a≤b.

Дано: a – первое число;

b – второе число.

Найти: с.

Связь: c=a+b, если a≤b

Алгоритм решения данной задачи организуется при помощи неполной формы ветвления.

начало

a

b

-

+

a≤b

c:=a+b

c

конец

Самостоятельная работа.

Задача 5. Определите значение переменной c после выполнения следующего фрагмента программы:

• Начало алгоритма.
• a := 40;
• b := 10;
• b := a - 2*b;
• Если a
• Вывод с;
• Конец алгоритма.

b, То c := a + b, Иначе c := b – a; Вывод с; Конец алгоримта. " width="640"

Задача 6. Определите значение переменной c после выполнения следующего фрагмента программы:

• Начало алгоритма.
• a := -5;
• b := 14;
• b := b + a*2;
• Если a b, То c := a + b, Иначе c := b – a;
• Вывод с;
• Конец алгоримта.