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

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

使用局部变量时，您有 'several' 个局部变量 a,b,c,d,k（一个独立于作用域）。

使用全局变量时，您可以与对 fib 的不同调用共享变量：

所以

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

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

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

On declaring variables as global gives different answers

c++

variables

global-variables

fibonacci