5.2. Разработка алгоритма

Информатика, 7 класс. Учебник: Кадыркулов Р. А., Рыскулбекова А. Д., Нурмуханбетова Г. К. (Алматыкітап баспасы, 2023). Раздел 5: Практическое программирование. Страницы 144–148.

Чему научишься

• Называть четыре свойства алгоритма: дискретность, определённость, результативность, массовость.
• Описывать алгоритм тремя способами: словами, блок-схемой, псевдокодом.
• Писать готовые алгоритмы: среднее арифметическое, наибольшее и наименьшее из трёх чисел.
• Собирать решение задачи из нескольких готовых алгоритмов.
• Рисовать блок-схемы и по ним писать программы на Python.

Разминка

• С какими свойствами алгоритма ты уже знаком? Алгоритм состоит из шагов (дискретность), команды понятны исполнителю (определённость), ответ получается за конечное число шагов (результативность) и подходит для целого класса задач (массовость).
• Какие готовые алгоритмы ты знаешь? Например: найти наибольшее из чисел, найти среднее арифметическое, достать цифры из числа, проверить число на чётность.
• Какие разветвляющиеся алгоритмы самые удобные? Те, где проверок немного и они простые. Скажем, наибольшее из трёх чисел находят двумя проверками подряд, а не перебором всех пар.

Разбираемся

Какие алгоритмы понимает компьютер

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

🌟 Слово «алгоритм» произошло от имени учёного аль-Хорезми, который жил в Средней Азии в IX веке и написал книгу об арифметических правилах. А как предмет научных исследований алгоритмы стали изучать в 1930-х годах.

У хорошего алгоритма четыре свойства.

Три способа записать алгоритм

Возьмём простую задачу: определить, чётное ли число n.

1. Словами. Введи n. Найди остаток от деления n на 2. Если остаток 0, скажи «чётное», иначе «нечётное».
2. Блок-схемой. Это рисунок из фигур, соединённых стрелками.
3. Псевдокодом. Это запись текстом, похожая на программу, но без строгих правил языка.

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

        (Начало)
            |
        /ввод n/
            |
       <n % 2 = 0 ?>
   Да /            \ Нет
/вывод «чётное»/  /вывод «нечётное»/
       \            /
         (Конец)

Псевдокод той же задачи:

ввод n
если остаток от деления n на 2 равен 0
    то вывод «чётное»
    иначе вывод «нечётное»

А вот код на Python:

n = int(input())
if n % 2 == 0:            # остаток от деления на 2 равен нулю?
    print("чётное")
else:
    print("нечётное")

💡 Блок-схема лучше всех показывает, куда «разветвляется» программа. Поэтому для ветвлений её рисуют чаще всего.

Готовые кирпичики

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

Наибольшее из трёх. Берём первое число за «рекордсмена» и сравниваем с остальными: если следующее больше, оно становится новым рекордсменом.

a = int(input())
b = int(input())
c = int(input())
big = a              # пока рекордсмен — первое число
if b > big:          # второе круче?
    big = b
if c > big:          # третье круче?
    big = c
print(big)

Наименьшее из трёх. Так же, только знак наоборот.

a = int(input())
b = int(input())
c = int(input())
small = a            # пока самое маленькое — первое число
if b < small:
    small = b
if c < small:
    small = c
print(small)

Среднее арифметическое. Сумма, делённая на количество.

a = int(input())
b = int(input())
c = int(input())
avg = (a + b + c) / 3   # скобки обязательны: иначе делится только c
print(avg)

Запускали все три программы: для 4, 9, 6 получается 9, 4 и 6.333333333333333.

🌟 В Python есть готовые функции max() и min(), и ими пользуются в настоящей работе. Но сейчас мы учимся, как они устроены внутри. Не называй свои переменные max и min: тогда настоящие функции перестанут работать в этой программе.

Собираем из кирпичиков: три магазина

Задача. В трёх магазинах один и тот же телефон стоит 240000, 200000 и 220000 тенге. Найди среднюю цену и ответь, на сколько процентов самый дорогой телефон дороже самого дешёвого.

Нужны сразу три готовых алгоритма: среднее, наибольшее и наименьшее. Склеиваем их в одну программу.

a = int(input())          # цена в первом магазине
b = int(input())          # во втором
c = int(input())          # в третьем
avg = (a + b + c) / 3     # кирпичик 1: среднее арифметическое
big = a                   # кирпичик 2: наибольшая цена
if b > big:
    big = b
