继续求m ^ n 问题(m与n是正整数)。前面的数值自乘递归解会得到一个递归的程序,请编制一个运算效率同样高的非递归的程序。

说明: 或许读者有自己独特的看法, 但在此提供一个简单的建议, 可以采用它来编写程序, 当然也可以把它化简。建议是把指数n用二进制来看, 比如若n=13, 那么13(10进制)=1101(2进制)=2 ^ 3 + 2 ^ 1 + 2 ^ 0, 所以求m ^ (2 ^ 3 + 2 ^ 1 + 2 ^ 0)时就相当于求m ^ (2 ^ 3) m ^ (2 ^ 2) m ^ (2 ^ 0);会发现二进制表示中对应那一位是1, 在m中就有那么一项。把这个观念编制成程序。

另外一个办法是可以把递归解法中每一个递归步骤的n提出来,看在什么时候用(m ^ k) ^ 2,什么时候用m(m ^ 2k),然后用非递归方式写出来。

了解了这些观点之后,编写这个程序就不难了。在编写完程序之后,还应该分析一下程序乘了多少次。

解答见iteration_power.py