Перевод в факториальную систему
Факториальная система счисления записывает число как сумму произведений цифр на факториальные веса: \(1!, 2!, 3!, 4!, \ldots\). Чтобы перевести десятичное число в эту систему, последовательно делят его на \(2,3,4,\ldots\), записывают остатки и читают их в обратном порядке.
Что такое факториальная жазба
В факториальной системе счисления разряды имеют не обычные степени одного основания, а факториальные веса. Разряд справа налево соответствует весам \(1!, 2!, 3!, 4!, \ldots\). Напомним, что \(0!=1\) и \(1!=1\), поэтому разряд с весом \(0!\) обычно не используют отдельно: его цифра всегда равна нулю.
Факториальная жазба числа \(N\) — это представление вида \(N=a_k\cdot k!+a_{k-1}\cdot (k-1)!+\ldots+a_2\cdot 2!+a_1\cdot 1!\), где цифра \(a_i\) удовлетворяет ограничению \(0\le a_i\le i\).
Ограничение на цифры связано с весами разрядов. В разряде с весом \(i!\) нельзя использовать цифру больше \(i\): например, для веса \(4!\) допустимы цифры от \(0\) до \(4\), а для веса \(2!\) — только \(0,1,2\). Подробнее набор допустимых символов рассматривается на странице алфавит факториальной системы счисления.
Для перевода десятичного числа в факториальную систему последовательно делите число на \(2,3,4,\ldots\). Каждый остаток становится цифрой соответствующего факториального разряда. Последний ненулевой остаток записывается слева, а первый — справа.
Почему работают последовательные деления
Сначала представим число в виде \(N=2q_1+a_1\), где \(a_1\) — остаток от деления на \(2\). Поскольку остаток меньше делителя, \(a_1\) может быть только \(0\) немесе \(1\) — это допустимая цифра при весе \(1!\).
Затем раскладываем частное: \(q_1=3q_2+a_2\). Получаем \(N=2(3q_2+a_2)+a_1\). После нескольких қадам множители образуют произведения \(2\cdot3\cdot4\cdots i=i!\), а остатки становятся цифрами факториальной жазбалар.
- Положите текущее число равным исходному числу \(N\).
- Разделите текущее число на \(2\) и запишите остаток.
- Частное разделите на \(3\), затем новое частное — на \(4\) и так далее.
- Остановитесь после получения частного \(0\).
- Прочитайте полученные остатки справа налево.
Какую цифру можно получить при делении на \(5\) в алгоритме перевода в факториальную систему?
Разбор перевода по шагам
Переведём число \(463_{10}\) в факториальную систему. Делители начинаются с \(2\). В таблице частное используется на следующем шаге, а остатки нужно будет прочитать в обратном порядке.
| Шаг | Деление | Частное | Остаток |
|---|---|---|---|
| 1 | \(463:2\) | 231 | 1 |
| 2 | \(231:3\) | 77 | 0 |
| 3 | \(77:4\) | 19 | 1 |
| 4 | \(19:5\) | 3 | 4 |
| 5 | \(3:6\) | 0 | 3 |
Остатки получены в порядке \(1,0,1,4,3\). Разворачиваем последовательность: \(3,4,1,0,1\). Поэтому \(463_{10}=34101_{!}\), где нижний индекс \(!\) обозначает факториальную систему.
Проверка показывает, что жазба верна: \(3\cdot120+4\cdot24+1\cdot6+0\cdot2+1=360+96+6+0+1=463\). Максимальная цифра здесь равна \(4\) и стоит в разряде \(4!\), а цифра в разряде \(5!\) равна \(3\), что также удовлетворяет ограничениям.
Деления выполняются слева направо: сначала на \(2\), затем на \(3\), \(4\) и так далее. Но найденные остатки идут от младшего разряда к старшему, поэтому в ответе их обязательно записывают справа налево.
Проверка и выбор старшего разряда
Перед началом можно определить, какой самый большой факториальный вес не превосходит число. Для \(463\) это \(5!=120\), а \(6!=720>463\), значит, жазба начинается с разряда \(5!\). Однако при последовательных делениях отдельно искать этот разряд необязательно: алгоритм сам остановится после деления на $6.
Проверка выполняется умножением цифр на их веса. Нужно помнить, что веса не являются степенями основания: нельзя проверять запись как обычное число с основанием \(10\) немесе \(2\). Вспомогательная тема веса факториальных разрядов помогает быстро составить ряд весов.
- \(1!=1\)
- \(2!=2\)
- \(3!=6\)
- \(4!=24\)
- \(5!=120\)
- \(6!=720\)
1. Читать остатки в том же порядке, в каком они получены. Нужно разворачивать их. 2. Делить каждый раз на одно и то же число. Делители меняются: \(2,3,4,\ldots\). 3. Разрешать цифру \(5\) в разряде \(4!\). В этом разряде максимум равен \(4\). 4. Забывать нулевые остатки: они являются значимыми цифрами внутри записи. 5. Проверять результат степенями основания вместо факториальных весов.
Связь с другими способами жазбалар
Перевод в факториальную систему — обратная операция к переводу из факториальной системы. В отличие от перевода в фибоначчиеву систему, здесь цифры ограничиваются номером разряда, а не условием отсутствия соседних единиц. Общие приёмы проверки разрядных представлений разобраны на странице разбор тапсырма на системы счисления.
В экзаменационной задаче могут попросить найти цифру, количество разрядов или само представление. Если требуется только отдельная цифра, не обязательно выписывать всю запись: достаточно выполнить деления до нужного шага и определить соответствующий остаток. Если требуется старшая цифра, продолжайте делить до нулевого частного.
Номер делителя на шаге на единицу больше нөмір текущего младшего факториального разряда: деление на \(2\) даёт цифру при \(1!\), деление на \(3\) — цифру при \(2!\), деление на \(4\) — цифру при \(3!\).
Жылдам тест
Проверьте понимание алгоритма
Кратко
- Факториальная жазба использует веса \(1!,2!,3!,\ldots\).
- В разряде с весом \(i!\) допустимы цифры от \(0\) до \(i\).
- Для перевода десятичного числа выполняют деления на \(2,3,4,\ldots\).
- Остатки записывают в обратном порядке: первый остаток становится последней цифрой.
- Результат проверяют суммой произведений цифр на соответствующие факториальные веса.