- 23, Oct 2024
- #1
Фон
Большинство людей здесь должны быть знакомы с несколькими базовыми системами целых чисел: десятичной, двоичной, шестнадцатеричной, восьмеричной. Например. в шестнадцатеричной системе число \$abc.de_{16}\$ будет обозначать
$$a\times16^2 + b\times16^1 + c\times16^0 + d\times16^{-1} + e\times16^{-2}$$
Однако можно также использовать нецелые основания, например иррациональные числа. Однажды такая база использует золотое сечение \$φ = \frac{1+√5}2 ≈ 1,618...\$. Они определяются аналогично целочисленным основаниям. Таким образом, число \$abc.de_φ\$ (где от \$a\$ до \$e\$ — целые цифры) будет представлять
$$a\timesφ^2 + b\timesφ^1 + c\timesφ^0 + d\timesφ^{-1} + e\timesφ^{-2}$$
Обратите внимание, что в принципе любая цифра может быть отрицательной (хотя мы к этому не привыкли) — мы будем представлять отрицательную цифру с ведущим \$\text{~}\$. Для целей этого вопроса мы ограничимся цифрами от \$\text{~}9\$ до \$9\$, поэтому мы можем однозначно записать число в виде одной строки (с тильдами между ними). Так
$$-2\timesφ^2 + 9\timesφ^1 + 0\timesφ^0 + -4\timesφ^{-1} + 3\timesφ^{-2}$$
будет записано как \$\text{~}290.\text{~}43\$. Мы называем такое число финарный номер.
Финарное число всегда можно представить в виде стандартная форма, что означает, что в представлении используются только цифры \$1\$ и \$0\$, нигде не содержится \$11\$ и с необязательным знаком минус, указывающим, что все число отрицательно. (Интересно, что каждое целое число имеет уникальное конечное представление в стандартной форме.)
Представления, которые не имеют стандартной формы, всегда можно преобразовать в стандартную форму, используя следующие наблюдения:
- \$011_φ = 100_φ\$ (потому что \$φ^2 = φ + 1\$)
- \$0200_φ = 1001_φ\$ (поскольку \$φ^2 + \frac1φ = 2φ\$)
- \$0\text{~}10_φ = \text{~}101_φ\$ (поскольку \$φ - \frac1φ = 1\$)
Кроме того:
- Если самая значащая цифра равна \$\text{~}1\$ (остальная часть числа имеет стандартную форму), число отрицательное, и мы можем преобразовать его в стандартную форму, поменяв местами все \$1\$ и \ $\text{~}1\$, добавляя знак минус и снова применяя три вышеуказанных правила, пока не получим стандартную форму.
Вот пример такой нормализации \$1\text{~}3.2\text{~}1_φ\$ (я использую дополнительные пробелы для положительных цифр, чтобы выровнять положение каждой цифры):
Input Output 1 1. 9 10010.0101 1.618 10000.0000101 1~3.2~1 -0.0101 0.~1021 0. (or -0.) 105.~2 1010.0101 ~31~5.~1 -100000.1001
Доходность \$-0,0101_φ\$.
Для дальнейшего чтения в Википедии есть очень информативная статья по теме.
Вызов
Следовательно, или иначе, напишите программу или функцию, которая, учитывая строку, представляющую финарное число (как описано выше), выводит ее стандартную форму без начальных или конечных нулей. Входные данные не обязательно содержат финарную точку, но всегда будут содержать цифру слева от нее (поэтому нет \$.123\$). Выходные данные всегда должны включать финарную точку и хотя бы одну цифру слева от нее.
Вы можете получить ввод через STDIN, ARGV или аргумент функции и либо вернуть результат, либо распечатать его в STDOUT.
Вы можете использовать алгоритм, отличный от описанной выше процедуры, если он в принципе корректен и точен для произвольных (действительных) входных данных, то есть единственными ограничениями, которые потенциально могут нарушить вашу реализацию, должны быть технические ограничения, такие как размер встроенных типы данных или доступную оперативную память. Например, оценка входных данных как числа с плавающей запятой, а затем жадный выбор цифр не допускается, поскольку можно найти входные данные, для которых неточности с плавающей запятой приведут к неверным результатам.
Это кодовый гольф, выигрывает самый короткий ответ (в байтах).
Тестовые случаи
1~3. 2~1φ Rule:
= 0~2. 3~1φ (3)
= ~1~1. 4~1φ (3)
= ~1 0 0. 4~1φ (3)
= ~1 0 0. 3 0 1φ (3)
= ~1 0 1. 1 0 2φ (2)
= ~1 1 0. 0 0 2φ (1)
= ~1 1 0. 0 1 0 0 1φ (2)
= - 1~1 0. 0~1 0 0~1φ (4)
= - 0 0 1. 0~1 0 0~1φ (3)
= - 0 0 1.~1 0 1 0~1φ (3)
= - 0 0 0. 0 1 1 0~1φ (3)
= - 0 0 0. 0 1 1~1 0 1φ (3)
= - 0 0 0. 0 1 0 0 1 1φ (3)
= - 0 0 0. 0 1 0 1 0 0φ (1)
#код-гольф #число #арифметика #теория чисел #преобразование оснований