关于a^n的计算

wayne

wikipedia说此题目前没有有效的方法： http://en.wikipedia.org/wiki/Addition_chain 给一个图： 更详细的信息： http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html

northwolves

Found in http://wwwhomes.uni-bielefeld.de/achim/add_fun1.html For n=375494703 holds: 34 = l(2n) < l(n) = 35.

medie2005

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

无心人

定义链的度信息为节点到数字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 then b = d(n) endif endfor 输出b

aimisiyou

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

aimisiyou

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

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