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

Сегодня на уроке мы вспомним:

· что такое алгоритм;

· какие основные виды алгоритмов различают;

· рассмотрим типовые задания по анализу программы с условным оператором, которые могут быть на ОГЭ по информатике.

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

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

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

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

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

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

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

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

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

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

Вспомним подробнее об алгоритмических конструкциях.

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

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

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

Команда 1

Команда 2

Команда 3

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

Рассмотрим пример.

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

b := 20

а := 10

b := 7 + b / а

а := а + b * 2

Решение будет таким. В первых двух командах присваивания определены начальные значения переменных а и b. Чтобы выполнить третью команду сначала необходимо вычислить правую часть выражения: 7 + 20 / 10 = 9. Затем переменной b будет присвоено значение 9. Для выполнения последней команды также сначала вычисляется правая часть выражения: 10 + 9 ∙ 2 = 28. После переменой а будет присвоено значение 28. Это и будет ответом.

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

Например, нужно вычислить значение выражения y²-5y-7, используя только операции вычитания и умножения.

Алгоритм с ветвлением

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

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

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

Как мы помним, полная форма команды ЕСЛИ определяет две ветви команд: если условие истинно, то выполняется первая команда, вторая команда будет выполнена, если условие ложно. Каждая ветвь в итоге ведёт к общему выходу, и в таком случае работа алгоритма будет продолжаться при выборе любого пути.

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

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

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

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

Условия выбора играют важную роль во всех формах структур ветвления. Обычно в них используются операторы сравнения или другие отношения. Как мы помним результатом условия, может быть только одно из двух логических значений – «Ложь» или «Истина». В языках программирования эти значения записывают как True и False. В учебном алгоритмическом языке используют обычно значения «да» и «нет». А в компьютерной форме эти значения обычно представлены битовыми значениями 0 и 1.

В простых условиях обычно одна операция, например, а не равно бэ, икс больше зет и так далее. Составное условное выражение образуется из объединения нескольких простых условий. Чтобы объединить простые условия используют следующие логические операторы:

· and (логическое И);

· or (логическое ИЛИ);

· xor (исключающее ИЛИ);

· not (отрицание).

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

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

Цикл с предусловием, или цикл «пока»

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

В цикле с предусловием сначала проверяется условие в его заголовке. Если условие истинно, то следует выполнение команды тела цикла и происходит возврат к заголовку цикла. Затем снова проверяется условие заголовка, так как оно могло измениться в результате работы команд цикла: если оно истинно, то опять выполняется тело цикла. Так происходит до тех пор, пока проверка условия в заголовке не выдаст результат «нет». Тогда будет выполнена команда, которая следует непосредственно за циклом.

Следует обращать внимание на формулировку условия в его заголовке.

Так как могут возникнуть следующие ситуации:

· Команды тела цикла ни разу не будут выполнены. Такое может произойти, если условие в заголовке сразу же выдает результат проверки «нет».

· Условие заголовка всегда выдаёт положительный результат проверки. Это приведёт «зацикливанию» алгоритма, то есть к бесконечному выполнению цикла.

Цикл с постусловием, или цикл «до»

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

В цикле с постусловием сначала выполняются команды тела цикла. А затем проверяется условие цикла. Если условие ложно, то есть проверка условия даёт результат «нет», то выполняется возврат к выполнению команд тела цикла. После снова проверяется условие, так как оно могло измениться в результате работы команд цикла. Так происходит до тех пор, пока проверка условия не выдаст результат «да». Тогда выполняется выход из цикла и управление передаётся команде, которая следует непосредственно за циклом.

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

Цикл с постусловием можно заменить циклом с предусловием, а наоборот — нет, так как тело цикла «пока» может не выполниться ни разу, если условие при первой же проверке выдаст «нет».

Цикл с параметром, или цикл со счётчиком, или цикл «для»

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

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

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

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

Приведена программа, записанная на пяти языках программирования. Было проведено 9 запусков программы, при которых в качестве значений переменных s и t вводились следующие пары чисел:(8, 8); (9, 6); (4, 7); (6, 6); (–9, –2); (–5, 9); (–10, 10); (6, 9); (10, 6). Сколько было запусков, при которых программа напечатала «YES»?

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

У нас есть две переменные s и t целого типа, которые вводятся пользователем при помощи пользовательского ввода. S и t – это числа из пар: s – это первое число из пары, а t второе. Далее идёт условный оператор: если s больше восьми или t больше восьми, то программа должна вывести на экран «YES». В противном случае, если и первое и второе условия не выполняются, то на экране должно появится слово «NO».

То есть, чтобы на экране появилось слово «YES», должно выполнится хотя бы одно из условий, так как в условии стоит логический оператор ИЛИ.

Чтобы получить ответ, необходимо перебрать все пары. Например, пара (9, 6). 9 больше 8, значит уже можно сказать, что на экране появится слово «YES» и переменную тэ можно даже не проверять.

А вот пара (–9, –2) приведёт к выводу слова «NO» на экране, так оба числа меньше восьми.

В результате у нас получается, что вот эти пары приведут к выводу слова «YES» на экран:

(9, 6); (–5, 9); (–10, 10); (6, 9); (10, 6).

Значит ответом будет число 5.

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

Было проведено 9 запусков программы, при которых в качестве значений переменных s и t вводились следующие пары чисел: (6, 8); (3, 5); (–7, 2); (7, 7); (9, 8); (–1, 3); (–4, 5); (6, 9); (2, –1).

Сколько было запусков, при которых программа напечатала «NO»?

Проанализируем программу. В этот раз давайте возьмём вариант написанный на языке Паскаль.

У нас есть две переменные s и t, которые вводятся пользователем при помощи пользовательского ввода. Далее идёт условный оператор: если s больше 5 И t больше 5, то программа должна вывести на экран «YES». В противном случае, если какое-то из условий не выполняется, то на экране должно появится слово «NO».

То есть, чтобы на экране появилось слово «NO», то должно не выполнится хотя бы одно из условий, так как в условии стоит логический оператор И.

Например, пара (6, 8). 6 больше 5 и 8 больше 5, значит на экране появится слово «YES».

Пара (3,5). 3 меньше 5, значит уже можно сказать, что на экране появится слово «NO» и переменную тэ можно даже не проверять, так как не выполняется уже одно условие.

В результате у нас получается, что вот эти пары приведут к выводу слова «NO» на экран: (3, 5); (–7, 2); (–1, 3); (–4, 5); (2, –1).

Значит ответом будет снова число 5.

В конце урока попробуйте ответить на следующие вопросы:

Какие три основных вида алгоритмов различают?

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

Как называется структура ветвления, которая предполагает поочерёдную проверку нескольких условий (одно за одним)?

Внимательно посмотрев урок, вам не составит труда ответить на вопросы.