1

对于google codejam 2008 中的问题陈述：Round 1A Question 3

在这个问题中，您必须找到数字 (3 + √5) n小数点前的最后三位。

例如，当 n = 5 时，(3 + √5) 5 = 3935.73982... 答案是 935。

对于 n = 2，(3 + √5) 2 = 27.4164079... 答案是 027。

我的解决方案基于 T(i) = 6*T(i-1) - 4*T(n-2) + 1，其中 T(i) 是 n=i 的整数部分，如下所示：

#include<stdio.h>
int a[5000];
main(){
    unsigned long l,n;
    int i,t;
    a[0]=1;
    a[1]=5;
    freopen("C-small-practice.in","r",stdin);
    scanf("%d",&t);
    for(i=2;i<5000;i++)
            a[i]=(6*a[i-1]-4*a[i-2]+10001)%1000;
    i=t;
    for(i=1;i<=t;i++){

            scanf("%ld",&n);
            printf("Case #%d: %.3d\n",i,a[(int)n]);
    }
    fclose(stdin);
}

在a[i]=(6*a[i-1]-4*a[i-2]+10001)%1000;我知道会有整数溢出的行中，但我不知道为什么通过添加 10,000 我得到了正确的答案。我正在使用 GCC 编译器，其中 sizeof(int)=4

谁能解释发生了什么？

4

1 回答 1

2

首先，线

a[i]=(6*a[i-1]-4*a[i-2]+10001)%1000;

实际上不应导致任何溢出，因为您将所有先前的值保持在 1000 以下。

其次，您是否考虑过如果6*a[i-1]-4*a[i-2]+1为负数会发生什么？取模运算符不必总是返回正值；它也可以返回负值（如果你要划分的东西本身是负的）。

通过添加 10000，您可以确保无论之前的值是什么，该表达式的值都是正数，因此 mod 将给出正整数结果。

扩展第二点，这里是 C99 规范的 6.5.5.6：

当整数被除法时， / 运算符的结果是代数商，其中任何小数部分被丢弃。如果商 a/b 是可表示的，则表达式 (a/b)*b + a%b 应等于 a。

“丢弃”一词旁边的注释说明/“向零截断”。因此，要使第二句话为真，a % bwhen的结果a是否定的本身必须是否定的。

于 2013-09-23T16:35:31.237 回答