Преобразование целого числа

[Mac Buster]

По-моему в нашем форуме ещё не затрагивалась тема способов преобразования целого числа из десятичной системы счисления в уравновешенную троичную. Позволю себе привести выдержку из брошюры С.В.Фомина "Системы счисления" вышедшей в серии "Популярные лекции по математике":

Можно, однако, записать каждое число в троичной системе и несколько иначе, а именно так, чтобы в его записи участвовали цифры 0, 1 и -1 (вместо 0,1 и 2). Для получения такой записи поступим следующим образом. Переведем числа А из десятичной системы в троичную, пользуясь схемой последовательных делений на три. Но только каждый раз, когда у нас при делении на три будет получаться 2, мы будем частное увеличивать на единицу, а в остатке при этом писать -1.

К этому следует добавить, что в том случае, если мы производили преобразование отрицательного числа, то по окончании перевода потребуется инвертировать разряды полученного троичного числа (последовательно заменить все 1 на -1 и обратно).

Кроме такого способа есть несколько других, например, один (крайне странный) приводится во втором томе "Искусства программирования" Д.Кнута. В публикациях Николая Петровича Брусенцова и Хосе Рамиля Альвареса описаны способы подобных преобразований не только для десятичной, но так же для двоичной и прочих систем.

[Shaos]

Вот мои собственные алгоритмы, придуманные из головы (никуда не глядя) для преобразования туда и обратно:

Code: Select all

 public static String toTernary(int num)
 {
    int n,m,k;
    String s = null;
    k = 387420489;
    for(int i=0;i<=18;i++)
    {
      n = num/k;
      num -= n*k;
      m = k/2;
      if(num>+m){n++;num-=k;}
      if(num<-m){n--;num+=k;}
      if(n!=0 && s==null) s="";
      if(n==-1) s+="N";
      if(n==0 && s!=null) s+="O";
      if(n==1) s+="P";
      k /= 3;
    } 
    return s;
 }
 
 public static int fromTernary(String s)
 {
    int n = 0;
    int k = 1;
    for(int i=s.length()-1;i>=0;i--)
    {
      char c = s.charAt(i);
      if(c!='N'&&c!='O'&&c!='P') return 0;
      if(c=='N') n-=k;
      if(c=='P') n+=k;
      k *= 3;
    }
    return n;
 }

Написано на джаве, могу переписать на русский, если надо

[sva]

можно проще и быстрее
сначала преобразовать число к 3му с основанием 3 (значаения разрядов 0,1,2) а затем преобразовать к 3му симметричному коду

преобразование к 3му с основанием 3 производится итеративным делением на 3 с выделением остатка в качестве значения следующего разряда (без нализа знака)

преобразование 3го с основанием 3 к 3му симметричному коду производится прибавлением к исходному числу половины максимально представимого данным кол-вом разрядов за вычетом 1 и последующим поразрядным вычитанием 1.

т.е. для трайта (6 тритов) примерно так

Code: Select all

int* dec2tri(int dec)
//dec - исходное число (максимально представимое -364 .. +364)
{
  char tri[6];  
  char tmp_tri[6];
  int tmp_dec;
  char sign;

  sign = dec/abs(dec);
  tmp_dec = abs(dec) +364;

  for(i=0;i<6;i++)
  {
    tmp_tri[i] = tmp_dec % 3;
    tmp_dec = tmp_dec /3;
  }
  for(i=0;i<6;i++) 
    if(sign>0)
      tri[i] = (tmp[i] -1);
    else
      tri[i] = (1-tmp[i]);

// или что коректнее  tri[i] = sign * (tmp[i] -1);

  return tri;
}

обратное преобразование делается в обратном порядке.
и этот вариант проще реализуется в железе.
тут используется N+1 операций деления (при использовании еще одной переменной можно для вычисления остатка от деления на 3 использовать не деление, а вычитание)

[Mac Buster]

Спасибо! Если я не ошибаюсь именно этот способ предложен в книге Д.Кнута.