0

N*Nすべての対角要素が であるようなプロパティを持つ上三角行列がありa1,a2,a3,...,aNます。a[i][j] (for all j>i) 私はそれが欲しい

(a[i][j-1] + a[i+1][j]) / 2.

多くのテストケースがあり、答えを計算するために毎回このプロパティを適用する必要があります。すべてのテストケースで全体の実行時間を短縮するために、これを行うための最適な方法は何ですか? テスト ケース: 入力はN and a1,a2,...,aN.

答えを計算するには、次のことを行う必要があります。

a[0][0] + a[0][2] + ... + a[0][n-1] + a[2][n-1] + a[4][n-1] + ... + a[n-1][n-1].

私の解決策（タイムアウトし続ける）：

#include<stdio.h>
double a[2000][2000];
int main(){
int test;
scanf("%d",&test);
//int arr[2000];
while(test--){
    int n,i,j;
    //scanf("%d",&n);
    scanf("%d",&n);
    for(i=0;i<n;i++){
         int num;
         scanf("%d",&num);
         if(n!=1)
            a[i][i] = num*0.5;
         else
            a[i][i] = num;
     }
    for(j=1;j<n;j++){
         int k=j;
         for(i=0;i<n-j;i++,k++){
             if(i==0 && k==n-1)
                 a[i][k] = (a[i+1][k]+a[i][k-1]);
             else
                 a[i][k] = (a[i+1][k]+a[i][k-1])*0.5;
         }
     }
     float sum=0.0;
     for(i=0;i<n;i+=2){
         if( i != n-1 )
         sum+=a[0][i]+a[n-1-i][n-1];
         else
         sum+=a[0][i];
     }
    printf("%.3f\n",sum);
}
getch();
}

上記のコードを最適化する方法のヒントをいくつか提供してください。

4

1 に答える 1

0

マトリックス全体を保存する必要はありません。列 j-1 から列 j の値を決定し、値を置き換えることができます。

double b[2000];
double sum = 0;

for (j=0; j<n; ++j) {      
  b[j]=a[j];
  i=j;
  while (i>0) {
    --i;
    b[i] = (b[i+1]+b[i])*0.5;
  }
  if (i%2==1) sum += b[0];
}
for (i=2; i<n; i+=2) {
  sum += b[i];
}

これにより、メモリ効率が向上し、キャッシュが使いやすくなりますが、複雑さは軽減されません。

いくつかの値が 0.5 倍されるときの追加のロジックがあります。それが何に基づいているのかわかりません。

于 2012-10-06T22:20:45.403 に答える