Серия презентаций по теме "Основы алгоритмизации"

Основы алгоритмизации

Лекция 3

I. Понятие алгоритма

Алгоритм - понятное и точное предписание (указание) исполнителю совершить последовательность действий, направленных на достижение указанной цели или на решение поставленной задачи

от algorithmi – латинской формы написания имени великого математика IX века аль-Хорезми , который сформулировал правила выполнения арифметических действий

Примеры:

Вычислить значение у по формуле

Чтобы решить эту задачу, достаточно выполнить последовательность следующих действий:

1. Умножить А на х, результат обозначить R 1 .

2. R 1 сложить с В, результат обозначить R 2 .

3. Умножить С на х, результат обозначить R 3 .

4. Из R 3 вычесть Д, результат обозначить R 4 .

5. Умножить R 2 на R 4 , считать результат значением у.

0.   Алгоритм построения имеет следующий вид: 1. Строим прямоугольную декартову систему координат. 2. Строим график функции . 3. Стираем часть графика левее оси ординат ОУ. 4. Симметрично отображаем оставшуюся часть графика относительно оси ОУ. " width="640"

Примеры:

Построить график функции при а0.

Алгоритм построения имеет следующий вид:

1. Строим прямоугольную декартову систему координат.

2. Строим график функции .

3. Стираем часть графика левее оси ординат ОУ.

4. Симметрично отображаем оставшуюся часть графика относительно оси ОУ.

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

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

Поочередное выполнение команд алгоритма за конечное число шагов приводит к решению поставленной задачи

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

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

II. Формальное исполнение алгоритма

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

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

III. Алгоритмический язык

Алгоритмический язык – это система обозначений и правил для единообразной и точной записи алгоритмов и их исполнения.

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

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

III. Алгоритмический язык

Алгоритм, записанный на алгоритмическом языке, должен иметь название . Название выбирается так, чтобы было ясно, решение какой задачи описывает данный алгоритм. Для выделения названия алгоритма перед ним записывается служебное слово АЛГ (алгоритм) .

За названием алгоритма (обычно с новой строки) записываются его команды. Для указания начала и конца алгоритма его команды заключаются в пару служебных слов НАЧ (начало) и КОН (конец) . Команды записываются последовательно. При записи одной команды можно перейти на другую строчку. Если несколько команд записываются на одной строке, то они разделяются точкой с запятой ( ; ).

Общий вид алгоритма, записанного на алгоритмическом языке:

АЛГ название алгоритма

НАЧ

команды алгоритма

КОН

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

• Точность
• Понятность
• Массовость
• Результативность.

V. Составные команды и их типы

Существуют несколько типов алгоритмов:

1. линейные,

2. разветвляющиеся ,

3. циклические.

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

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

VI. Команда ветвления

Команда ветвления записывается следующим образом:

ЕСЛИ условие

ТО серия 1

ИНАЧЕ серия 2

ВСЕ

В зависимости от условия выполняется только одна из двух серий команд, входящих в команду ветвления. Если условие соблюдено, то надо выполнить серию 1, а если нет – серию 2.

Команды из каждой серии выполняются подряд , каждая по своим правилам. Команда ветвления заканчивается, как только выполнится последняя команда из серии 1 или серии 2.

Блок-схема для полной формы записи команды ветвления имеет вид:

Команда ветвления используется и в сокращенной форме:

ЕСЛИ условие

ТО серия

ВСЕ

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

Блок-схема для сокращенной формы записи команды ветвления имеет вид:

Пример

Составить программу для вычисления значения F по формуле:

VII. Команда повторения (цикла)

Использование команд повторения позволяет с помощью сравнительно коротких алгоритмов записывать предписания о совершении очень длинной последовательности действий.

Команда повторения записывается следующим образом:

ПОКА условие

НЦ

серия

КЦ

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

Если условие не соблюдается с самого начала, то серия команд не выполняется ни разу. Условие цикла проверяется перед выполнением серии, но не в процессе ее выполнения.

