1

google codejam 2008の問題記述: Round 1A Question 3

この問題では、数値 (3 + √5) nの小数点の前の最後の 3 桁を見つける必要があります。

例えば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を追加することで正しい答えが得られる理由はわかりません。sizeof(int)=4 の GCC コンパイラを使用しています

誰が何が起こっているのか説明できますか?

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 は正の整数の結果を返します。

その 2 番目のポイントを拡張すると、C99 仕様の 6.5.5.6 になります。

整数を除算すると、/ 演算子の結果は、小数部分が破棄された代数商になります。商 a/b が表現可能な場合、式 (a/b)*b + a%b は a と等しくなります。

「廃棄」という言葉の横のメモには、「/ゼロに向かって切り捨てる」と記載されています。したがって、2 番目の文が真であるためには、a % bwhen ais negative の結果自体が負でなければなりません。

于 2013-09-23T16:35:31.237 に答える