Конвертировать между сбалансированными базами!

13

Сбалансированные базы:

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

С этого момента сбалансированные основания базы bмогут быть представлены как balb- так сбалансированное основание 4 = bal4.

В определении этого задания диапазон цифр в сбалансированной базе bот, -(k - 1)до b - k, где

k = ceil(b/2)

Примеры диапазона цифр в различных сбалансированных базах:

bal10:
  k = ceil(10/2) = 5
  range = -(5 - 1) to 10 - 5 = -4 to 5
        = -4, -3, -2, -1, 0, 1, 2, 3, 4, 5
bal5:
  k = ceil(5/2) = 3
  range = -(3 - 1) to 5 - 3 = -2 to 2
        = -2, -1, 0, 1, 2

Представления чисел в сбалансированных базах в основном такие же, как нормальные базы. Например, представление числа 27(основание 10) в bal4(сбалансированное основание 4) 2 -1 -1, потому что

  2 -1 -1 (bal4)
= 2 * 4^2 + -1 * 4 + -1 * 1
= 32 + (-4) + (-1)
= 27 (base 10)

Задача:

Ваша задача, учитывая три входа:

  • число для преобразования ( n)
    • этот ввод может быть гибким, см. «Гибкость ввода / вывода»
  • база, которая nв данный момент находится в ( b)
  • база, которая nдолжна быть преобразована в ( c)

Где 2 < b, c < 1,000.

Вернуть число в сбалансированном базовом cпредставлении n. Выход также может быть гибким.

Программа / функция должна определять длину самого nвхода.

Гибкость ввода / вывода:

Ваш вход nи выход может быть представлен следующими способами:

  • определение массива на вашем языке
  • строка с любым символом в качестве разделителя (например, пробелы, запятые)

Примеры:

Обратите внимание, что они используют массив Python как nи вывод. Вы можете использовать любой язык, который соответствует вашему языку, если он соответствует определению «Гибкость ввода / вывода».

[2, -1, -1] 4 7 = [1, -3, -1]
[1, 2, 3, 4] 9 5 = [1, 2, 2, -1, 2]
[10, -9, 10] 20 5 = [1, 1, 1, -2, 1, 0]

Это код-гольф , поэтому выигрывает самый короткий код в байтах!

code-golf math base-conversion clismique
источник
В вашем первом ответе 4 не является законной цифрой bal7; Я считаю, что ответ должен быть [1, -3, -1]. И я получаю разные ответы для второго теста ([1,2,2, -1,2]) и третьего теста ([1,1,0, -2,1,0]), а также ...?
Грег Мартин
@GregMartin Ах, блин, я подсчитал их вручную, поэтому возникли некоторые проблемы. Спасибо, что заметили! Можете ли вы еще раз проверить свои решения, на всякий случай?
clismique
@GregMartin @ Qwerp-Derp Третий контрольный пример[1,1,1,-2,1,0]
ngenisis

Ответы:

2

Mathematica, 85 байт

#~FromDigits~#2~IntegerDigits~#3//.{p___,a_:0,b_,q___}/;b>⌊#3/2⌋:>{p,a+1,b-#3,q}&

объяснение

#~FromDigits~#2

Преобразовать #1(подразумевается 1 - ввод 1, список цифр) в целочисленную базу #2(ввод 2).

... ~IntegerDigits~#3

Преобразуйте полученное целое число в основание #3(вход 3), создав список цифр.

... //.{p___,a_:0,b_,q___}/;b>⌊#3/2⌋:>{p,a+1,b-#3,q}

Повторно заменить список цифр; если цифра больше, чем пол ( #3/ 2), вычтите #3ее и добавьте 1к цифре слева. Если слева ничего нет, вставьте 0и добавьте 1.

Юнг Хван Мин
источник
Обычно рекомендуется немного рассказать о своем решении и объяснить его людям, которые могут не знать Mathematica.
ATaco
@ATaco Добавлено объяснение!
JungHwan Мин
Я немного озадачен этим. Я никогда не видел дополнительных шаблонов, используемых где-либо, кроме определений функций. Вам не нужно внешнее, {...}так как есть только одно правило замены.
ngenisis
1
@JungHwanMin Правда, я думаю, что меня смущает то, как это влияет на матч p___. Находит ли это самое короткое, p___сопровождаемое либо a_,b_или b_, либо проверяет весь шаблон, требующий каждого из дополнительных шаблонов, и затем постепенно отбрасывает дополнительные шаблоны, пока не найдет совпадение (или какой-либо третий вариант)?
ngenisis
1
@ngenisis Я считаю, что я ошибся в предыдущем комментарии (удалено), наблюдая за результатом FixedPointList[k=#3;#/.{p___,a_:0,b_,q___}/;b>⌊k/2⌋:>{p,a+1,b-k,q}&, #~FromDigits~#2~IntegerDigits~#3]&. {p___,a_,b_,q___}сначала сопоставляется (для всех возможных p), а затем {p___,b_,q___}сопоставляется. Вторая замена применяется только тогда, когда она bнаходится в начале, потому что если bв середине есть a , удовлетворяющее условию, оно {p___,a_,b_,q___}будет соответствовать ей.
JungHwan Мин
1

Perl 6 , 121 байт

->\n,\b,\c{sub f{sum [R,](@^n)Z*($^b X**0..*)}
first {f(b,n)==f c,$_},map {[$_-($_>floor c/2)*c for .base(c).comb]},0..*}

Медленное перебор.

Как это устроено:

  • map {[ .base(c).comb]}, 0..*- Создать ленивую бесконечную последовательность натуральных чисел в базе c, где каждое число представлено в виде массива цифр.
  • $_ - ($_ > floor c/2) * c- Преобразуйте его, вычитая cиз каждой цифры больше пола (с / 2).
  • first { f(b, n) == f(c, $_) }, ...- Получить первый массив этой последовательности, который при интерпретации как базовое cчисло равен входному массиву, nинтерпретированному как базовое bчисло.
  • sub f { sum [R,](@^n) Z* ($^b X** 0..*) }- Вспомогательная функция, которая превращает массив @^nв число в базе $^b, взяв сумму произведенных произведений, сжав реверсированный массив с последовательностью степеней базы.
SMLS
источник
1

JavaScript (ES6), 89 байт

(n,b,c,g=(n,d=n%c,e=d+d<c)=>[...(n=n/c+!e|0)?g(n):[],e?d:d-c])=>g(n.reduce((r,d)=>r*b+d))

100 байтов работает для отрицательных значений n.

(n,b,c,g=(n,d=(n%c+c)%c)=>[...(n-=d,n/=c,d+d<c||(d-=c,++n),n?g(n):[]),d])=>g(n.reduce((r,d)=>r*b+d))
Нил
источник
0

Mathematica, 118 114 байт

IntegerDigits[#3~FromDigits~#2,k=⌊#/2⌋;#]//.{{a_,x___}/;a>k:>{1,a-#,x},{x___,a_,b_,y___}/;b>k:>{x,a+1,b-#,y}}&

⌊и ⌋являются 3-байтовыми символами U+230Aи U+230B, соответственно. Преобразует #3в базу 10из базы #2, затем преобразует в базу #(поэтому порядок аргументов обратный из примеров). Если какая-либо цифра превышает максимально допустимую цифру k=⌊#/2⌋, уменьшите эту цифру #и увеличьте следующую цифру (возможно, потребуется добавить перед ней 1). Продолжайте делать это, пока все цифры не станут меньше k.

ngenisis
источник