Статья Автор: Деникина Н.В., Деникин А.В.

Считаем в Python. Инструменты

Почему аккуратные люди ошибаются в задании 7

Формулы тут простые. Сложность в другом: чисел много, они большие, и между ними прячутся переводы единиц.

Умножил, поделил на 8, поделил на 1024, где-то округлил — и одна пропущенная тысяча двадцать четвёртая рушит ответ.

На экзамене под рукой компьютер. Пять строк считают ту же цепочку без единой ошибки.

Первый инструмент: глубина цвета через логарифм

Вопрос «сколько бит нужно на один пиксель, если цветов K» — это тот же вопрос, что и про символы алфавита. В какую степень возвести двойку, чтобы получилось не меньше K.

Отвечает math.log2, а math.ceil поднимает результат до целого.

import math

colors = 256                 # сколько цветов в палитре
depth = math.ceil(math.log2(colors))
print(depth)

Вывод программы:

Ловушка, которая портит именно это задание

Часто пишут int(math.log2(colors)) + 1 — «отбросить дробь и прибавить единицу». Смотри, что выходит.

import math

for colors in [2, 16, 256, 65536]:
    print(colors, int(math.log2(colors)) + 1, math.ceil(math.log2(colors)))

Вывод программы:

2 2 1
16 5 4
256 9 8
65536 17 16

Разбор

Для 256 цветов логарифм равен ровно 8, дробной части нет. Отбрасывать нечего, а единицу мы прибавили — получилось 9 бит вместо 8.

И так на всех точных степенях двойки. А в задании 7 палитра почти всегда именно такая: 2, 16, 256, 65536 цветов.

То есть ошибка срабатывает не в редком случае, а в самом частом.

Пиши math.ceil, а не int(...) + 1.

Второй инструмент: целые числа вместо дробей

В задании 7 объёмы делятся на 8 и на 1024. Если использовать обычное деление /, результат становится дробным, и в нём копится погрешность (если эти операции не последние). Обычное деление // даёт целое, округляя вниз. А когда нужно вверх — поделить нацело и добавить единицу, если остался остаток. Проверяй остаток (операция %) и прибавляй 1, если он больше нуля.

Микропаттерн «Держи всё в битах и целых». Переводи в биты в самом начале, считай целыми, переводи в Кбайт в самом конце. Если деление последняя операция (ты переводишь результатв Кбайты или Мбайты), можешь вывести и результат обычного деления, но в ответ всегда целое число - округли в нужную сторону!

Пример: афиша фестиваля

Растровое изображение 1024 × 768 точек, палитра 256 цветов. Считаем объём.

Данные — сверху, формулы — снизу, каждая строка отвечает за одно действие.

import math

w = 512                     # ширина в пикселях
h = 3                      # высота в пикселях
colors = 200                 # цветов в палитре

depth = math.ceil(math.log2(colors))   # бит на пиксель
bits = w * h * depth                   # бит на всё изображение
byte = bits / 8                       # байт
kb = byte / 1024                      # Кбайт

print(depth, bits, byte, kb)

Вывод программы:

8 6291456 786432 768

Пример: заставка

Звук считается так же: перемножаем частоту, время, разрядность и число каналов.

freq = 16000                 # частота дискретизации, Гц
sec = 40                     # длительность, с
depth = 16                   # разрядность, бит
channels = 2                 # стерео

bits = freq * sec * depth * channels
byte = bits / 8
kb = byte / 1024

print(bits, byte, kb)

Вывод программы:

20480000 2560000 2500

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

Третий инструмент: перебор для «наибольшего» и «наименьшего»

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

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

Перебор эту развилку убирает. Наращиваем величину по одному шагу, пока помещаемся в лимит.

Микропаттерн «Не уверен в округлении — перебирай». Условие цикла дословно повторяет условие задачи: «влезает ли ещё один».

Пример: сколько цветов поместится

Изображение 1024 × 768 нужно уместить в 512 Кбайт. Какое наибольшее количество цветов может быть в палитре?

Сначала делением: переводим лимит в биты и смотрим, сколько бит достаётся одному пикселю.

limit = 512 * 1024 * 8       # отведено 512 Кбайт, переводим в биты
w = 1024
h = 768

depth = limit // (w * h)     # сколько бит достаётся одному пикселю
colors = 2 ** depth
print(depth, colors)

Вывод программы:

5 32

Теперь то же перебором

Наращиваем глубину цвета, пока изображение помещается в лимит.

limit = 512 * 1024 * 8       # отведено 512 Кбайт в битах
w = 1024
h = 768

depth = 1
while (depth + 1) * w * h <= limit:
    depth = depth + 1
print(depth, 2 ** depth)

Вывод программы:

5 32

Оба способа дали одно

Глубина 5 бит, палитра 32 цвета.

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

Обязательно проверь границу: 5 бит дают объём ровно в лимит, а 6 бита — уже больше. Значит 5 — действительно наибольшее.

Пример: сколько секунд поместится

Звук записывают с частотой 16 кГц, разрядностью 16 бит, в стерео. Файл не должен превысить 2 Мбайт. Какова наибольшая длительность записи в секундах?

Тот же приём: добавляем по секунде, пока помещаемся.

limit = 2 * 1024 * 1024 * 8  # 2 Мбайт в битах
freq = 16000
depth = 16
channels = 2

sec = 0
while (sec + 1) * freq * depth * channels <= limit:
    sec = sec + 1
print(sec)

Вывод программы:

Пример: время передачи

Файл объёмом 768 Кбайт передают по каналу со скоростью 1048576 бит в секунду. Сколько секунд займёт передача?

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

size_kb = 768           # объём файла, Кбайт
speed = 1048576         # скорость канала, бит в секунду

bits = size_kb * 1024 * 8

sec = bits // speed     # сколько целых секунд
if bits % speed > 0:
    sec = sec + 1       # остался хвост - нужна ещё секунда

print(bits)
print(sec)

Вывод программы:

6291456
6

Проверим руками: 6291456 ÷ 1048576 = ровно 6. Здесь разделилось нацело, остатка нет — поэтому if не сработал.

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

Микропаттерн «Есть остаток — добавь единицу». Это то же самое, что на бумаге: «5,4 секунды, значит 6».

Ловушки счёта на компьютере

Написали int(math.log2(k)) + 1. Неверно на 2, 16, 256, 65536 цветах — то есть почти всегда.
Забыли import math. Без него ни ceil, ни log2 не работают.
Поделили на 1000 вместо 1024. Кбайт — это 1024 байта, а не тысяча.
Смешали биты и байты в одной формуле. Переводи всё в биты сразу и держи в них до самого конца.
Использовали / вместо //. Дробные числа копят погрешность, а ответ в задании 7 всегда целый. Допустимо при вычислении в самом конце и ответ округляется "глазками".
Округлили вниз время передачи. Неполная секунда всё равно считается целой.
Подставили разрядность звука в логарифм. Она уже дана в битах, вычислять её не нужно.
Поверили программе, не проверив её. Прогони на разобранном примере из тетради — если совпало, можно доверять.

Регламент для всех типов задач

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

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

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

Проверь себя

Что напечатает эта программа?

import math

colors = 250                 # сколько цветов в палитре
depth = math.ceil(math.log2(colors))
print(depth)

В ответе запишите целое число.

Проверить ответ

Что делает проверка if bits % speed > 0: sec = sec + 1?

Проверить ответ

Расставьте шаги программы для задачи про изображение.

Проверить ответ

Печать