一位 friend 向我提出挑战,要求我编写一个程序来获取三个整数 (int a, int n, int k)
并尽可能高效地进行计算,a^n mod k
我想到了这个解决方案
public static int rec(int a,int n,int k) //calc a^n mod k
{
if(n == 1)
return a % k;
int exp1 = rec(a, n/2, k), exp2 = exp1;
if(n % 2 == 1)
exp2 = rec(a, n/2 + 1, k);
return (exp1 * exp2) % k;
}
这是一个非常简单的递归解决方案,依赖于 a^(b+c) mod d = (a^b mod d * a^c mod d) mod d
的事实,并运行在对数时间。至少理论上是这样。
在实践中,当我们测量我们的解决方案时,他的线性时间解决方案比我的解决方案更好。我怀疑这是因为我使用递归而不是循环。那有意义吗?如果是这样 - 我怎样才能将这段代码变成一个迭代程序?
最佳答案
Does that make sense?
是的。正如 Boris The Spider 指出的那样,Java 中没有尾部优化。
how can I turn this code into an iterative program?
让我复制粘贴一个迭代解决方案来计算来自 here 的数字的幂
int pow(int x, int n) {
int res = 1;
while(n > 0) {
if(n % 2 == 1) {
res = res * x;
}
x = x * x;
n = n / 2;
}
return res;
}
免责声明:虽然上面的代码在我看来没问题,但我还没有亲自测试过。
关于java - 将递归程序转为迭代,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42115120/