Экспонирование - позиционная система на основе трех - PullRequest
Новая
       4

Экспонирование - позиционная система на основе трех

0 голосов
/ 29 июня 2018

У меня есть натуральное число x в десятичной системе и натуральное число n в троичной системе счисления. Как рассчитать значение x ^ n, используя минимальное количество умножений?

Я знаю алгоритм для бинарной системы и искал аналогию, но не нашел ее.

1 Ответ

0 голосов
/ 29 июня 2018

Возможно, вам нужно что-то вроде этого: 

function expbycubing(x, n): 

   //treat n = 0..2 cases here

   switch n % 3:
       0: return expbycubing(x * x * x, n shrt 1)    
       ///// note shift in ternary system  (tri)201 => (tri)020  
       1: return x * expbycubing(x * x * x, n shrt 1)
       2: return x * x * expbycubing(x * x * x, n shrt 1)

Рабочий код Delphi 

 function expbycubing(x, n: Integer): int64;
  begin
    Memo1.Lines.Add(Format('x: %d  n: %d', [x, n]));
    if n = 0 then Exit(1);
    if n = 1 then Exit(x);
    if n = 2 then Exit(x * x);
    case n mod 3 of
      0: Result := expbycubing(x * x * x, n div 3);
      1: Result := x * expbycubing(x * x * x, n div 3);
      2: Result := x * x * expbycubing(x * x * x, n div 3);
    end;
  end;

var
  i: Integer;
begin
  for i := 12 to 12 do
    Memo1.Lines.Add(Format('%d: %d', [i, expbycubing(2, i)]));
end;

журнал: 

x: 2  n: 12
x: 8  n: 4
x: 512  n: 1
12: 4096
...