1

我正在研究一个家庭作业问题，涉及将递归解决方案与其迭代对应物进行比较。目前我的递归函数适用于给定的一组值，但是迭代版本似乎适用于除最后一个值之外的每个值，这对我来说似乎很奇怪。

迭代函数如下

uint64_t
normalPower(uint64_t k, uint64_t n, uint32_t m)
{
    uint64_t answer = 1;
    for (int i = 1; i <= n; i++)
    {
    answer = answer * k % m;
    }
    return answer;
    return EXIT_SUCCESS;

}

其他相关信息是

uint64_t n;
for (int i = 0; i <= 10; i++)
{
    n = n * 10;
}

和

uint64_t k = 1835;
uint32_t m = 590623782;

当我运行递归函数时，我得到了我与其他同学确认的最终值的答案 424171147。我只是对为什么该算法适用于所有以前的值而不是最后一个值感到困惑。非常感谢任何和所有帮助。

附带说明：我知道迭代版本非常低效，这就是分配的重点。

这里要求的是递归函数

uint64_t
fastPower(uint64_t k, uint64_t n, uint32_t m)
{
    uint64_t answer = 0;
    if (n % 2 == 0 && n > 1)
    {
    uint64_t kn = fastPower(k, n / 2, m);
    answer = (kn * kn) % m;
    return answer;
    }
    else if (n > 1)
    {
    answer = fastPower(k, 1, m) * fastPower(k, n - 1, m) % m;
    return answer; 
    }
    else
    answer = k % m;
        return answer;
    return EXIT_SUCCESS;
}

n 在声明时也被初始化为 1。

4

1 回答 1

1

您的代码在数学上是“正确的”。您遇到的是迭代函数中循环计数器上的整数溢出。由于i是带符号的 int，因此它被包装成负数（与您的 unsigned 相比n，它被解释为无符号，这将导致奇怪的结果）

如果你改变

for (int i = 1; i <= n; i++)
{
    answer = answer * k % m;
}

至

for (uint64_t i = 1; i <= n; i++)
{
    answer = answer * k % m;
}

然后i将匹配n大小和符号，并且答案将匹配

于 2015-10-22T13:43:31.983 回答