将变量声明为全局变量会给出不同的答案

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("%lldn", 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("%lldn", 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），因此对当前调用有副作用。