谷歌代码果酱 2008 年第 1A 轮 Q 3.

Question

对于谷歌代码jam 2008中的问题陈述：第1轮A问题3

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

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

对于 n = 2，(3 + √5(² = 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: %.3dn",i,a[(int)n]);
    }
    fclose(stdin);
}

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

谁能解释发生了什么？

Answer 1

首先，行

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为负时，a % b的结果本身必须是负数。