Уроки по теме Алгоритмизация

11/13/18

Алгоритм

и его формальное исполнение

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

Алгоритм содержит несколько шагов.

Шаг алгоритма – это каждое отдельное действие алгоритма.

«Алгоритм – это порядок действий».

Исполнитель – это объект выполняющий определенный набор действий.

Система команд исполнителя (СКИ) – это совокупность команд, которые может выполнять исполнитель.

Среда исполнителя – обстановка, в которой функционирует исполнитель.

Разработка и исполнение алгоритмов

Разрабатывает алгоритмы: человек

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

Исполнитель решает задачу по заданному алгоритму, строго следуя по предписаниям (программе) не вникая и не рассуждая, почему он так делает.

Кто может быть исполнителем алгоритма?

!!! Исполнителем алгоритма может быть не только человек , но и автоматическое устройство (реальное или воображаемое).

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

Задание:

Назови исполнителей следующих видов работы:

Уборка мусора во дворе

Обучение детей в школе

Вождение автомобиля

Ответ у доски

Приготовление пищи

Печатание документа на принтере

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

Детерминированность (определенность, точность) – каждое действие должно строго и недвусмысленно определено

Результативность – получение результата за конечное количество шагов

Свойства АЛГОРИТМА

Массовость – использование алгоритма для решения однотипных задач

Дискретность (прерывность, раздельность) – разбиение алгоритма на шаги

Классификация алгоритмов по форме представления :

Словесные

Табличные

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

Программные

Задание : Составь алгоритм сбора портфеля. Продумай СКИ.

Возьми портфель

Открой дневник

Посмотри расписание

Сложи школьные принадлежности в портфель

Закрой портфель

Словесный

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

Число шагов __________________

Исполнитель ________________

Среда исполнителя _______________

5 (пять)

Человек

Квартира

Средства представления и записи алгоритмов

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

Основные условные обозначения в блок-схемах

Условное обозначение

Назначение блока

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

Ввод или вывод данных.

Внутри блока перечисляются данные через запятую.

Процесс.

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

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

Внутри блока записываются логические условия. Имеет два выхода Да(+) и Нет(-).

Направление.

Линейный (следование)

Разветвленный (ветвление, выбор, альтернатива)

Циклический (повтор)

Вспомогательный

Комбинированный

Классификация алгоритмов по структуре:

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

Линейный алгоритм – это алгоритм, шаги которого выполняются последовательно друг за другом. 

(Пример: алгоритм сбора портфеля).

Задача

Вычислить периметр произвольного треугольника по его трем сторонам.

Решение:

1 этап: Постановка задачи.

Исходные данные : А, B, C – стороны произвольного треугольника

Выходные данные : P – периметр треугольника.

2 этап: Математическая модель.

P=A+B+С

3 этап: Составление алгоритма

Начало

Ввод

A, B, C

P=A+B+C

Вывод

P

Конец

Базовая структура линейного алгоритма:

Начало

Серия команд 1

Серия команд 2

Серия команд N

Конец

начало

№ 1 И спользуя блок-схему алгоритма , вычислите значение функции Y при X=2,

ввод: X

Z = 8 * X

Z =

Z = Z - 1

Y = 3 * X

Y = Y / Z

вывод: Y

конец

11/13/18

Разветвляющийся алгоритм

Закончите предложения:

Алгоритм – это …

Основные свойства алгоритма …

Алгоритмы можно записать такими способами …

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

Базовые структуры алгоритмов:

1. Линейный алгоритм или структура следования

Команда 1

Команда 2

. . .

Команда N

Следование  – команды выполняются одна за другой в том порядке, в котором записаны в программе (линейные алгоритмы).

Графически ветвление можно представить схемой.

Форма организации действий, при которой,

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

да

нет

Условие

Серия 2

Серия 1

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

ЕСЛИ условие ТО команда 1 ИНАЧЕ команда 2

