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

您的代码在数学上是 'correct'。您运行遇到的是迭代函数中循环计数器的整数溢出。由于 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 的大小和符号，答案将匹配

C for循环几乎正确

C for loop almost right

c

for-loop

uint32

uint64