Задачи на остатки и периодичность

Остаток и периодичность

Многие задачи информатики связаны с повторяющимися событиями: дни недели, цвета светофора, позиции по кругу, музыкальные ноты. Ключ к ним — операция взятия остатка от деления, которая показывает положение внутри цикла.

Если событие повторяется через каждые k шагов, то номер шага по модулю k определяет текущую фазу. Это превращает длинный счёт в короткий: вместо тысячи шагов достаточно знать остаток.

Основная идея

Пусть дни недели пронумерованы от 0 (понедельник) до 6 (воскресенье). Тогда через n дней после понедельника будет день с номером mod(n, 7). Остаток как бы «возвращает» нас в начало цикла, отбрасывая полные недели.

нач цел n, den ввод n den := mod(n, 7) вывод den | 0 - понедельник, 6 - воскресенье кон

Примеры периодов

Задача	Период	Выражение
день недели	7	mod(n, 7)
чётность шага	2	mod(n, 2)
позиция по кругу из 5	5	mod(n, 5)
последняя цифра числа	10	mod(n, 10)

Движение по кругу

Если по кругу расставлены позиции от 0 до k-1 и мы делаем n шагов из позиции start, конечная позиция равна mod(start + n, k). Так считают положение фишки в настольной игре или номер выигравшего в считалочке. Если шаги делаются назад, остаток помогает не уйти в отрицательные номера: к результату прибавляют период.

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

Где встречается

Остатки используют в задачах о календарях, в шифрах со сдвигом (например, шифр Цезаря), при распределении элементов по группам и в проверке делимости. Это одна из самых частых идей в заданиях ОГЭ по информатике.

Ещё остаток помогает работать с последней цифрой числа: mod(n, 10) даёт младшую цифру, а деление нацело на 10 убирает её. Сочетая эти две операции в цикле, перебирают все цифры числа по очереди — от младшей к старшей.

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

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

Кратко о главном

• Остаток от деления показывает фазу внутри периода.
• Период k задаёт выражение mod(n, k).
• Деление нацело даёт число полных кругов.
• Идея применяется в календарях, шифрах и играх по кругу.