5

.NET の C++ でこのアルゴリズムを見つけようとしていますが、できません。次のアルゴリズムを見つけました。

// Best solution
function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

しかし、正しくないように思われますか、それとも間違っていますか? 最後にウサギがカメと出会うことを実際にどのように証明できますか? それがどのように正確に機能し、どのように機能するかについての説明を事前に感謝しますproof

編集済み

この解決策について、通常のアルゴリズムでは高速反復子を 1 つしか使用しないことがわかりましたが、ここでは 2 つを使用します。なぜですか?

4

3 に答える 3

3

あなたが見つけたコードのアイデアはうまくいくようです。便宜上、2 つの高速反復子が使用されます (ただし、ループの条件に多くの「アクション」を入れるなど、この種の「便利さ」はwhile避けるべきです)。1 つの変数を使用して、より読みやすい方法で書き直すことができます。

while (fastNode && fastNode.next()) {
    if (fastNode.next() == slowNode || fastNode.next().next() == slowNode) {
        return true;
    }
    fastNode = fastNode.next().next();
    slowNode = slowNode.next();
}
于 2010-10-07T10:42:41.983 に答える
2

アルゴリズムは正しいです。証拠：

サイクルがない場合は自明です: うさぎはリストの最後を見つけます。

それで、サイクルがあり、うさぎがそこに入り、狂ったように走り回ります。最終的に、カメはサイクルの最初のノードに到達します。この時点から、両方とも必然的にサイクルにとどまります。あるノードから次のノードに移動する唯一の方法は、最終的にサイクルの最初のノードに戻ることです。(自分を納得させるために、リスト/グラフの絵を描いてください。)

うさぎは動きが速いので、やがて亀に追いつきます。サイクルの長さとそれに入る前に通過したノードの数 (奇数か偶数かが重要なので、4 つのケースがあります) に応じて、これは奇数または偶数のステップの後に発生する可能性があります。そのため、ウサギは現在のノードと次のノードの両方でカメの存在を確認する必要があります。(コード例では、これを実現するために 2 つのポインターを使用していますが、実際には必要ありません)。

より正式な証明については、このウィキペディアのページをご覧ください。

于 2010-10-07T10:45:54.350 に答える
0

このアルゴリズムは、リンクされたリストでサイクルを見つけます。
代わりに 1 つの高速ノードを使用できます。

 function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode = startNode;
  while (slowNode && fastNode = fastNode.next() && fastNode = fastNode.next()){
    if (slowNode == fastNode) return true;
    slowNode = slowNode.next();
  }
  return false;
}
于 2010-10-07T10:41:05.557 に答える