1

そのため、ペアを介して完全なパスを形成するために一緒に接続できる場合とできない場合がある一連のペアがあるプログラムに行き詰まっています。ペアの 2 番目のアイテムが別のペアの最初のアイテムと一致するかどうかを、ペアがなくなるまでチェックできるようにする必要があります。たとえば、私のペアは次のようになります。

(1,5)
(2,4)
(3,2)
(5,3)
(4,3)

何らかの方法でペアを反復処理し、ペアの 2 桁目が次のペアの 1 桁目に一致するかどうかに基づいて、それぞれを通過する完全なパスを取得できるかどうかを確認できる必要があります。この例では、出力は

(1,5)、(5,3)、(3,2)、(2,4)、(4,3) となり

、完全に一致します。一致が形成されない場合は、失敗を報告する必要があります。入力はテキスト ファイルに基づいています。これまでのところ、Streamreader でファイルを読み取り、改行に基づいてペアを分割し、カンマに基づいて各ペアを反復して項目に分割することができました。進め方についてはほとんど無知です。誰かアイデアがあれば、よろしくお願いします。

StreamReader sr = new StreamReader("inputs.txt");
string line = null;
line = sr.ReadToEnd();
var str = line.Trim().Split('\n');
int length = str.Length;
int index=1;

while (index < length)
{
    var pair = str[index].Split(',');
    var item1 = pair[0];
    var item2 = pair[1];
}
4

3 に答える 3

2

あなたが説明した問題は、別の形式に変換できます。グラフ。_

あなたが与えた例のように見えます。

あなたの例を表す有向グラフ

(1,5) などのペアがあったので、1 から 5 への矢印を描きました。

このようなグラフ上のパスは、矢印の方向にのみ進むことができます。

あなたが知りたいのは、「このグラフには、すべてのペアを使用する、つまりすべてのエッジを通過するパスがありますか?」ということです。

このようなパスは、オイラー有向パスとして知られています。

ウィキペディアには、そのようなパスを見つけるための 2 つのアルゴリズム、Fleury と Hierholzer がリストされており、どちらも 1800 年代後半に発見されました。これにより、この問題を解決するためにどこから始めればよいかがわかると思います。

于 2013-04-05T09:35:41.973 に答える