ロボットをシミュレートして、蓋と対応する瓶を一致させるJavaプログラムを作成する必要があります。ロボットには 2 つのアームがあり、1 つは蓋用、もう 1 つは瓶用です。蓋と蓋、瓶と瓶を比較することはできません。ユーザーは次の 3 行を入力します。
5(n)
9 7 2 5 6(size of lids)
2 6 5 7 9(size of jars)
出力は次のようになります。
3 5 4 2 1
2 行目の 3 番目の数値は、3 行目の 1 番目の数値と同じです。
分割統治アルゴリズムを使用することになっていますが、どこから始めればよいかまったくわかりません。私が行かなければならないのは、それがクイックソートに似ているということだけです。どんな助けでも大歓迎です。
分割統治アルゴリズムは、最初は混乱するかもしれません。解決できない比較的大きな問題があるかのように考えてみてください。ただし、その問題がはるかに小さい場合は、答えを見つけることができます。この状況への適用: 蓋と瓶のサイズの 2 つの大きなリストを持つ代わりに、1 つの蓋のサイズといくつかの瓶のサイズがあるとします。ふたが合う瓶は簡単にわかりますよね？1 つのふたの問題を解決するという考え方は、基本的に、大きな問題 (複数のふた) を小さな問題 (1 つのふた) に分割することです。それが理解できたら、アルゴリズムに進むことができます。
アルゴリズムを作成するために、再帰を使用する可能性があります。基本ケースから始めて、最も単純で意味のある問題を解決します (1 ふたの例が気に入っています)。その問題を解決できたら、すべてのふたについて同じ問題を再帰的に解決できますか? 学習体験を台無しにしたくないので、コードを添付しません (これは明らかに宿題です)。
「分割統治」の要点は、作業を複数の小さな問題に分割することです。次に、小さな問題を解決し、ソリューションに結合されるまでそれらをロールアップします。これは、再帰的な解決策を意味します。
再帰関数では、常に「基本ケース」が必要です。これは簡単に解決できる簡単なケースです。たとえば、瓶が 1 つと蓋が 1 つしかない場合は、瓶が蓋と一致することを返すだけです。(問題文の一部として、各瓶に常に 1 つの一致する蓋があるためです。)
したがって、開始する場所の 1 つは、長さ 1 の jar/lid のリストに対してのみ正しく機能する簡単なプログラムです。次に、より多くの機械を追加して、より能力を高めます。
クイックソートでは、数値を分割する場所 (「ピボット」) を選択してから、非常に大まかな並べ替えを行います (ピボットの左側にあるはずの右側にある数値を取り出して左に移動し、およびその逆）。次に、サブリストで再帰的にクイックソートを呼び出します。最終的に、クイックソートへの再帰呼び出しのそれぞれが、基本ケース (長さ 1 のサブリスト) にヒットします。それらがすべて基本ケースにヒットすると、クイックソートが実行されます。(注: クイックソートを最適化し、コードを追加して高速化する方法はありますが、ここではクイックソートの最も単純な実装について説明します。)
この場合、1 から n までの数字だけの長さ n のリストから始めて、正しいリストが得られるまで数字を交換する必要がありますか?
うーん。長さ 2 のリストでは、2 つの可能性しかありません: リストが整列するか、整列しないかです。並んだら完成です。そうでない場合は、数字を入れ替えて並べれば完了です。うーん。これはある意味で並べ替えに似ていますが、並べ替えのように数値を直接比較することはできません。(並べ替えでは、3 つ並べ替えると 5 未満になることが常にわかっていますが、ここではそうではない可能性があります。) そこで、リストを分割する方法を考えて、長さ 2 または長さ 1 のサブリストができるまでそれを続けます。次に、それらの些細なケースを処理します。
楽しい問題のように聞こえます。楽しんで取り組んでいただければ幸いです。