Как конфертировать из неуравновешенного в сбалансированное троичное?

Моя цель - преобразовать десятичное число в сбалансированное троичное. Преобразование из десятичного в несбалансированное троичное просто требует деления на 3 и отслеживания остатков. Как только я получу несбалансированное троичное представление числа, я не могу понять, как его "сбалансировать".

Например: 15 в десятичном виде это 120 в несбалансированной троичной и +- 0 в сбалансированной троичной. Как мне перейти от 120 до +-0? Я не могу понять, как бороться с двумя в несбалансированном троичном представлении.

Спасибо!

Источник

2 ответа

Решение

Обратите внимание, что 2 в троичной системе - это +- в сбалансированной троичной форме или в десятичной системе счисления 2 = 3 - 1. Так что, если вы начинаете с массива, заполненного 0, 1 и 2, просто замените каждые 2 на -1 и добавьте 1 к номер слева. (Убедитесь, что у вас есть дополнительный 0 в начале числа, по крайней мере, если он начинается с 2.) В зависимости от того, как вы выполняете замену, вам также может понадобиться заменить 3 на 0, добавив 1 как обычно слева. Затем повторяйте процесс до тех пор, пока не останется 2 с (или 3 с).

Источник

Один из способов увидеть это, если вы получаете остаток 2 с оставшимся частным x, это эквивалентно получению остатка -1 с оставшимся частным x+1,

Преобразование тогда подобно простому преобразованию в троичное основание с одной дополнительной проверкой.

String output="";
while (n>0) {
   rem = n%3;
   n = n/3;
   if (rem == 2) {
       rem = -1;
       n++;
   }
   output = (rem==0?'0':(rem==1)?'+':'-') + output;
}

Работающую программу можно найти здесь.

Источник

Смещенная троичная система против сбалансированной тройной

"Тернарный манифест " Дугласа У. Джонса - отличный источник информации по теме (сбалансированного) троичного представления. Автор отмечает, что

сбалансированное троичное кодирование в точности эквивалентно смещенному кодированию

Смещенное кодирование - это способ кодирования чисел со знаком в (ограниченных) числах без знака с использованием смещения b. Чтобы прочитать смещенное число, прочтите его как обычно, затем вычтите b, чтобы получить представленное значение.

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

Decimal  Biased Balanced
   4       22      ++
   3       21      +0
   2       20      +-
   1       12      0+
   0       11      00
  -1       10      0-
  -2       02      -+
  -3       01      -0
  -4       00      --

[...]
естественное смещение b для n-тройного троичного числа - все единицы:
b = ⌊3n / 2⌋ = (3n-1) / 2
[...]
Чтобы преобразовать смещенные числа в сбалансированные числа, вычтите 1 из каждой цифры, так что 2 станет+1 (представлен как +), 1 становится 0 (представлен как 0), а 0 становится –1 (представлен как -).
[...]
Это просто изменение символов, связанных с цифрами, вопрос того, как цифры напечатаны на странице, а не вопрос того, как цифры представлены внутри некоторого механизма. Разницу между предвзятым и сбалансированным представлениями можно считать чисто косметической.

Преобразование целых чисел в сбалансированный троичный

Чтобы преобразовать целое число i в сбалансированное троичное

  • Вычислите n, количество цифр в сбалансированном троичном представлении i.
    Решая | i | ≤ (3n-1) / 2 для n, мы знаем, что n = ⌈log3(2 | x | +1) ⌉.
  • Вычислите смещение b = (3n-1) / 2.
  • Затем преобразуйте i+b в троичную строку с n цифрами (ведущие 0важны!),
  • и замените символы 012 по -0+.

Пример реализации в Java jshell:

import static java.lang.Math.*;

String balTer(int i) {
  // n=…+1 and ….substring(1) ensure leading zeroes 
  int n = max(1, (int) ceil(log(2 * abs(i) + 1) / log(3))) + 1;
  int b = ((int) pow(3, n) - 1) / 2;
  return Integer.toString(i + b, 3).substring(1)
      .replace('0', '-').replace('1', '0').replace('2', '+');
}

balTer(15) // returns "+--0"
Источник

Поскольку мне не хватало этого в Интернете, вот моя собственная реализация в Pari/GP -

{balanced_ternary(x,maxdigits=20,chars=["y","0","1"])=my(res,st,dez,dig);
      dez=floor(log(abs(2*x))/log(3)); 
      res=x/3^dez;
      st=""; 
      for(k=0,maxdigits,
               if(k==dez+1,st=Str(st,"."));
               dig = if(res>1/2 
                       ,res--;chars[2+1]
                       ,if(res<-1/2
                              ,res++;chars[2-1]
                              ,chars[2+0]
                 )); 
               st=Str(st,dig);res*=3
           );
       return(st);}

потом

balancedternary (1)    \\ %1002 = "1.00000000000000000000"
balancedternary (-1)   \\ %1003 = "y.00000000000000000000"
balancedternary (1.2)  \\ %1004 = "1.1yy11yy11yy11yy11yy1"
balancedternary (-1.2) \\ %1005 = "y.y11yy11yy11yy11yy11y"

balancedternary (27-3) \\ %1006 = "10y0.00000000000000000"
balancedternary (400)  \\ %1007 = "1yy0y11.00000000000000"
balancedternary (sqrt(3))   \\ %1008 = "1y.y1yy10y0000yy1100y0"
balancedternary (sqrt(3)/3) \\ %1009 = "1.yy1yy10y0000yy1100y0"

Просто q&d, не все "особые случаи" проверены / закодированы.

Источник

Я знаю, что этот вопрос касается преобразования из обычного троичного, но FWIW, вы также можете достичь поставленной цели, перейдя прямо от десятичного к сбалансированному тройному, например, с помощью программ на

Источник
Другие вопросы по тегам