Question

将recursion改成loop....

int powmod2 (int x, int e, int m)
int xsqrm = x*x%m;
if (e==0)
return 1;
else if (e%2==0)
return powmod2 (xsqrm, e/2,m);
else if (e%2==1)
return x* powmod2 (xsqrm, (e-1)/2,m)%m;
}
如题, 将这个code改成不用recursion的东西.. 我快被 e=奇数时候的那个condition弄疯了.......

感激不尽

Answer 1

int powmod(int x, int e, int m) {
stack<int> stack;

while (e != 0) {
stack.push(e % 2);
e = e / 2;
}

int result = 1;
while (stack.empty() == false) {
result = (result * result) % m;
if (stack.pop() == 1) {
result = (result * x) % m;
}
}

return result;
}

其中的stack是栈的实现，需要你根据你具体语言而定
摸乘这个东西只是想把递归转换成迭代是有点麻烦，但是如果你知道模乘的原理就不难写出来了