if c > big:
    big = c
small = a                 # кирпичик 3: наименьшая цена
if b < small:
    small = b
if c < small:
    small = c
print("Средняя цена =", avg)
print((big - small) / small * 100, "%")   # на сколько процентов дороже

Для 240000, 200000, 220000 программа выведет:

Средняя цена = 220000.0
20.0 %

Проверка вручную: (240000 − 200000) / 200000 = 0,2, то есть 20 %.

📕 В учебнике в похожем примере про зарплаты (200000, 100000, 150000) написано, что максимальная зарплата больше минимальной на 200 %, и в программе стоит (max/min)*100. Но правильно «на 100 %» и формула (big - small) / small * 100: эта формула считает, на сколько больше, а (max/min)*100 показывает, сколько процентов составляет большее число от меньшего (200 % — это «в два раза», а не «на 200 % больше»).

⚠️ Частая ошибка. Деление без скобок. a + b + c / 3 делит на 3 только c. Среднее — это (a + b + c) / 3.

👨‍👩‍👧 Родителю. Предложите ребёнку записать «алгоритм» бытового дела (заварить чай, собраться в школу) и найти в нём слабое место: где команда неоднозначна («немного подождать») или шаг пропущен. Так свойства алгоритма превращаются из слов в инструмент.

Проверь себя

• Назови свойства алгоритма и объясни одно из них своими словами. Дискретность, определённость, результативность, массовость. Например, результативность значит, что алгоритм заканчивается и даёт ответ за конечное число шагов.
• Какими тремя способами можно описать алгоритм? Словами или формулами, блок-схемой, псевдокодом.
• Что означает ромб в блок-схеме? Проверку условия. Из него выходят две стрелки: «Да» и «Нет».
• Зачем использовать готовые алгоритмы? Не нужно изобретать одно и то же заново, меньше ошибок, а сложную задачу легко собрать из знакомых частей.
• Чем отличаются (max - min) / min * 100 и max / min * 100? Первое считает, на сколько процентов больше, второе показывает, сколько процентов составляет большее от меньшего.

Решаем упражнения

Практическая работа

№ 1 · «Практическая работа»

Анализ. Сравни схемы 1, 2, 3 с программами на рис. 1, 2, 3 (наименьшее, наибольшее, среднее арифметическое). Затем разработай блок-схему для программы «Заработная плата» с рис. 4: три зарплаты, среднее арифметическое, наибольшая и наименьшая, и на сколько процентов наибольшая больше наименьшей.

Как думать. Каждая строка кода соответствует одной фигуре: ввод — параллелограмм, присваивание — прямоугольник, if — ромб, print — параллелограмм вывода. Если рядом стоит блок-схема и код, их можно читать парами.

Решение.

1. Сравнение. Схема 1 (наименьшее): min = a, потом ромб «b < min?» с «Да → min = b», потом ромб «c < min?» с «Да → min = c», вывод min. Это один в один код с рис. 3. Схема 2 (наибольшее) отличается знаками > и переменной max. Схема 3 (среднее): ввод, прямоугольник k = (a + b + c) / 3, вывод k. Это код рис. 1, где в k = {a + b + c} / 3 печатные фигурные скобки надо читать как обычные круглые.

📕 На рис. 1 в учебнике напечатано k={a+b+c}/3 (фигурные скобки), но правильно k=(a+b+c)/3: в Python фигурные скобки создают множество, и деление множества на 3 вызовет ошибку. На схеме 3 и на рис. 4 стоят правильные круглые скобки.

2. Блок-схема программы «Заработная плата»:

(Начало)
   |
/ввод a, b, c/
   |
[k = (a + b + c) / 3]
   |
[big = a]
   |
<b > big ?> --Да--> [big = b]
   | Нет                |
   +<-------------------+
   |
<c > big ?> --Да--> [big = c]
   | Нет                |
   +<-------------------+
   |
[small = a]
   |
<b < small ?> --Да--> [small = b]
   | Нет                  |
   +<---------------------+
   |
<c < small ?> --Да--> [small = c]
   | Нет                  |
   +<---------------------+
   |
/вывод: средняя зарплата, k/
   |
/вывод: (big - small) / small * 100, «%»/
   |
(Конец)

Программа по этой блок-схеме (пример 200000, 100000, 150000):

a = int(input())
b = int(input())
c = int(input())
k = (a + b + c) / 3              # среднее арифметическое
big = a                          # наибольшая
if b > big:
    big = b
