2

次のようなシーケンスがあると仮定します：0、1、2、3、4、5、6、7、0、1、2など。基本的にN個の数字で構成され、何度も繰り返されるシーケンス。

このシーケンスの2つの数値間の距離/差を見つけるための最も簡単なアルゴリズムは何ですか？たとえば、距離from 5 to 7 is +2と距離from 0 to 6 is -2。より高レベルのビューについては、ループ/繰り返しシーケンス番号が何であるかを確認し、最も近いパス（それらの間の最小番号）上の番号の「前」または「後」を調べる必要があります。

4

2 に答える 2

4

X> Yと仮定すると：

dist(X, Y) = min { X-Y, N-(X-Y-1) }

N = 7の例：

dist（7、5）= min {7-5、7-（7-5-1）} = min {2、6} = 2

dist（6、0）= min {6-0、7-（6-0-1）} = min {6、2} = 2

dist（5、1）= min {5-1、7-（5-1-1）} = min {4、4} = 4

最後の例は、距離定義の小さな欠陥を示しています。dist（5、1）= 4またはdist（5、1）= -4ですか？負の距離を避けるために、定義を少し変更しました（したがって、私のアルゴリズムは距離の絶対値を計算します）。定義を維持したい場合は、の最初の引数がmin2番目の引数より大きい場合にのみ、距離を負にします。

于 2012-09-01T19:46:21.017 に答える
-1

これは非常に単純で、連続した番号と連続していない番号で機能します。おそらく拡張メソッドにします。

[TestFixture]
public class NumbersFixture
{
    [Test]
    public void FindDistance()
    {
        var numbers = new List<int> { 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2 };

        var num1 = 6;
        var num2 = 0;

        var from = numbers.IndexOf(num1);
        var indexFound = numbers.FindIndex(from, f => f == num2);
        var distance = from - indexFound;

        var result = string.Format("{0}", distance);
        Console.WriteLine(result);
    }
}
于 2012-09-01T20:04:03.783 に答える