Codegolf — Стандартизация Номера Phinary

  • Автор темы Vova_stronsky
  • Обновлено
  • 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\$ и с необязательным знаком минус, указывающим, что все число отрицательно. (Интересно, что каждое целое число имеет уникальное конечное представление в стандартной форме.)

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

  1. \$011_φ = 100_φ\$ (потому что \$φ^2 = φ + 1\$)
  2. \$0200_φ = 1001_φ\$ (поскольку \$φ^2 + \frac1φ = 2φ\$)
  3. \$0\text{~}10_φ = \text{~}101_φ\$ (поскольку \$φ - \frac1φ = 1\$)

Кроме того:

  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)

#код-гольф #число #арифметика #теория чисел #преобразование оснований

Vova_stronsky


Рег
22 Aug, 2006

Тем
75

Постов
192

Баллов
617
  • 26, Oct 2024
  • #2

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

Минимизировано:

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

Расширено:

g[a,b]

Код создает функцию [a,b] that performs the specified conversion.

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

Должен отметить, что код обрабатывает только «разумный диапазон» входных данных. Чтобы неограниченно расширить область определения функции, количество нулей в 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 can be increased, and the constant bounding the -0. шлейф можно увеличить. Поддерживаемый в настоящее время диапазон уже является излишним для предоставленных тестовых примеров.

Примеры результатов

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

while( c++ < 99 ) isn't pretty, but the answer is still correct. I can fix it if necessary.

 

Наталья Мананникова


Рег
07 Dec, 2020

Тем
83

Постов
186

Баллов
621
  • 26, Oct 2024
  • #3

Хаскелл, 336 байт

z

Это жадный алгоритм, но с точным представлением F of numbers а + (а, б ∈ ℤ), чтобы избежать ошибок с плавающей запятой. 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, '' ); } tests whether а + < 0. Пример использования:

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,'')}
 

Yrubakdn


Рег
31 Aug, 2011

Тем
61

Постов
179

Баллов
494
Тем
403,760
Комментарии
400,028
Опыт
2,418,908

Интересно