if c > big:
    big = c
small = a                        # наименьшая
if b < small:
    small = b
if c < small:
    small = c
print("Средняя зарплата =", k)
print((big - small) / small * 100, "%")   # на сколько процентов наибольшая больше наименьшей

Запуск для 200000, 100000, 150000 печатает «Средняя зарплата = 150000.0» и «100.0 %». Если взять формулу учебника max / min * 100, получится 200.0 %; про эту разницу мы написали выше (📕).

Ответ: три схемы соответствуют трём кодам по парам; блок-схема программы «Заработная плата» показана выше: ввод, среднее, поиск наибольшего (два ромба), поиск наименьшего (два ромба), два вывода.

№ 2 · «Практическая работа»

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

Как думать. Возьми жизненную ситуацию, где есть сразу «среднее» и «лучшее/худшее». Например, забег на 60 метров.

Пример ответа. Задача. Три ученика пробежали дистанцию за 12, 15 и 18 секунд. Найди среднее время и на сколько секунд самый медленный отстал от самого быстрого. Здесь работают три алгоритма: среднее арифметическое, наименьшее и наибольшее.

a = int(input())          # время первого, с
b = int(input())          # время второго
c = int(input())          # время третьего
avg = (a + b + c) / 3     # алгоритм «среднее»
best = a                  # алгоритм «наименьшее»: лучшее время
if b < best:
    best = b
if c < best:
    best = c
worst = a                 # алгоритм «наибольшее»: худшее время
if b > worst:
    worst = b
if c > worst:
    worst = c
print("Среднее время", avg)
print("Отставание последнего от лучшего", worst - best)

Для 12, 15, 18 программа выводит «Среднее время 15.0» и «Отставание последнего от лучшего 6». Мы запускали её на этих данных.

Ответ: пример задачи про забег выше; в ней используются алгоритмы среднего арифметического, наименьшего и наибольшего.

№ 3 · «Практическая работа»

Оценка. Насколько важно использовать известные алгоритмы при разработке программы для решения задачи?

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

Пример ответа. Это очень важно. Готовый алгоритм уже проверен тысячами программистов, поэтому в нём меньше ошибок. Он экономит время, ведь не надо придумывать то, что уже придумано. Сложную задачу удобно разбить на части и для каждой взять знакомый «кирпичик», как мы делали в задаче про магазины.

Ответ: важно: готовые алгоритмы надёжны, экономят время и помогают собирать сложные программы из простых частей.

Вопросы для размышления

№ 4 · «Вопросы для размышления», вопрос 1

Почему важно знать свойства алгоритмов, когда разрабатываешь конкретный алгоритм?

Как думать. Свойства — это список проверок: если алгоритм их не проходит, он работать не будет.

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

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

№ 5 · «Вопросы для размышления», вопрос 2

Какие способы описания алгоритмов ты знаешь? Насколько важно их использование при разработке программ?

Как думать. Вспомни три способа из урока и скажи, когда какой удобнее.

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

Ответ: словесное описание, блок-схема, псевдокод; они помогают продумать решение до написания кода.

№ 6 · «Вопросы для размышления», вопрос 3

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

Как думать. Это вопрос на мнение, но его нужно обосновать.

Пример ответа. Для задач с ветвлениями удобнее всего блок-схема: сразу видно, где программа «разветвляется». Для линейных задач (ввод, формула, вывод) хватит словесного описания или псевдокода. Лучший способ — тот, при котором ты точнее всего видишь ход решения.

Ответ: для ветвлений удобнее блок-схема, для простых задач достаточно слов или псевдокода.

Задание

№ 7

«Задание», задание 1 (метка «*», базовый уровень). Если трёхзначное число N чётное, его последняя цифра больше 5 и оно читается одинаково слева направо и справа налево (палиндром), выведи «1», иначе «0». Нарисуй блок-схему. Примеры: 636 даёт 1, 434 даёт 0.

Как думать. Палиндром из трёх цифр: первая цифра равна последней. Чётность и «больше 5» проверяем по последней цифре. Все три условия должны выполняться одновременно, значит, между ними нужен and.

Решение. Блок-схема:

(Начало)
   |
/ввод N/
   |
