时间戳

首页 > 解决方案 > 求幂 - 基于三的位置系统

algorithm - 求幂 - 基于三的位置系统

问题描述

我在十进制系统中有一个自然数 x，在三进制系统中有一个自然数 n。如何使用最小乘法数计算 x^n 的值？

我知道二进制系统的算法，我一直在寻找一个类比，但我没有找到。

标签： algorithmpseudocode

解决方案

也许你需要这样的东西：

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)

工作德尔福代码

 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

推荐阅读