1

私は最初のアルゴリズムを書こうとしていますが、これは私が始めると思われる疑似コードです。アルゴリズムは、k スポットのセット {0,1,2,3,4,5,6,7,8,9} を並べ替えることを想定しています。たとえば、n= 0 ～ 9 を設定すると、n=10 および r=kn^r 順列になります。

U={0,1,2,3,4,5,6,7,8,9} (単方向リスト)
S は最初は空で、k=2 とします。セットの順列は 10^2 である必要があります。疑似コードを段階的にたどる..

1) 「U から e を削除」および「S の末尾に追加」

U={1,2,3,4,5,6,7,8,9}

S={0}

2) k!= 1 であるため、"PuzzleSolve(k-1,S,U)" を再度実行します。

U={2,3,4,5,6,7,8,9}

S={0,1} および k =1 であるため、解をチェックします。解決策が見つからないと仮定すると、1 は U に戻り、S から削除されます。

今：

U ={2,3,4,5,6,7,8,9,1}

S ={0}

したがって、最初の行の for ループにより、 U のすべての数値が 0 と一致するまで、これが繰り返されます。ただし、私の質問は、S の末尾から e を削除するにはどうすればよいですか? S を連結リストにしたかったのですが、片連結リストの末尾から連結を外すことはできないと思います。S にはどのデータ構造を使用すればよいですか?

Algorithm PuzzleSolve(k,S,U):

Input: Integer k, sequence S, and set U (universe of elements to test)

Output: Enumeration of all k-length extensions to S using elements in U without repetitions


**for** all e in U **do**
  Remove e from U {e is now being used}
  Add e to the end of S
  **if** k = 1 **then**
         Test whether S is a configuration that solves the puzzle
         **if** S solves the puzzle **then**
           **return** “Solution found: ” S
**else**
  PuzzleSolve(k - 1, S,U)
Add e back to U {e is now unused}
Remove e from the end of S
4

3 に答える 3

2

この場合、配列または arrayList を使用するのが理にかなっています。セットのサイズはすでにわかっているので、リンク リストを使用する必要はありません。ただし、質問からは、独自の構造を作成する必要があるのか​​ 、組み込みの構造を使用できるのかが明確ではありません。配列を使用できない場合は、連結リストを実装できます。for-each-loop で反復処理できるように、連結リストを反復可能にする必要があります。

リンクされたリストの作成についてサポートが必要ですか?

于 2013-09-07T19:10:02.270 に答える