1

[5、2、3、2、0、2]のような数字の配列がある場合

次のように、既にアクセスしたインデックスに到達するまで、配列に継続的にインデックスを付けることができる回数をカウントしたいと思います。

A[0] = 5 
A[5] = 2
A[2] = 3
A[3] = 2 stop here because we already indexed 2.

したがって、私の問題は、以前にアクセスしたインデックスを格納するために追加のデータ構造を使用せずに、インデックス作成を停止するタイミングをプログラムに指示する方法はありますか？

4

2 に答える 2

1

この配列を有向グラフとして扱っているようです。もしそうなら、あなたが本当に求めているのは、有向グラフでサイクルを検出する方法です。

見る：

しかし、あなたの質問に具体的に答えるには、迷路の中をさまよっていた場合、以前に特定のジャンクションに行ったことがあるかどうかをどのように判断しますか？ブレッドクラムをドロップするか、スレッドをアンスプールして、どこにいたかを思い出させることを検討してください。ここでも同じです。元の配列に「訪問済み」フラグで注釈を付けるか、訪問したインデックスのコピーを独自の配列に保持する必要があります。

于 2012-10-22T23:47:50.347 に答える
0

配列要素を無効な値、たとえば-1に初期化して開始する場合、次の擬似コードのように、配列要素がすでに割り当てられている場合は停止できます。

if (A[x] == -1)
    A[x] = y
else
    stop
于 2012-10-22T23:46:49.090 に答える