计算 x^25 至少需要几次乘法运算？

luyuanhong

这是台湾网友 YAG 发表在“陆老师的《数学中国》园地”的一个帖子，

欢迎大家一起来想想如何解答：



是否題目舉例有錯 需改成這樣

以符號“  ^  ”代表指數運算，計算X^8  的值須要3次乘法，即先算出T=X＊X，然後
再計算T^2=X^4,  (T^2)^2=X^8   就可以得到X^8的值，則計算X^25至少須要幾次乘法運算？
（A）5        （B）6         （C）7         （D）8

ANS: A

好怪喔!

drc2000

第一步：先得X ^2=X *X 与X ^3=A*X ，(分别记做A，B，合计两次乘法)
第二步：再得X ^6与X ^9，（类似上一步，分别记做C,D，实际也是合计两次乘法）
第三步：得X ^18，【（X ^9）*（X ^9），一步乘法，记做E】
第四步：得X ^4，【同第三步，也只要用一步乘法,记做F】

以上四步，总计用了6次乘法，得到了ABCDEF6个数，
即X ^2，X ^3，X ^6，X ^9，X ^18，X ^4

而想得到X ^25=X ^18*X ^4*X ^3=E*F*B的结果，至少还需要2次乘法

以上共8次

luyuanhong

题  计算 x^25 至少需要几次乘法运算？

解  第一次：x * x = x^2 。

    第二次：x^2 * x^2 = x^4 。

    第三次：x^4 * x^4 = x^8 。

    第四次：x^8 * x^8 = x^16 。

    第五次：x^16 * x^8 = x^24 。

    第六次：x^24 * x = x^25 。

    看来，六次是最少的，不可能再少了。

luyucheng1

按连续方次运算，然后补尾次数，这样最省。

(((x^2)^2)^2)^2=16次方（4次运算），补2的8次方和2的一次方；共需6次运算。

drc2000

luyuanhong 发表于 2014-6-15 16:25
题  计算 x^25 至少需要几次乘法运算？

解  第一次：x * x = x^2 。

强！
（现在够8个字了吧，是么？）

drc2000

luyucheng1 发表于 2014-6-15 17:23
按连续方次运算，然后补尾次数，这样最省。

(((x^2)^2)^2)^2=16次方（4次运算），补2的8次方和2的一次方 ...

棒！
（现在够8个字了吧，是么？）

ataorj

x^25
a=xx:1_2
b=aa:1_4
c=bb:1_8
d=cc:1_16
e=dcx:2_24+1
=====6
----------------
a=xx
b=aaa
c=bb
d=cc
e=dx
===6
-------------
a=xx
b=aa
c=bbb
d=ccx
===6
%%%%%%%%%%%%
a=xx:1
b=aa:1
c=bb:1
d=cc:1
e=dd:1

e/c/x:2

5次乘法2次除法
7次运算,不是最少次数运算,但是不计除法成本则是需要的最少次乘法运算
%%%%%%%%%%%%%%

luyucheng1

不计除法次数，题目也许是这个意思。。。。。

这样，只要连续平方运算，达到或超过要求的次数，即为最少乘法次数。
16方次<x^n<=32方次，都属于5次乘法运算。如x^25=x^32/(x^7),，除的方次不计，乘法用了5次。

luyuanhong

题  计算 x^25 至少需要几次乘法运算？

解  如果乘法以外还允许做除法，则有

    第一次乘法：x * x = x^2 。

    第二次乘法：x^2 * x^2 = x^4 。

    第三次乘法：x^4 * x^4 = x^8 。

    第四次乘法：x^8 * x^8 = x^16 。

    第五次乘法：x^16 * x^16 = x^32 。

    第一次除法：x^８ ÷ x = x^７ 。

    第二次除法：x^32 ÷ x^7 = x^25 。

    这样，只需要 5 次乘法和 2 次除法就可以了。

kingwang82

LS的说的不对吧，除法就不算乘法了？？那我把第一步改成X÷1/X  后面依次更改，那么一次乘法运算都不用了！！