C for循环几乎正确

Question

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

迭代函数如下

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。

Answer 1

您的代码在数学上是“正确的”。您遇到的是迭代函数中循环计数器的整数溢出。由于 i 是一个带符号的 int，它被包裹成负数(与你的无符号 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 的大小和符号，答案将匹配