4 
#include <vector>
std::vector<long int> as;

long int a(size_t n){
  if(n==1) return 1;
  if(n==2) return -2;
  if(as.size()<n+1)
    as.resize(n+1);
  if(as[n]<=0)
  {
    as[n]=-4*a(n-1)-4*a(n-2);
  }
  return mod(as[n], 65535);
}

上記のコードサンプルは、メモ化を使用して、いくつかの入力に基づいて再帰式を計算しますn。同じ式を使用する純粋な再帰関数を記述したため、これがメモ化を使用していることはわかっていますが、これは、の値がはるかに大きい場合にはるかに高速ですn。私はこれまでベクターを使用したことがありませんが、いくつかの調査を行い、ベクターの概念を理解しています。メモ化では、計算された各値が保存されることになっているため、同じ計算を繰り返し実行する代わりに、すでに計算された値を簡単に取得できることを理解しています。

私の質問は、このメモ化はどのように行われ、どのように機能するのかということです。nの値がすでに存在するかどうかを確認する時点で、コードを確認できないようです。また、の目的がわかりませんif(as[n]<=0)。この式は正と負の値を生成する可能性があるため、このチェックが何を探しているのかわかりません。

ありがとう、私はこれがどのように機能するかを理解していると思います。実際、私が思っていたよりも少し単純です。

シーケンス内の値が0になることはないと思います。したがって、nは1から開始する必要があると思うので、これでうまくいくはずです。

しかし、ゼロが私のシーケンスで実行可能な数であった場合、それを解決できる別の方法は何ですか？たとえば、5つが表示されない場合はどうなりますか？ベクトルを5で埋める必要がありますか？

編集：うわー、コードをチェックしてこれを入力しているときに、他にもたくさんの応答がありました。皆さんの助けに感謝します、私は今それを理解していると思います。

4

5 に答える 5

6

if (as[n] <= 0)チェックです。あなたが言うように有効な値が負になる可能性がある場合は、チェックするために別の番兵が必要です。有効な値をゼロにすることはできますか？そうでない場合は、テストを行いますif (as[n] == 0)。これにより、デフォルトでintsのベクトルがゼロで埋められるため、コードを簡単に記述できます。

于 2008-09-29T03:08:31.017 に答える
1

コードはis（as [n] <= 0）を誤ってチェックしているように見え、関数の負の値（ほぼ1つおきの値に見える）を再計算します。これにより、再帰的ソリューションでは2 ^ nではなくnで作業が線形にスケーリングされるため、実行速度が大幅に向上します。

それでも、（as [n] == 0）かどうかをテストすることをお勧めします。これは、私のシステムで3倍高速に実行されているように見えます。関数が0を返すことができる場合でも、0の値は、計算に少し時間がかかることを意味します（ただし、0が頻繁な戻り値である場合は、値が計算されたかどうかを示す別のベクトルを検討することをお勧めします。単一のベクトルを使用して関数の値とそれが計算されたかどうかを格納する）

于 2008-09-29T03:36:01.403 に答える
0

数式で正の値と負の値の両方が得られる場合、この関数には重大なバグがあります。チェックif(as[n]<=0)は、この計算値をすでにキャッシュしているかどうかをチェックすることになっています。しかし、数式が負になる可能性がある場合、この関数はこのキャッシュされた値をたくさん再計算します...

おそらく本当に欲しかったのはvector<pair<bool, unsigned> >、値が計算されたかどうかをブール値が示す、でした。

于 2008-09-29T03:30:23.507 に答える
0

投稿されたコードは、約40％の時間しか記憶していません（正確には、記憶された値が正の場合）。Chris Jester-Youngが指摘したように、正しい実装は代わりにチェックしif(as[n]==0)ます。または、メモ化コード自体を変更して読み取りを行うこともできますas[n]=mod(-4*a(n-1)-4*a(n-2),65535);

（==0メモ化された値が0の場合、チェックでさえ手間がかかります。幸い、あなたの場合、これは決して起こりません！）

于 2008-09-29T03:38:18.433 に答える
0

このコードにはバグがあります。as[n] <= 0 の場合、as[n] の値を再計算し続けます。正であることが判明した a の値を記憶します。as[] には十分な正の値があり、再帰がすぐに終了するため、メモ化を使用しないコードよりもはるかに高速に動作します。標識として 65535 より大きい値を使用することで、これを改善できます。ベクトルが拡張されると、ベクトルの新しい値はゼロに初期化されます。

于 2008-09-29T04:20:16.897 に答える