最短加法链问题
给定一个正整数和一个实数,如何用最少的乘法次数计算出xn。例如,可以用6次乘法逐步计算x23如下:x,x2,x3,x5,x10,x20,x23
可以证明计算最少需要6次乘法。计算的幂序列中各幂次1,2,3,5,10,20,23组成了一个关于整数23的加法链。在一般情况下,计算xn的幂序列中各幂次组成正整数的一个加法链
上述最优求幂问题相应于正整数的最短加法链问题,即求n的一个加法链使其长度达到最小。正整数的最短加法链长度记为l(n)。
2022-12-14 10:41:15
2.32MB
算法
1