0

ConwayのGameofLifeを組み込みデバイスに実装しようとしています。使用できるRAMは1kbしかなく、合計で512バイトに相当する2048個のセルがあります。一度に次世代の8x8セルを計算するので、一度に2世代をRAMに保存する必要はありません。

しかし、私もやりたいのは、GoLがループ/静的状態でスタックしていることを検出することです。PCでモックアップを作成したときは、最後の100世代と1000世代を保存し、現在の世代と比較しました。1kbのRAMではこれを行うことはできません。私が考えているのは、単に最後のx世代のハッシュを計算し、そのハッシュを現在の世代のハッシュと比較することです。

XTEAまたはSHA1の非常に軽い実装がいくつかありますが、両方の世代の個々のセルが等しいかどうかを判断する必要があるため、ハッシュがこの目的に本当に適しているかどうかはわかりません。あなたは何をお勧めします？

ありがとう、

ジョー

編集：考えてみると、実際に一致の数を数えることができ、それが特定のしきい値に達した場合、それがループ内にあると想定しますが、1000世代ごとに繰り返されるパターンではうまく機能しません。

4

3 に答える 3

1

かなり良い選択だと思います。ハッシュ衝突の可能性は非常に低いので、原子炉ではなく、あなたのアプリケーションとして受け入れられます。

于 2011-12-09T15:07:26.757 に答える
0

ハッシュは、物事が等しくない場合に伝えるのに適しています。ハッシュが等しい場合でも、個々の比較を行う必要があります（十分にすべきです）。

于 2011-12-09T14:59:29.743 に答える
0

より多くのRAMを搭載したデバイスを入手することにしましたが、パターンがある場合は同じパターンがx世代ごとに一致しますが、ランダムなハッシュ衝突の場合は一致しません。したがって、次の世代がある場合：

123*
231
312
123*
231
312
123*

123は3世代ごとに一致します。これは、ハッシュの衝突では発生しません。

他の答えは正しくて価値がありましたが、これが問題の解決策を提供する唯一の答えです。自分の質問に答えるときのエチケットがわからないので、これを答えとしてマークするべきではなかった場合は、反対票を投じないでください。メッセージを送ってください。正しい答えを再割り当てします。

ありがとう、

ジョー

于 2011-12-20T18:07:02.967 に答える