3

最近、私はインタビューに出席し、理解できない次の質問に出くわしました.

質問1：

私が読んだ証拠によると、カメは1ステップ移動し、ウサギは一度に2ステップ移動します。私はこれを理解し、うさぎは亀の2倍の速度で動くので、ある時点で会うでしょう。2 と 3 または 3 と 5 または 2 と 4 のようなランダムな値を持つことはできません。カメとウサギの値を選択するための条件は何ですか? ランダムな値を選択できますか?

質問2：

カメとウサギがループに入る条件はありますか? カメとウサギの値がそれぞれ 2 と 4 であるとします。そして、リンクされたリストは次のようになります

            3   
          /   \
    1 -  2     4
          \   /
            5

Tortoise がノード 3 でループに入り、Hare がノード 2 でループに入ると、ループ内で両者が出会うことはありません。では、カメとノウサギがループに入る条件はありますか?

それらが互いに出会うように選択されるべき限定された値はありますか?

4

3 に答える 3

2

カメは番号が付けられたポイントから開始し、Tステップ S tを実行し、ウサギHはステップ S hから開始してステップを実行します。

それらが満たされるための必要十分条件は、

|T - H| = k X gcd (S t , S h )

つまり、開始位置の差は、ステップの倍数でなければなりませんgcd。

于 2016-02-03T08:39:24.547 に答える
1

任意の長さのサイクルをキャッチするには、2 つの移動速度が比較的素数である必要があります。十分条件だと思います。

于 2016-02-03T08:03:43.633 に答える