Задний план

Большинство людей здесь должны быть знакомы с несколькими целочисленными базовыми системами: десятичной, двоичной, шестнадцатеричной, восьмеричной. Например, в шестнадцатеричной системе число abc.de ₁₆ будет представлять

a*16^2 + b*16^1 + c*16^0 + d*16^-1 + e*16^-2

Однако можно также использовать нецелые основания, такие как иррациональные числа. После того, как такая база использует золотое сечение ф = (1 + √5) / 2 ≈ 1.618 ... . Они определяются аналогично целочисленным основаниям. Таким образом, число abc.de _φ (где от a до e являются целыми числами) будет представлять

a*φ^2 + b*φ^1 + c*φ^0 + d*φ^-1 + e*φ^-2

Обратите внимание, что в принципе любая из цифр может быть отрицательной (хотя мы к этому не привыкли) - мы будем представлять отрицательную цифру с лидирующей ~. Для целей этого вопроса мы ограничимся цифрами от ~9до 9, поэтому мы можем однозначно написать число в виде одной строки (с тильдами между ними). Так

-2*φ^2 + 9*φ^1 + 0*φ^0 + -4*φ^-1 + 3*φ^-2

будет написано как ~290.~43. Мы называем такой номер финальным номером .

Двоичное число всегда может быть представлено в стандартной форме , что означает, что в представлении используются только цифры 1и 0, не содержащее 11нигде, и необязательный знак минус, указывающий, что все число является отрицательным. (Интересно, что каждое целое число имеет уникальное конечное представление в стандартной форме.)

Представления, которые не в стандартной форме, всегда можно преобразовать в стандартную форму, используя следующие наблюдения:

1. 011 _φ = 100 _φ (потому что φ ² = φ + 1)
2. 0200 _φ = 1001 _φ (потому что φ ² + 1 / φ = 2φ)
3. 0 ~ 10 _φ = ~ 101 _φ (потому что φ - 1 / φ = 1)

К тому же:

4. Если самая значимая цифра ~1(с остальной частью числа, являющейся стандартной формой), число является отрицательным, и мы можем преобразовать его в стандартную форму, поменяв местами все 1и ~1, добавив знак минус, и применив вышеупомянутые три правила снова, пока мы получить стандартную форму.

Вот пример такой нормализации (я использую дополнительные пробелы для положительных цифр, чтобы выровнять каждую позицию цифры): 1~3.2~1φ

      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)

Уступая .-0.0101φ

Для дальнейшего чтения в Википедии есть очень информативная статья на эту тему.

Соревнование

Следовательно, или иначе, напишите программу или функцию, которая, учитывая строку, представляющую двоичное число (как описано выше), выводит свою стандартную форму, без начальных или конечных нулей. Входные данные не обязательно содержат двоичную точку, но всегда будут содержать оставшуюся цифру (поэтому нет .123). Выходные данные всегда должны содержать двоичную точку и по крайней мере одну цифру слева от нее.

Вы можете получить ввод через STDIN, ARGV или аргумент функции и либо вернуть результат, либо распечатать его в STDOUT.

Вы можете использовать алгоритм, отличный от описанной выше процедуры, если он в принципе является правильным и точным для произвольных (допустимых) входных данных, то есть единственными ограничениями, которые могут потенциально нарушить вашу реализацию, должны быть технические ограничения, такие как размер встроенного типы данных или доступная оперативная память. Например, оценка входных данных как числа с плавающей запятой, а затем жадное выделение цифр недопустима, поскольку можно найти входные данные, для которых неточности с плавающей запятой приведут к неверным результатам.

Это код гольф, самый короткий ответ (в байтах) выигрывает.

Тестовые случаи

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

Javascript (ES6) - 446 418 422 420 байт

уменьшенная:

