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

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

9 класс

Алгоритм – понятие фундаментальное, такое же, как «точка», «прямая», «информация». Поэтому точного и чёткого определения алгоритма не существует.

Однако можно дать некое понятие алгоритма, описывающее его основные признаки.

« Алгоритм – это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.» (А. Колмогоров)

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

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

« Алгоритм - организованная конечная последовательность действий, понятная исполнителю, чётко и однозначно задающая процесс решения класса задач и позволяющая получить за конечное число шагов результат, однозначно определяемый исходными данными.»

Историческая справка .

Понятие «алгоритм» появилось в Европе в 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

Алгоритмическая структура «цикл» Цикл со счётчиком

Нет

организация

счётчика

Да

Тело цикла

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

Нет

Условие

Да

Тело цикла

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

Тело цикла

Условие

Нет

Да

y x:=x-y y:=y-x" width="640"

Задание 1.

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

1) 1;

2) 5;

3) 10;

4) 15.

.

x:=55;

y:=75

нет

xy

да

да

нет

xy

x:=x-y

y:=y-x

Задание 2.

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

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

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

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

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

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

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

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

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

3) Квадрат

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

Задание 3.

Определите значение целочисленных переменных x , y и t после выполнения фрагмента программы (ниже представлена одна и та же программа, представленная на разных языках программирования) :

1) x=2; y=5; t=5;

2) x=7; y=5; t=5;

3) x=2; y=2; t=2;

4) x=5; y=5; t=5.

Бейсик

Паскаль

x=5

y=7

t=x

x=y MOD x

y=t

Алгоритмический

x:=5;

y:=7;

t:=x;

x:=y Mod x;

y:=t;

x:=5

y:=7

t:=x

x:=mod (x,y)

y:=t