"Алгоритм и его формальное исполнение. Свойства алгоритмов."

Составитель: Портнова Е.С.

МБОУ «СОШ №65» г.Кемерово

Алгоритм и его формальное исполнение. Свойства алгоритмов.

« Алгоритм – это строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд.» (Н.Д. Угринович)

Понятие « алгоритм » появилось в Европе в XII веке, когда на латынь была переведена книга математика Мухаммеда ибн Муса ал- Хорезми, жившего в 783-850 годах.

Значение слова алгоритм очень схоже со значением слов рецепт, процесс, метод, способ.

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

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

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

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

Детерминированность

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

Точность

Конечность, результативность – алгоритм составляется для достижения результата и этот результат должен быть получен за конечное количество шагов.

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

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

Массовость

• язык программирования (этот способ записи алгоритма абсолютно формализован).

Пример . Определение чётности введенного числа.

BASIC

Pascal

INPUT “Введите целое число”; X

A $ =” четное ”

IF X MOD 20

THEN A$=” не ”+A$

PRINT “ Введенное число ”, A$

Var x: Integer;

Str: String;

Begin

Write (‘Введите целое число’);

ReadLn(x);

If x Mod 2 0

Then Str:=’ не ’+Str;

WriteLn (‘Введенное число ‘, Str );

End .

При описании любого языка используются следующие понятия:

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

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

начало/конец

ввод/вывод

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

подпрограмма

условие ветвления

условие цикла

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

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

начало

Действие 1

Действие 2

Действие N

конец

Алгоритмическая структура

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

Условие

Да

Нет

Действие 2

Действие 1

Алгоритмическая структура

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

Условие

Нет

Да

Действие

Алгоритмическая структура

«выбор»

Условие 1

Условие 2

Действие 1

Действие 3

Действие 2

Алгоритмическая структура

«цикл» Цикл со счётчиком

Нет

организац ия

счётчика

Да

Тело цикла

Алгоритмическая структура

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

Нет

Условие

Да

Тело цикла

Алгоритмическая структура

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

Тело цикла

Условие

Нет

Да

Задание

Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:

Вперед n , где n - целое число, вызывающая передвижение черепашки на n шагов в направлении движения.

Направо m , где m - целое число, вызывающая изменение направления движения на m градусов по часовой стрелке.

Запись Повтори 5 [Команда1 Команда2] означает, что последовательность команд в скобках выполняется 5 раз.

Черепашке был дан для исполнения следующий алгоритм:

Повтори 5 [вперед 10 направо 72]

Какая фигура появится на экране?

1) Незамкнутая ломаная линия

2) Правильный треугольник

3) Квадрат

4) Правильный пятиугольник.