Существует укороченный вариант Ветвления – в нем ветвь ИНАЧЕ может отсутствовать. Тогда если условие истинно, то выполняется команда 1 . Если же условие ложно, то ничего не выполняется, а Ветвление заканчивается, то есть мы сразу попадаем в точку выхода.

ЕСЛИ условие ТО команда

Словесная запись:

40». x+2440 Да Нет Выписать x" width="640"

ПРИМЕР 1.

Задача: «Из ряда чисел 15, 16, 17, 18

выпишите значения x, при которых верно

неравенство x + 24 40».

x+2440

Да

Нет

Выписать x

0 Да Нет Число Число отрицательное положительное" width="640"

ПРИМЕР 2.

Дано число x. Определите, является ли число x положительным? (с помощью блок-схемы)

X 0

Да

Нет

Число

Число

отрицательное

положительное

Решение задач

Пусть задано число x . Требуется составить алгоритм на языке блок-схем и на естественном языке для вычисления следующей функции:

Задание:

Задание 1.

Составить алгоритм для перехода дороги по сигналу светофора.

Задание 2.

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

(подсказка:

бумажка красная – раствор кислый,

бумажка синяя – раствор щелочной,

цвет не изменился – раствор нейтральный).

Составить блок-схему вычисления функции:

11/13/18

Циклические алгоритмы

Многие процессы в окружающем мире основаны на многократном повторении одной и той же последовательности действий.

Смена времен года:

Жизнь растений в течение года проходит одни и те же циклы.

Алгоритм называется циклическим , если последовательность шагов алгоритма выполняется многократно

ЦИКЛ С ПОСТУСЛОВИЕМ

(цикл-до)

ЦИКЛ С ПРЕДУСЛОВИЕМ

(цикл-пока)

серия команд

да

нет

условие

Серия команд

да

нет

условие

ЦИКЛ С ПАРАМЕТРОМ

параметр

серия команд

Цикл «До»

Цикл «Пока»

Транжира

Деньги есть?

Съел

НЕТ

ДА

Понравилось?

Купил

НЕТ

Обжора

Тело цикла – шаги алгоритма, которые повторяются.

Составьте блок-схему алгоритма работы автомата по продаже банок «PEPSI». Обведи карандашом тело цикла.

Шаги:

• Посмотреть цену
• Опустить монету
• Подойти к автомату
• Набралась нужная сумма?
• Достать деньги
• Взять банку
• Нажать кнопку

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

Начало

Шаги:

• Посмотреть цену
• Достать деньги
• Опустить монету
• Набралась нужная сумма?
• Нажать кнопку
• Взять банку

Посмотреть цену

Достать деньги

Опустить монету

Нет

Набралась нужная сумма?

Нажать кнопку

Взять банку

Конец

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

НАЧАЛО

X: = - 5

Y: = 2 * X

X

Y

ВЫВОД: X, Y

X: = X + 1

да

X ≤ 0

нет

КОНЕЦ

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

НАЧАЛО

X = - 3

Y = -2 * X

ВЫВОД: X, Y

X

Y

X = X + 1

да

X ≤ 2

нет

КОНЕЦ

Маша забыла пароль для входа в Windows XP, но помнила алгоритм его получения из символов «KBZKZ9KBK» в строке подсказки. Если все последовательности символов «ZKZ» заменить на «RP», а «KBK» на «1111», а из получившейся строки удалить 2 последних символа, то полученная последовательность и будет паролем. Какой пароль был у Маши?

Витя пригласил своего друга Сергея в гости, но не сказал

ему код от цифрового замка своего подъезда, а послал следующее SMS-сообщение: «в последовательности чисел 9, 8, 4, 3, 6 все четные числа разделить на 2, а затем удалить из полученной последовательности все нечетные числа». Найдите код цифрового замка.

Определить значение переменной b после выполнения фрагмента алгоритма:

a:= 256

b:= 0

да

a = 1

нет

a:= a/2

b:= b + a