Блок-схема команды повторения имеет вид:

Пример

1. Написать алгоритм суммирования всех чисел от 1 до 10 и начертить блок-схему, т.е. необходимо вычислить: .

2. Написать алгоритм и нарисовать блок-схему вычисления суммы только четных чисел от 1 до 10.

Задание на дом

• Сформулируйте и запишите алгоритм вычисления у по формуле:

2. По приведенному алгоритму восстановите формулу для вычисления значения у.

  1. Умножить х на х, результат обозначить R 1 .

2. Умножить R 1 на а, результат обозначить R 2 .

3. Сложить R 2 с в, результат обозначить R 3 .

4. Разделить R 3 на с, результат считать значением у.

Задание на дом

3. Составить блок-схему и написать алгоритм вычисления F по формуле:

4. Нарисовать блок-схему и записать алгоритм вычисления суммы чисел от 1 до 40, кратных 5.

Литература:

1. Основы информатики и вычислительной техники: Проб. учеб. пособие для сред. учеб. заведений. В 2-х ч. Ч.1/ А.П. Ершов, В.М. Монахов, С.А. Бешенков и др. – М.: Просвещение, 1985. – 96 с., ил., Часть 1, с. 17 – 29.

VIII. Величины и их типы

Постоянной называется величина, значение которой не меняется в процессе исполнения алгоритма, а остается одним и тем же, указанным в тексте алгоритма

Переменной называется величина, значение которой меняется в процессе исполнения алгоритма.

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

VIII. Величины и их типы

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

В процессе исполнения алгоритма величина может не получить конкретного значения. Такая величина называется неопределенной .

VIII. Величины и их типы

Сокращенно типы переменных обозначаются словами

НАТ (натуральный)

ЦЕЛ (целый)

ВЕЩ (вещественный)

ЛИТ (литерный) и т.д

Величины, значениями которых являются слова или текст, называются литерными .

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

Общий вид заголовка имеет вид:

  АЛГ название алгоритма (список величин с указанием типов)

АРГ имена аргументов

РЕЗ имена результатов

Имена аргументов и результатов алгоритма перечисляются через запятую.

Общий вид заголовка имеет вид:

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

Ее тип также должен быть указан исполнителю, а описание приводится после служебного слова НАЧ .

Пример

.

Рассмотрим запись алгоритма работы с величинами на примере алгоритма решения квадратного уравнения

Алгоритм имеет вид:

.

АЛГ решение квадратного уравнения ( ВЕЩ а, в, с, х 1 , х 2 , ЛИТ у)

АРГ а, в, с

РЕЗ х 1 , х 2 , у

НАЧ ВЕЩ D

ЕСЛИ D

ТО у: = «нет решения»

ИНАЧЕ у: = «есть решение»

;

ВСЕ

КОН

Знак присваивания : =

.

• делит команду присваивания на левую и правую части ; в левой части может стоять любая переменная величина алгоритма, а в правой части - любое числовое или нечисловое выражение ;
• нельзя путать со знаком математического равенства «=». Знак «: =» указывает исполнителю действие (присвоить переменной вычисленное значение), в то время как знак «=» никаких действий не предполагает .

Пример

.

• Составить блок-схему и записать алгоритм вычисления значения у по формуле:

Пример

.

Пример

.

АЛГ вычисление у ( ВЕЩ х, у, ЛИТ g )

АРГ х

РЕЗ у

НАЧ ВЕЩ R 1 , R 2 , R 3 , R 4

R 1 : = х 2 ; R 2 : = 6 R 1 ; R 3 : = х + R 2

ЕСЛИ х

ТО g : = «выражение не существует»

ИНАЧЕ g : = «выражение существует»

R 4 : =

ВСЕ

у = R 3 · R 4

запись ответа

КОН

Задание на дом

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

Дополнительное задание

• Составить алгоритм и блок-схему вычисления суммы квадратов всех четных и кубов всех нечетных чисел на промежутке от 1 до 10