Формальный исполнитель алгоритмов, записанных на алгоритмическом языке.
ОГЭ, задание 6, часть 1.
Есть вопросы и замечания - пишите!
Алгоритм – понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящую от исходных данных к искомому результату.
Алгоритм должен обладать следующими свойствами:
- понятность - означает, что он должен быть записан с помощью команд, понятных исполнителю этих команд;
- конечность – означает, что результат должен быть получен за конечное число шагов;
- точность – означает, что каждая команда алгоритма должна определять однозначное действие исполнителя;
- дискретность – означает, что алгоритм должен быть разбит на последовательность отдельно выполняемых шагов.
Существует три вида алгоритмических конструкций:
- следование (линейные алгоритмы);
- ветвление (алгоритмы с использованием условий «если»);
- циклы (повторение одного или нескольких действий в одном месте программы).
Для наглядной записи алгоритмов используют блок-схемы. Вот некоторые элементы (блоки), их составляющие:
- овал, означает начало или конец алгоритма;
- параллелограмм, означает ввод или вывод данных;
- прямоугольник, означает выполняемое действие;
- ромб, означает выбор условия для дальнейшего выполнения алгоритма.
Линейными называются алгоритмы, при выполнении которых операторы выполняются в порядке их следования в алгоритме.
Пример линейного алгоритма «Утро школьника»:
- проснулся
- умылся
- позавтракал
- пошел в школу.
Пример блок-схемы линейного алгоритма дан на рис.1
В алгоритмах ветвления переход к тому или иному действию зависит от результата проверки поставленного условия, поэтому такие операторы называют так же операторами условного перехода.
Пример алгоритма ветвления «Утро школьника»:
- Проснулся
- Если день будний, то:
умылся;
позавтракал;
пошел в школу
- иначе:
уснул снова.
Пример блок-схемы линейного алгоритма дан на рис.2.
Обратите внимание, что ветка «нет» в алгоритме ветвления может отсутствовать, именно поэтому она данном примере обозначена неявно.
Для обозначения данных в алгоритмах и перевода их с человеческого языка в машинный код используется понятие величины. Величина – это именованная область оперативной памяти, в которой хранятся некоторые данные определённого типа.
По степени изменчивости величины в языках программирования бывают постоянными (константами), значения которым присваиваются перед началом выполнения программы и сохраняются свое до конца выполнения программы, и переменными, которые при выполнении программы принимают различные значения.
При этом:
- имя (идентификатор) величины служит для обозначения величины в алгоритме и всегда начинается с буквы;
- тип величины показывает, какие значения может принимать величина и какие действия можно с ней выполнять (три основных типа: числовой, символьный и логический);
- значение величины содержит присвоенные ей данные.
Рассмотрим здесь структуру программы и основные операторы алгоритмического языка, используемые в условиях задач данного задания ОГЭ. Примером использования алгоритмического языка в школе является система КуМир.
Слова алг, нач и кон называются служебными словами и служат для оформления алгоритма.
Часть алгоритма между словами нач и кон называются телом алгоритма. Тело алгоритма описывает решение задачи, в нем указывается, как достигается цель алгоритма.
Исполнение программы, состоящей из одного алгоритма, компьютер выполняет в следующем порядке:
- находит алгоритм в памяти;
- проверяет, соблюдаются ли начальные условия задачи;
- читает команды, записанные между словами нач и кон, и передает их исполнителю алгоритма (вызывает команду);
- заканчивает выполнение алгоритма.
Значение величины в процессе выполнения программы изменяется при помощи оператора присваивания, которая записывается в виде
имя величины := выражение
При выполнении оператора присваивания сначала вычисляется выражение в правой части оператора, а затем полученное значение записывается в память, отведенную для величины, указанной в левой части оператора присваивания.
Важно:
- знаки двоеточия и равенства пишутся слитно;
- при записи значения в переменную старое значение в ней стирается.
Если же в операторе присваивания в правой части изменяется значение переменной, записанной в левой части, то это операция выполняется компьютером иначе.
Например, в операторе а := а + 1 компьютер сначала берет из памяти старое (существующее) значение переменной а, изменяет его (в данном примере увеличивает на 1), а затем записывает новое значение вместо старого. Будем далее называть такой оператор присваивания оператором накапливания.
Далее будем рассматривать операторы по мере их появления в рассматриваемых примерах.
Линейный алгоритм
Задача 1.
В программе := обозначает оператор присваивания, знаки +, -, * и / — соответственно операции сложения, вычитания, умножения и деления. Правила выполнения операций и порядок действий соответствуют правилам арифметики.
Определите значение переменной b после выполнения алгоритма:
а := 7
b := 4
а := 2*а + 3*b
b := a/2*b
В ответе укажите одно целое число — значение переменной b.
Решение.
Будем записывать решение задачи в виде таблицы, где будем фиксировать все изменения с переменными, происходящие в каждом операторе.
При вычислениях арифметических выражений для установления приоритета операций пользуемся правилами математики.
Ответ: 52
Алгоритм ветвления
Задача 2.
Ниже приведена программа, записанная на алгоритмическом языке:
алг
нач
цел s, t
ввод s
ввод t
если s>10 или t>10
то вывод “ДА”
иначе вывод “НЕТ”
все
кон
Было проведено 9 запусков программы, при которых в качестве значений переменных вводились следующие пары чисел (s, t):
(1, 2); (11, 2); (1, 12); (11, 12); (–11, –12); (–11, 12); (–12, 11); (10, 10); (10, 5).
Сколько было запусков, при которых программа напечатала «YES»?
Решение.
Рассмотрим алгоритм данной задачи.
В начале объявляются целочисленными переменные s и t и читаются их начальные значения.
После этого работает ключевой оператор данной программы – если, оператор ветвления. В нем проверяются два условия, объединенные логической связкой или, и по результатам этой проверки выполняется переход либо к одному, либо к другому действию. Поэтому оператор если иначе называется оператором условного перехода.
Из математической логики знаем, что логическое выражение s>10 или t>10 будет ложным, если обе части выражения ложны и истинны во всех остальных случаях.
Следовательно, в подаваемых на ввод переменных нужно посчитать такие пары чисел, в которых выполняется хотя бы одно из условий, т.е. хотя бы одно из заданных чисел больше 10. Таких пар в условии пять:
(11, 2); (1, 12); (11, 12); (–11, 12); (–12, 11).
Ответ: 5
