logo标签列表

如何从不平衡三进制转换为平衡三进制？

algorithmmathternary
6
我的目标是将十进制数转换为平衡三进制数。将十进制转换为不平衡三进制只需要除以3并跟踪余数。一旦我有了该数字的不平衡三进制表示，我似乎无法弄清如何“平衡”它。
例如：十进制中的15在不平衡三进制中为120，在平衡三进制中为+--0。我该如何从120转换为+--0？我不知道如何处理不平衡三进制表示中的2。
谢谢！
1
维基百科有答案。 - user3386109
谢谢 user3386109 :) - corecase
是的，没错。您可能需要经过几次迭代，将2更改为1T。 （我假设您最后一个T是要成为1T）。 - user3386109
在维基百科的例子中，他们有点跳过了中间迭代。它应该是 0212 = 0010 + 1T00 + 001T = 1T2T = 1T0T + 01T0 = 10TT。 - user3386109
随时乐意帮助 :) - user3386109
显示剩余4条评论
5个回答
6
请注意，三进制中的2在平衡三进制中表示为+-，或者在十进制中表示为2=3-1。因此，如果你开始使用一个由0、1和2填充的数组，只需将每个2替换为-1，并向其左侧的数字加1。（如果数字以2开头，请确保在数字开头有一个额外的0。）根据替换的方式，你可能还需要将3替换为0，并像往常一样向左添加1。然后重复这个过程，直到没有更多的2（或3）。
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;
}

运行程序可以在这里找到。
0
0

偏置三进制与平衡三进制

Douglas W. Jones的《三进制宣言》是关于（平衡）三进制表示的信息的绝佳来源。作者指出：

平衡三进制编码与偏置编码完全等价。

偏置编码是一种使用偏移量b将有符号数编码为（有界）无符号数的方法。要读取偏置数，按照通常的方式读取，然后减去b以获取所代表的值。

Douglas W. Jones描述了三进制偏置和平衡数字之间的联系，并给出了两个三进制数字（= 三位数）的示例。

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      --

[...]
the natural bias b for an n-trit ternary number is all ones:
b = ⌊3n / 2⌋ = (3n-1) / 2
[...]
To convert biased numbers to balanced numbers, subtract 1 from each digit, so 2 becomes +1 (represented as +), 1 becomes 0 (represented as 0), and 0 becomes –1 (represented as -).
[...]
This is merely a change of the symbols associated with the digits, a matter of how the digits are printed on the page, not a matter of how the digits are represented inside some mechanism. The difference between biased and balanced representations can be considered to be entirely cosmetic

将整数转换为平衡三进制

将整数i转换为平衡三进制的步骤如下：

  • 计算n，即i的平衡三进制表示中的数字个数。
    通过解决 |i| ≤ (3n-1) / 2，我们可以得到 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"
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"

只是快速而粗略地编写，没有检查/编码所有的“特殊情况”。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接