F=s=>{D=[];z='000000000';N=t=n=i=e=0;s=(z+s.replace(/^([^.]*)$/,'$1.')+z).replace(/~/g,'-').replace(/-?\d/g,s=>((D[n++]=s/1),0));for(;i<n-3;i=j){if(p=D[j=i+1]){if(!e&&p<0){D=D.map(k=>-k);N=~N;p=-p}e=1}d=D[i];x=D[i+2];m=D[i+3];if(p<0){d--;p++;x++;e=j=0}if(p>1){d++;m++;p-=2;e=j=0}if(!d&&p*x==1){d=p;e=j=p=x=0}D[i]=d;D[i+1]=p;D[i+2]=x;D[i+3]=m}return(N?'-':'')+s.replace(/0/g,()=>D[t++]).replace(/^(0(?!\.))+|0+$/g,'')}

Expanded:

F = s => {
    D = [];
    z = '000000000';
    N = t = n = i = e = 0;
    s = (z + s.replace( /^([^.]*)$/, '$1.' ) + z).replace( /~/g, '-' ).
        replace( /-?\d/g, s => ((D[n++]=s/1),0) );

    for( ; i < n-3; i = j ) {
        if( p = D[j = i+1] ) {
            if( !e && p < 0 ) {
                D = D.map( k=>-k );
                N = ~N;
                p = -p;
            }
            e = 1;
        }
        d = D[i];
        x = D[i+2];
        m = D[i+3];

        if( p < 0 ) {
            d--;
            p++;
            x++;
            e = j = 0;
        }
        if( p > 1 ) {
            d++;
            m++;
            p-=2;
            e = j = 0;
        }
        if( !d && p*x == 1 ) {
            d = p;
            e = j = p = x = 0;
        }

        D[i] = d;
        D[i+1] = p;
        D[i+2] = x;
        D[i+3] = m;
    }

    return (N ? '-' : '') + s.replace( /0/g, ()=>D[t++] ).replace( /^(0(?!\.))+|0+$/g, '' );
}

Код производит функцию, Fкоторая выполняет указанное преобразование.

Это сложная проблема для гольфа. Появляются многочисленные крайние случаи, которые препятствуют упрощению кода. В частности, работа с негативами - это боль, как с точки зрения синтаксического анализа, так и с точки зрения логической обработки.

Я должен отметить, что код обрабатывает только «разумный диапазон» входных данных. Чтобы расширить область функции без привязки, число нулей в zможет быть увеличено, а константа, ограничивающая while( c++ < 99 )цикл, может быть увеличена. Поддерживаемый диапазон уже исчерпан для поставленных тестовых случаев.

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

F('1')          1.
F('9')          10010.0101
F('1~3.2~1')    -0.0101
F('0.~1021')    -0.
F('105.~2')     1010.0101
F('~31~5.~1')   -100000.1001

Это -0.не красиво, но ответ по-прежнему правильный. Я могу исправить это при необходимости.

Haskell, 336 байт

z=[0,0]
g[a,b]|a*b<0=g[b,a+b]
g x=x<z
k![a,b,c,d]=[b,a+b,d-c+read k,c]
p('.':s)=1:0:2`drop`p s
p('~':k:s)=['-',k]!p s
p(k:s)=[k]!p s
p[]=1:0:z
[1,0]&y='.':z?y
[a,b]&y=[b,a+b]?y
x@[a,b]?y@[c,d]|x==z,y==z=""|g y='-':x?[-c,-d]|g[c-1,d]='0':x&[d,c+d]|g[c,d-1]='1':x&[d,c+d-1]|0<1=[b-a,a]?[d-c,c]
m[a,b,c,d]=[1,0]?[a*d+b*c-a*c,a*c+b*d]
f=m.p

Это жадный алгоритм, но с точным представлением [a,b]чисел a + bφ ( a , b ∈ ℤ), чтобы избежать ошибок с плавающей точкой. g[a,b]проверяет, является ли a + bφ <0. Пример использования:

*Main> f "9"
"10010.0101"
*Main> f "1~3.2~1"
"-0.0101"
*Main> f "0.~1021"
"0."