论坛 › 算法交流 › 关于a^n的计算

wayne 发表于 2010-5-25 11:38:16

wikipedia说此题目前没有有效的方法：
http://en.wikipedia.org/wiki/Addition_chain


给一个图：



更详细的信息：
http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html

northwolves 发表于 2010-5-25 13:11:51

Found in http://wwwhomes.uni-bielefeld.de/achim/add_fun1.html

For n=375494703 holds: 34 = l(2n) < l(n) = 35.

medie2005 发表于 2010-5-25 13:33:07

22# northwolves
那是star chain，和这里讨论的是有区别的。
我们这里讨论的是shortest chain。
从网页信息里，可以看出，他自己也不能确定 l(375494703)=35。

无心人 发表于 2010-5-27 16:32:23

定义链的度信息为节点到数字1的距离
假设有两个数字x >y在链的相同分支上，则d(x + y) = d(x + 1)
否则，假设x > y且在不同分支上，分支点为z，则d(x + y) = d(x) + d(y) - d(z)
if n mod 2 = 0
   a = l(n / 2)
else
a = l(n - 1) + 1
endif
b = a
for i = 1 to n / 2
   根据规则，从i, n - i计算d(n)
if d(n) < b thenb = d(n) endif
endfor

输出b

aimisiyou 发表于 2014-12-24 21:34:18

将n转为2进制，去掉首位，剩余位数+剩余位数中1的个数即为求a^n所需的乘法次数。如a^10，10的二进制数为1010，len(010)+1=4次，即需做4次乘法。

aimisiyou 发表于 2014-12-25 19:07:47

aimisiyou 发表于 2014-12-24 21:34
将n转为2进制，去掉首位，剩余位数+剩余位数中1的个数即为求a^n所需的乘法次数。如a^10，10的二进制数为101 ...

看来我错了，采用二分法不正确，31只需7步，但len(1111)+4=8。

查看完整版本: 关于a^n的计算