Подготовка к ОГЭ 2021 года, занятие 8. Формальный исполнитель алгоритмов, записанных на алгоритмическом языке. Задание 6, часть 1

Подготовка к ОГЭ 2021 года, занятие 7, часть 1.

Формальный исполнитель алгоритмов, записанных на алгоритмическом языке. Задание 6

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

Алгоритм должен обладать следующими свойствами:

• понятность - означает, что он должен быть записан с помощью команд, понятных исполнителю этих команд;

• конечность – означает, что результат должен быть получен за конечное число шагов;

• точность – означает, что каждая команда алгоритма должна определять однозначное действие исполнителя;

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

Существует три вида алгоритмических конструкций:

• следование (линейные алгоритмы);

• ветвление (алгоритмы с использованием условий «если»);

• циклы (повторение одного или нескольких действий в одном месте программы).

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

- овал, означает начало или конец алгоритма;

- параллелограмм, означает ввод или вывод данных;

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

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

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

Пример линейного алгоритма «Утро школьника»:

• проснулся

• умылся

• позавтракал

• пошел в школу.

Пример блок-схемы линейного алгоритма дан на рис.1 Рис. 1

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

Пример алгоритма ветвления «Утро школьника»:

• Проснулся

• Если день будний, то:

• умылся;

• позавтракал;

• пошел в школу

• иначе:

• уснул снова.

Пример блок-схемы линейного алгоритма дан на рис.2. Рис.2.

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

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

в которой хранятся некоторые данные определённого типа.

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

При этом:

• имя (идентификатор) величины служит для обозначения величины в алгоритме и всегда начинается с буквы;

• тип величины показывает, какие значения может принимать величина и какие действия можно с ней выполнять (три основных типа: числовой, символьный и логический);

• значение величины содержит присвоенные ей данные.

Рассмотрим здесь структуру программы и основные операторы алгоритмического языка, используемые в условиях задач данного задания ОГЭ. Примером использования алгоритмического языка в школе является система КуМир.

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

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

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

• находит алгоритм в памяти;

• проверяет, соблюдаются ли начальные условия задачи;

• читает команды, записанные между словами нач и кон, и передает их исполнителю алгоритма (вызывает команду);

• заканчивает выполнение алгоритма.

Значение величины в процессе выполнения программы изменяется при помощи оператора присваивания, которая записывается в виде

имя величины := выражение

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

Важно:

• знаки двоеточия и равенства пишутся слитно;

• при записи значения в переменную старое значение в ней стирается.

Если же в операторе присваивания в правой части изменяется значение переменной, записанной в левой части, то это операция выполняется компьютером иначе.

Например, в операторе а := а + 1 компьютер сначала берет из памяти старое (существующее) значение переменной а, изменяет его (в данном примере увеличивает на 1), а затем записывает новое значение вместо старого. Будем далее называть такой оператор присваивания оператором накапливания.

Далее будем рассматривать операторы по мере их появления в рассматриваемых примерах.

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

Задача 1.

В программе := обозначает оператор присваивания, знаки +, -, * и / — соответственно операции сложения, вычитания, умножения и деления. Правила выполнения операций и порядок действий соответствуют правилам арифметики.

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

а := 7

b := 4

а := 2*а + 3*b

b := a/2*b

В ответе укажите одно целое число — значение переменной b.

Решение.

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

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

Ответ: 52

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

Задача 2.

Ниже приведена программа, записанная на алгоритмическом языке:

алг

нач

цел s, t

ввод s

ввод t

если s10 или t10

то вывод “ДА”

иначе вывод “НЕТ”

все

кон

Было проведено 9 запусков программы, при которых в качестве значений переменных вводились следующие пары чисел (s, t):

(1, 2); (11, 2); (1, 12); (11, 12); (–11, –12); (–11, 12); (–12, 11); (10, 10); (10, 5).

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

Решение.

Рассмотрим алгоритм данной задачи.

В начале объявляются целочисленными переменные s и t и читаются их начальные значения.

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

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

Следовательно, в подаваемых на ввод переменных нужно посчитать такие пары чисел, в которых выполняется хотя бы одно из условий, т.е. хотя бы одно из заданных чисел больше 10. Таких пар в условии пять:

(11, 2); (1, 12); (11, 12); (–11, 12); (–12, 11).

Ответ: 5