Начала алгоритмизации и программирования

АЛГОРИТМ:
ЧТО И КАК
«Начала алгоритмизации и программирования»
Занятие 2

На этом занятии:
Разберёмся, кто и для кого пишет алгоритмы
Поговорим о свойствах алгоритмов
Познакомимся с разными формами описания алгоритмов и попробуем переводить алгоритмы из одной формы в другую
Поэкспериментируем с алгоритмами из реальной жизни
Попрактикуемся в чтении и исполнении алгоритмов

Алгоритм –
формальное описание последовательности действий для достижения цели
Является ли алгоритмом…
…раздел «Подготовка к работе» в инструкции к стиральной машине?
…конституция США?
…технология изготовления детали на металлорежущем станке?
…маршрут, построенный навигатором?
…ответ на вопрос «Как добраться до ближайшей станции метро?»?
…книга Дейла Карнеги «Как перестать беспокоиться и начать жить»?
…глава в учебнике про умножение и деление в столбик?

Исполнитель алгоритма
Исполнитель алгоритма – человек или автоматическое устройство, которому предстоит осуществить описываемую последовательность действий.
Исполнитель должен:
Хранить алгоритм в памяти.
Распознавать его команды.
Быть в состоянии их исполнять.
Является ли кофейный автомат исполнителем алгоритмов?
Речь обо всём автомате или о его микропроцессоре?
Что является входными данными? А выходными?
А какая у него система команд?

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

Есть надежный способ папу
Навсегда свести с ума.
Расскажите папе честно,
Что вы делали вчера.
Если он при этом сможет
Удержаться на ногах,
Объясните, чем заняться
Завтра думаете вы.
И когда с безумным видом
Папа песни запоет,
Вызывайте неотложку,
Телефон ее - ноль три.
Каким из свойств алгоритмов данный
НЕ ОБЛАДАЕТ?
ДИСКРЕТНОСТЬ!
ОК, ну а теперь?
ОДНОЗНАЧНОСТЬ!

А теперь?
КОНЕЧНОСТЬ!
Ну и как это можно исправить?

Формы записи алгоритма
Рассмотрим на примере алгоритма нахождения наибольшего общего делителя двух чисел
(алгоритм Евклида)
Два натуральных числа, А и В
Натуральное число, НОД(А,В)
Алгоритм
нахождения НОД
- Да легко!
Просто вычитайте из большего меньшее, пока они не сравняются!

Словесный
Ввести числа А и В.
Если А=В, то перейти к п.8
Если А>В, то перейти к п. 6.
В:= В - А (вычесть из В значение А, результат записать в В)
Перейти к п.2
А:= А - В (вычесть из А значение В, результат записать в А)
Перейти к п.2
Вывести значение А.
Закончить работу алгоритма.
- Да легко!
Просто вычитайте из большего меньшее, пока они не сравняются!

Блок-схема
- Да легко!
Просто вычитайте из большего меньшее, пока они не сравняются!
НАЧ
Ввод А, В
А = В
А > В
Вывод А
КОН
А := А - В
В := В - А
ДА
НЕТ
ДА
НЕТ

Псевдокод
(алгоритмический язык)
- Да легко!
Просто вычитайте из большего меньшее, пока они не сравняются!
Алг НОД
Цел А, В
НАЧ
Ввод А, В
Пока А ≠ В НЦ
Если A > B То
А := А – В
Иначе
В := В – А
Всё
КЦ
Вывод А
КОН