package main import (
"fmt"
) //递归形式分治求解
func power(x, m int) int {
if m == {
return
} else {
y := power(x, m/)
y = y * y
if m% != {
y = x * y
}
return y
}
} //迭代形式分治求解, 分析可用到如下图
func power2(x, m int) int {
y :=
var k uint32
for k = ; (m >> k) > ; k++ {
}
k--
for k > {
y = y * y
if (m>>k)% > {
y = y * x
}
k--
}
y = y * y
if m% != {
y = y * x
}
return y
}
func main() {
x :=
m :=
fmt.Println(x, "^", m, power(x, m))
fmt.Println(x, "^", m, power2(x, m))
}
//X的任意M次方,可从X的一次方,开始向上迭代产生,而路径的选择则根据M的二进制表示,来选择唯一路径,
比如X^15, 15的二进制形式为1111, 则选择的路径对应上图中的1111, 其他同理