c++ - 在将变量声明为全局变量时给出了不同的答案

Question

我有两个相似的代码

代码1:

#include <bits/stdc++.h>

using namespace std;

long long int MOD = 1000000007;

long long int fib(long long int n)
{
    if(n <= 2)
        return 1;
    long long int k = n/2;
    long long int a = fib(k+1);
    long long int b = fib(k);
    if(n%2 == 1)
        return (a*a + b*b)%MOD;
    else
    {
        long long c = 2*a - b;
        if(c < 0)
            c+=MOD;
        return (b*(c))%MOD;
    }
}

int main()
{
    long long int n;
    scanf("%lld",&n);
    printf("%lld\n", fib(n));
    return 0;
}

这里我将变量k,a,b定义为局部变量。对于 n = 100000000，输出为 908460138。

代码2:

#include <bits/stdc++.h>

using namespace std;

long long int MOD = 1000000007;

long long int a,b,c,d,k;

long long int fib(long long int n)
{
    if(n <= 2)
        return 1;
    k = n/2;
    a = fib(k+1);
    b = fib(k);
    if(n%2 == 1)
        return (a*a + b*b)%MOD;
    else
    {
        c = 2*a - b;
        if(c < 0)
            c+=MOD;
        return (b*(c))%MOD;
    }
}

int main()
{
    long long int n;
    scanf("%lld",&n);
    printf("%lld\n", fib(n));
    return 0;
}

这里我将变量k,a,b定义为全局变量。对于 n = 100000000，输出为 265038576。

任何人都可以解释为什么我的输出会有这种差异。 Code1 给出了正确的输出(但运行时间更长)。如何解决？

Answer 1

当使用局部变量时，您有“多个”局部变量 a,b,c,d,k(一个独立于作用域)。

当使用全局变量时，您可以在对 fib 的不同调用中共享该变量:

所以

a = fib(k+1);
b = fib(k);

第二次调用将修改之前的 k、a(如果 k > 2)，因此对当前调用有副作用。