最小の移動数でディスクのセットを並べ替える

Question

この質問は、私がこの問題にどのようにアプローチできるかについての思考/洞察をどこで探しているのかを探るアルゴリズム/アプローチの詳細です。私は一連のプログラミング問題をブラウズしており、アイテムのリストをソートするのに必要な最小限の移動数を提供する必要がある1つの質問に出くわしました。この問題は「Easy」とマークされていますが、私はこれに対して良い解決策を見つけることはできません。あなたの考えは大歓迎です。 問題文は次のようなものです。

Xには同じ半径のN個のディスクがあります。すべてのディスクには1からNまでの固有の番号が付いています。ディスクはランダムな順序で1つのパイルに重ねて配置されます。 Xはディスクのこの山を上から下に向かって昇順にソートしたいと考えています。しかし、彼はこれを行うための非常に特殊な方法を持っています。 ひとつのステップでは、彼は山から1枚のディスクしか選択できません。彼は一番上に置くことができます。。そして、Xは可能な最小限のステップでディスクの山を並べ替えることを望んでいます。ランダムに順序付けられたディスクのこの山をソートするのに必要な最小限の移動回数を見つけることができますか？

Answer 1

最小移動を考慮せずに簡単に解決する方法は次のとおりです。 最大値のディスクを取り出し、上に置きます。そして2番目の最大値を取って頂きます。そして、すべてが整理されるまで続けます。今、この貪欲なアプローチは、あなたに最小限のステップを与えるとは限りません。 [5,4,1,2,3]上記欲張りアプローチではこのようになる：

[5,4,1,2,3] 
[4,1,2,3,5] 
[1,2,3,5,4] 
[1,2,5,4,3] 
[1,5,4,3,2] 
[5,4,3,2,1] 

5が移動を要するが、最小の移動は、このすべき：

この例検討します唯一の2

は、最初のNから始まる降順に既に存在するどのように多くの価値だと思い、最小の動きを取得するのにかかる

[5,4,1,2,3] 
[5,4,1,3,2] 
[5,4,3,2,1] 

は、あなたが移動する必要はありませんそれらの何かを考えることができます。残りの部分は、最小値である移動する必要があります。 10から出発して、実施例ここ

[1,5,2,3,10,4,9,6,8,7]

ためDESC順[10,9にある合計4つの数字であります、8,7]残りの部分は移動する必要があります。だから最小の動きは、10-4 = 6

[1,5,2,3,10,4,9,6,8,7] 
[1,5,2,3,10,4,9,8,7,6] 
[1,2,3,10,4,9,8,7,6,5] 
[1,2,3,10,9,8,7,6,5,4] 
[1,2,10,9,8,7,6,5,4,3] 
[1,10,9,8,7,6,5,4,3,2] 
[10,9,8,7,6,5,4,3,2,1]