Алгоритмы и исполнители — Информатика, 9 класс

Блок-схемы, формальное исполнение алгоритма, исполнители Вычислитель, Кузнечик и Чертёжник, дерево вариантов. 100 заданий на отработку.

Простыми словами

Исполнитель не догадывается, «что имел в виду автор», — он выполняет команды буквально. Поэтому и мы должны исполнять алгоритм так же: шаг за шагом, записывая значения переменных.

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

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

Блок-схемы: ветвление и цикл

Тело выполнится для

i = 1, 2, 3, 4

— 4 раза,

s = 40

Надёжный приём — трассировочная таблица: столбцы для каждой переменной и условия, строки для шагов.

шаг	$i$	$i \leq 4$ ?	$s$
0	1	да	0
1	2	да	10
2	3	да	20
3	4	да	30
4	5	нет	40

Проверяйте условие при каждом заходе в ромб с текущими значениями, особенно на границе ( $i = 4$ при условии $i \leq 4$ — ещё «да», при $i < 4$ — уже «нет»).

Вычислитель: сколько программ

Команды «прибавь 1» и «умножь на $m$ ». Число программ $K (v)$ , переводящих $a$ в $v$ , считают по возрастанию $v$ :

K (v) = K (v - 1) + K (v : m)

второе слагаемое — только если

v

делится на

m

v : m \geq a

;

K (a) = 1

Из 3 в 18, команды «+1» и «·2».

$v$	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
$K$	1	1	1	2	2	3	3	4	4	6	6	8	8	11	11	14

Например, $K (18) = K (17) + K (9) = 11 + 3 = 14$ . Ответ: 14.

Кузнечик и Чертёжник

Команды «Вперёд 7» и «Назад 8». Наименьшее число команд из 3 в 35.

Порядок команд не важен, важно их количество: $3 + 7 a - 8 b = 35$ , то есть $7 a - 8 b = 32$ .
$7 a$ должно делиться на 8 (так как $32$ и $8 b$ делятся на 8) ⇒ $a$ кратно 8. Наименьшее $a = 8$ : $56 - 8 b = 32$ , $b = 3$ .
Всего $8 + 3 = 11$ команд.

«Повтори 2 раза: сместиться на $(1, 3)$ , сместиться на $(- 2, 1)$ ; конец; сместиться на $(- 5, 6)$ ». Как вернуться в начало?

Тело цикла: $(1 - 2, 3 + 1) = (- 1, 4)$ ; два раза — $(- 2, 8)$ .
Итог: $(- 2 - 5, 8 + 6) = (- 7, 14)$ .
Возврат — противоположный вектор: $(7, - 14)$ .

Дерево вариантов

Код длины $k$ , каждый символ — из алфавита мощностью $N$ . На каждом шаге дерево ветвится на $N$ ветвей, число листьев:

Q = N^{k}

Q

— число различных кодов,

N

— число символов алфавита,

k

— длина кода

N = 2

k = 2

2^{2} = 4

кода

Коды длины 7 из алфавита ${A, B, C}$ : $3^{7} = 2187$ . Коды длины 5 из ${0, 1}$ : $2^{5} = 32$ .

Не перепутайте: основание степени — число символов алфавита, показатель — длина кода. $7^{3} = 343 \neq = 3^{7}$ .

Виды алгоритмов

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

Примеры заданий

Это несколько заданий из тренажёра, остальные — в тренажёре в начале страницы.

У исполнителя Вычислитель две команды: 1) прибавь 1, 2) умножь на 2. Сколько существует программ, которые число 3 преобразуют в число 18?

Показать ответ

Ответ: 14
Решение. Динамическим подсчётом от 3 до 18 получаем 14 программ.

ромб (решение) в блок-схеме обозначает

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

Показать ответ

Ответ: проверку условия (ветвление)
Решение. Ромб — блок проверки условия: из него выходят две ветви, «да» и «нет».

параллелограмм в блок-схеме обозначает

выполнение действия
ввод или вывод данных
проверку условия
конец алгоритма

Показать ответ

Ответ: ввод или вывод данных
Решение. Параллелограмм — блок ввода-вывода данных.

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

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

Показать ответ

Ответ: выполнение действия (вычисление)
Решение. Прямоугольник — блок обработки: присваивание, вычисление.

овал (скруглённый блок) в блок-схеме обозначает

начало или конец алгоритма
вывод данных
цикл
проверку условия

Показать ответ

Ответ: начало или конец алгоритма
Решение. Овал — терминатор: с него алгоритм начинается и им заканчивается.

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

линейным
циклическим
разветвляющимся
вспомогательным

Показать ответ

Ответ: циклическим
Решение. Циклический алгоритм содержит тело цикла, выполняемое многократно.

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

разветвляющимся
линейным
рекурсивным
циклическим

Показать ответ

Ответ: разветвляющимся
Решение. Разветвляющийся алгоритм содержит блок проверки условия и две ветви.

свойство алгоритма, означающее применимость к целому классу однотипных задач, — это

результативность
дискретность
массовость
определённость

Показать ответ

Ответ: массовость
Решение. Массовость: один алгоритм решает не одну задачу, а класс задач с разными исходными данными.