4

私の仕事は、特定の開始スタックを特定の目標スタックに移動する最短の移動シーケンスを見つけるコードを作成することです。スタックがどのように始まるかを描いた本の元のリストと、必要な目標の順序を示す本の目標リストが与えられます。問題は、標準の並べ替えアルゴリズムが機能しないことです。本は、特定の論理ではなく、人の好みに基づいています。

質問で使用してほしいシステムは次のとおりです。スタック内のどこからでも本を1冊ずつ引き出し、スタックの一番上に置きます。したがって、本X、Y、およびZがある場合は、Yを引き出して、Y、X、Zの順序にすることを選択できます。

イニシャル：

'1984 - George Orwell'
'Moby Dick - Herman Melville'
'To Kill A Mockingbird - Harper Lee'
'Atlas Shrugged - Ayn Rand'
'The Black Cat - Edgar Allen Poe'

ゴール：

'Atlas Shrugged - Ayn Rand'
'To Kill A Mockingbird - Harper Lee'
'1984 - George Orwell'
'Moby Dick - Herman Melville'
'The Black Cat - Edgar Allen Poe'

これは宿題です。しかし、それは任務の目的を損なうので、私は私のためにそれをする人を探していません。どこから始めればよいかわからないので、始めるためのアイデアやヒントを探しています。

注：私はこれを宿題としてタグ付けするつもりでしたが、タグは明示的にそうしないと言っているので、私はしていません。これが間違っている場合は、私を訂正してください。

4

2 に答える 2

4

わかりました、主な問題はあなたが上に置くことができるだけであるということです、しかしあなたはどんな本でも選ぶことができます。メソッドではなくヒントが必要だったので、次のようにします。

  1. あなたは上にしか置くことができないので、最も難しいので常に下を見始めてください
  2. 明らかに、すでに適切な場所にある本を引っ張る必要はありません
  3. 正しい順序で本の上にある本の下にあるすべての本を引っ張る必要があります
  4. 本を上に積み重ねる場合は、正しい順序でそこに置く必要があります
  5. ABGFCEDをアルファベット順に変換するには、常に最後にアタッチする場合は、E、F、Gの順にプルするのが最適です。

これがあなたを始めさせてくれたことを願っています、そして私は明確にしたことはありません。

于 2012-11-09T02:17:32.157 に答える
0

本当に単純なアルゴリズムは、一番下にある次の本を見つけて引き出すたびに、スタックをループするだけです。小さなスタックには線形探索で十分です。

'The Black Cat - Edgar Allen Poe'あなたの例では、最初の反復、'Moby Dick - Herman Melville'2番目、'1984 - George Orwell'3番目などで引き出します。

これはO（n ^ 2）アルゴリズムです。

于 2012-11-09T02:21:03.500 に答える