Разработка урока "Алгоритмы и программы"

Алгоритмы и программы

Понятие и свойства алгоритмов

Алгоритм — строго определенная последовательность действий для некоторого исполнителя, приводящая к поставленной цели или заданному результату за конечное число шагов.

Для выполнения алгоритма исполнителю необходимо иметь исходные (входные) данные — те, что задаются до начала алгоритма

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

• Дискретность
• Конечность
• Понятность
• Определенность(детерминированность)
• Массовость.

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

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

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

Словесные описания строго не формализуемы, поэтому может быть нарушено свойство определенности алгоритма: исполнитель может неточно понять описание этапа алгоритма. Словесная запись достаточно многословна. Сложные задачи трудно представить в словесной форме.

Пример 1. Записать в словесной форме правило деления обыкновенных дробей.

Решение.

Шаг 1. Числитель первой дроби умножить на знаменатель второй дроби.

Шаг 2. Знаменатель первой дроби умножить на числитель второй дроби.

Шаг 3. Записать дробь, числителем которой являет результат выполнения шага 1, знаменателем — результат выполнения шага 2

Блок-схема

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

Пример 4. Алгоритм целочисленных преобразований представлен в виде фрагмента блок–схемы. Знаком := в нем обозначен оператор присваивания некоторого значения указанной переменной. Запись X := 1 означает, что переменная Х принимает значение 1.

Определить результат работы алгоритма для исходных данных Х = 7, Y = 12.

Формальные алгоритмические языки

Алгоритмический язык — это искусственный язык (система обозначений), предназначенный для записи алгоритмов. Он позволяет представить алгоритм в виде текста, составленного по определенным правилам с использованием специальных служебных слов.

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

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

Псевдокод

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

Служебные слова учебного алгоритмического языка:

Стандартная структура алгоритма

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

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

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

Различают три основных вида алгоритмов (базовые алгоритмические конструкции, или структуры): линейные, с разветвлениями и с циклами.

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

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

Третий вид алгоритмов (с циклами ) обеспечивает многократное выполнение некоторой совокупности действий. Алгоритм, предписывающий повторное выполнение действий, называется циклическим алгоритмом (алгоритмом с повторением, или структурой цикла).

Линейные алгоритмические конструкции

В блок–схемах линейные алгоритмы представляют с помощью последовательности функциональных блоков:

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

Команда 1

Команда 2

Команда 3

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

Примеры

Пример 1. Определить значение целой переменной n после выполнения следующего алгоритма:

m := 3

n := 4

m := 6 + m*n

n := n + m/3

Пример 2. Вычислить значение выражения x2 – 3 × х – 10, используя только операции сложения и умножения

Алгоритмические конструкции ветвления

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

Существует две реализации структуры ветвления: полная и неполная (краткая). Обе формы ветвления являются замкнутыми: каждая из них имеет один вход и один выход.

Полная форма ветвления означает, что осуществляется выбор между двумя действиями. Если проверка условия дает результат «да», то выбирается действие 1; в противоположном случае (то есть если проверка условия дает результат «нет») — выбирается действие 2.

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

Примеры

Пример 1 . Для извлечения квадратного алгебраического корня из числа B необходимо проверить, положительно ли это число. Если проверка дает значение «истина» («да»), извлечь корень; если результат проверки — «ложь» («нет»), выдать соответствующее сообщение пользователю.

Краткая форма ветвления предполагает, что в случае истинности условия будет выполнена команда 1, а иначе — никакие действия не выполняются.

Полная и краткая формы структуры выбор

Полная и краткая формы структуры выбор различаются действиями после проверки последнего условия. Если проверка последнего условия выдает «ложь» («нет»), — в полной форме выполняют заданную команду; в краткой форме ничего не делают.

Циклические конструкции

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

ЦИКЛ С ПРЕДУСЛОВИЕМ (ИЛИ ЦИКЛ «ПОКА»)

Заголовок этой структуры содержит условие, которое называется предусловием. Эта структура предписывает повторять тело цикла до тех пор, пока выполняется условие в его заголовке (т. е. пока оно остается истинным).

Работа цикла с предусловием начинается с проверки условия в его заголовке. Если условие истинно — выполняются команды тела цикла и происходит возврат к заголовку цикла. Снова проверяется условие заголовка (поскольку оно могло измениться в результате работы команд цикла) — если оно истинно, опять выполняется тело цикла. Так происходит до тех пор, пока проверка условия в заголовке не выдаст результат «нет». Тогда управление будет передано команде, следующей непосредственно за циклом.

Возможна ситуация, когда команды тела цикла не будут выполнены ни разу — если условие в заголовке сразу же выдает результат проверки «нет». Также возможна ситуация, когда условие заголовка всегда выдает положительный результат проверки — это приведет к бесконечному выполнению цикла, так называемому «зацикливанию» алгоритма. Таким образом, при создании цикла «пока» следует обращать особое внимание на формулировку условия в его заголовке.

ЦИКЛ С ПОСТУСЛОВИЕМ (ИЛИ ЦИКЛ «ДО»)

Постусловие формулируется противоположным образом по отношению к предусловию. Цикл «до» предписывает повторять команды тела цикла до тех пор, пока не выполнится условие в его заголовке (т. е. пока оно остается ложным).

Работа цикла с постусловием начинается с выполнения команд тела цикла. Затем проверяется условие цикла. Если условие ложно (проверка условия дает результат «нет») — происходит возврат к выполнению команд тела цикла. Затем снова проверяется условие (поскольку оно могло измениться в результате работы команд цикла). Так происходит до тех пор, пока проверка условия не выдаст результат «да». Тогда происходит выход из цикла и управление будет передано команде, следующей непосредственно за циклом.

В отличие от цикла с предусловием, тело цикла «до» всегда выполняется хотя бы один раз (до первой проверки). Тело цикла «пока» может не выполниться ни разу, если условие при первой же проверке выдаст «нет». Поэтому цикл с постусловием можно заменить циклом с предусловием, а наоборот — нет

ЦИКЛ С ПАРАМЕТРОМ (ЦИКЛ СО СЧЕТЧИКОМ, ИЛИ ЦИКЛ «ДЛЯ»)

Эта структура предписывает повторять команды тела цикла для всех значений некоторой переменной (параметра, или счетчика цикла).

Имя параметра цикла (счетчика) указывают в заголовке после служебного слова для. Затем с помощью служебных слов от и до задают начальное и конечное значение этого параметра.

Работа цикла «для» начинается с присвоения параметру начального значения. Если оно не превышает конечного значения, выполняются команды тела цикла. Затем значение параметра цикла увеличивается на единицу. Если оно снова не превышает конечного значения, опять происходит выполнение тела цикла. Если же полученное значение параметра превысит конечное, цикл будет завершен и управление передано следующей за циклом команде.

Цикл со счетчиком всегда выполняется i1 – i2 + 1 раз.