Целочисленные алгоритмы строятся на делении с остатком, и почти все они сводятся к циклу с остатками. Вторая половина главы — про структуры, различающиеся одним: с какого конца из них забирают элементы.
Что нужно знать
- Деление с остатком: a = b · q + r, где остаток неотрицателен и меньше делителя.
- Последнюю цифру числа даёт остаток от деления на 10, отбрасывает её целочисленное деление на 10.
- Алгоритм Евклида: НОД(a, b) = НОД(b, a mod b), пока второй аргумент не станет нулём.
- Число простое, если делителей нет до квадратного корня из него — проверять дальше незачем.
- Решето Эратосфена вычёркивает кратные и находит все простые числа до заданного предела.
- Стек работает по правилу «последним вошёл — первым вышел», очередь — «первым вошёл — первым вышел».
- Стек нужен для скобочных выражений и рекурсии, очередь — для обхода в ширину и буферов.
Где чаще всего ошибаются
- Проверяют простоту числа перебором до самого числа, а не до корня.
- Меняют местами аргументы в алгоритме Евклида и зацикливаются.
- Путают стек и очередь по порядку извлечения.
- Забывают, что при отрицательном делимом остаток в разных языках считается по-разному.
Проверить себя
По этой же главе есть проверочная работа из 11 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Информатика · 11 класс · Поляков, 2023 · Глава 6 · Целочисленные алгоритмы и структуры данных