2

私は私が次のようなものを持っている問題の解決策を見つけようとしています

  1. A> B
  2. B> C
  3. B> D
  4. C> D

そして、私はA> B>C>Dとして答えを得る必要があります。

この問題の条件

  1. 出力にはすべての要素が含まれます。
  2. 問題には偽の入力はありません。たとえば、（A> B）（C> D）は、出力を判別できないため、偽の入力です。
  3. 入力は任意のサイズにすることができますが、偽物になることはなく、問題の解決策は常にあります。

Javaコレクションを使用してこれを最適に解決するための解決策を見つける必要があります。ヒント/ヒントは大歓迎です。

前もって感謝します！

4

4 に答える 4

8

これはトポロジカルソートと呼ばれます。 http://en.wikipedia.org/wiki/Topological_sorting

それを考えると、あなたは自分で宿題を完了することができるはずです。

于 2010-02-11T13:48:37.520 に答える
1

このクラスで最近取り上げたグラフに賭けています...
ここでグラフをどのように適用できると思いますか？
問題の入力（A> B>、A> D、C> Aなど）に基づいて構築される構造を考えられますか？多分ある種の有向グラフ...

問題がそのようなグラフで表現されると、解決策はこのグラフをナビゲートすることを含みます...

于 2010-02-11T13:53:06.783 に答える
0

あなたはそれらをに入れ始めますList。リストはソートされるので、nthペア(a, b)についてはa、二分探索を使用して検索します。すでに存在する場合はスキップし、存在しない場合は適切な位置に挿入します。以来、リストの残りの部分でa > bこれを再度実行します。bこの助けを願っています。

于 2010-02-11T13:54:08.547 に答える
0

これは、入力のMapと、返された List にその回答を追加する再帰メソッドを使用して行うことができます (または、ツリーを下降するときに各ノードを出力するだけです) 。完了時に答えが逆になるのを防ぎます D->C->B->A (または、最後にリストを .reverse() するだけです。) 再帰するときにブレーク条件をテストすることを忘れないでください。(ヒント: キーが見つかりません)

于 2010-02-11T15:24:51.967 に答える