关于a^n的计算

northwolves

1. 计算a^n至少需要几步乘法（显然>=$log_2 n$) 2. 使用该最少的步数共有多少种不同的计算方法？ 比如： 计算a^14最少需要6步，共14种计算方法： 1 2 3 4 7 14 1 2 3 5 7 14 1 2 3 6 7 14 1 2 3 6 8 14 1 2 3 6 12 14 1 2 4 5 7 14 1 2 4 5 9 14 1 2 4 5 10 14 1 2 4 6 7 14 1 2 4 6 8 14 1 2 4 6 10 14 1 2 4 6 12 14 1 2 4 8 10 14 1 2 4 8 12 14 3. a^n计算时，最少步数正好有 n种的除了1和14还有哪些？

asdfslw

一般地，一数列1=a0, a1, a2,... ar=e，如果对每个i=1,2,...r,存在一整数对(j,k),j<=k

northwolves

谢谢回复。 更正一下，1楼的a^14 应该是5步： 1 2 3 4 7 14 即 a*a=a^2 a*a^2=a^3 a^2*a^2=a^4 a^3*a^4=a^7 a^7*a^7=a^14

无心人

乘法链的长度似乎有公式可以估算上界

northwolves

计算a^n至少需要几步乘法（显然>=log2n) ------------------------------------------------- 已经推导出： p(1)=0 p(2)=1 p(3)=2 p(2^n)=n p(2n)=p(n)+1 p(2n+1)=min(p(n)+2, p(n+1)+2)

wayne

按楼上的思路，编了一个Mathematica程序：

2. g = If[# > 3, If[EvenQ[#], #0[#/2] + 1, Min[#0[(# - 1)/2], #0[(# + 1)/2]] + 2], # - 1] &;
3. Table[{ii,g@ii}, {ii, 1, 100}]

复制代码

wayne

5# northwolves

p(2n+1)=min(p(n)+2, p(n+1)+2)

感觉这个好像有问题

wayne

比如：计算 a^27,按5楼的理论，应该先算出13或14，而a^13,a^14都至少需要5步，所以， 27应该要7步，可是这个只需要6步即可完成： 2,3,6,12,24,27 2,4,8,9,18,27

wayne

另外，算31,63,127,255,......似乎也有问题。 a^16需要四步，按5楼的理论，那么a^31应该要6步，可六步的方案我笔画了很长时间，也没找到。 7步的如下： 2，3，6，12，24，30，31 2，3，6，12，18，30，31 2，4，5，10，20，30，31 2，4，5，10，15，30，31

medie2005

Knuth写了一个程序计算的： http://www-cs-faculty.stanford.edu/~knuth/programs.html