[first = N // 100]
[last = N % 10]
   |
<N чётное И last > 5 И first = last ?>
  Да |                    | Нет
/вывод 1/              /вывод 0/
     \_____________  _____/
                   (Конец)

Программа:

n = int(input())
first = n // 100        # первая цифра
last = n % 10           # последняя цифра
if n % 2 == 0 and last > 5 and first == last:
    print(1)
else:
    print(0)

Тесты (запускали): 636 → 1; 434 → 0; 828 → 1; 626 → 1; 737 → 0 (нечётное); 646 → 1; 100 → 0.

Ответ: программа выше; для 636 выводится 1, для 434 выводится 0. Подходят только числа вида 6x6 и 8x8.

№ 8

«Задание», задание 2 (метка «**», средний уровень). Алгоритм из схемы 5: ввод x и y; если x = 0, вывести «ошибка»; иначе z = x // y и вывести x, y, z. Вычисли результат для а) x = 0, y = 1; б) x = 2, y = 4; в) x = 6, y = 0. Затем 1) запиши соответствующий схеме код; 2) определи условие задачи по результатам и коду.

Как думать. Просто идём по схеме. Сначала смотрим, чему равно x. Но заметь: делим на y, а не на x. Что случится, если y = 0?

📕 В схеме 5 условие стоит «x = 0?», но делят на y. Ошибка «деление на ноль» возникает при y = 0, а не при x = 0. Правильно проверять y == 0.

Решение.

1. Код строго по схеме, как напечатано:

x = int(input())
y = int(input())
if x == 0:
    print("ошибка")
else:
    z = x // y
    print(x, y, z)

2. Результаты по этой схеме:

Запуск подтвердил все три строки.

3. Исправленная схема (проверка y = 0) — это и есть «задача, которую решает алгоритм»: даны два целых числа x и y; найти целую часть частного x // y; если делить нельзя, вывести «ошибка».

x = int(input())
y = int(input())
if y == 0:                # делить на ноль нельзя
    print("ошибка")
else:
    z = x // y            # целая часть частного
    print(x, y, z)

Результаты исправленной программы:

Ответ: по схеме как напечатано: а) «ошибка»; б) 2 4 0; в) сбой из-за деления на ноль. Условие задачи: найти целую часть частного x // y, а при делении на ноль (y = 0) вывести «ошибка». Правильная проверка — y == 0.

№ 9

«Задание», задание 3 (метка «**», средний уровень). Даны действительные числа X и Y, не равные друг другу. Меньшее из них замени на их среднее арифметическое, а большее на их произведение. Представь алгоритм блок-схемой и запиши код. Если введены равные числа, выведи их сумму. Примеры: 20 10 даёт 200 15, 20 20 даёт 40.

Как думать. Сначала проверим равенство. Если числа разные, считаем сразу и среднее, и произведение, пока исходные числа не изменились. Потом смотрим, какое из них было меньше.

Решение. Блок-схема:

(Начало)
   |
/ввод X, Y/
   |
<X = Y ?> --Да--> /вывод X + Y/ --------+
   | Нет                                |
[mean = (X + Y) / 2]                    |
[prod = X * Y]                          |
   |                                    |
<X < Y ?> --Да--> [X = mean; Y = prod]  |
   | Нет               |                |
[X = prod; Y = mean]   |                |
   |                   |                |
   +-------------------+                |
   |                                    |
/вывод X, Y/                            |
   |                                    |
(Конец) <-------------------------------+

Программа:

x, y = map(float, input().split())
if x == y:
    print(x + y)              # числа равны: выводим сумму
else:
    mean = (x + y) / 2        # среднее арифметическое
    prod = x * y              # произведение
    if x < y:                 # x меньше: он становится средним, y становится произведением
        x = mean
        y = prod
    else:
        x = prod
        y = mean
    print(x, y)

Тесты (запускали программу):

Числа получились дробными (с .0) потому, что мы читаем их как float: «действительные числа» по условию. Значение то же, что в примере учебника: 200 15 и 40.

Ответ: блок-схема и программа выше; для 20 10 получаем 200 и 15, для 20 20 получаем 40.

Домашнее задание

№ 10 · «Домашнее задание», задание 1

Напиши эссе (70–100 слов) о том, насколько важно уметь составлять алгоритмы и знать их свойства. Приведи примеры из жизни.

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

Пример ответа. (Всего 74 слова.)

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

Ответ: любое связное эссе на 70–100 слов с примером из жизни; образец выше.

Шпаргалка

Термины: алгоритм, дискретность, определённость, результативность, массовость, блок-схема, псевдокод, разработка алгоритма, выполнение алгоритма.

Мини-тест