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是有符号整型，因此它被包装成负数(与无符号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匹配，则答案将匹配