algorithm - このアルゴリズムは終了しますか?

Question

コレクション内の値が異なる場合、このアルゴリズム (疑似コード) は終了しますか?

while (curElement != average(allElements))
{
    curElement = average(allElements);
    nextElement();
}

配列の最後にいる場合は、最初からやり直すと想定していることに注意してください。

score 5 · Accepted Answer

これは擬似コードであるため、2つの要素を含む簡単な例から、プログラムが終了しない場合があることがわかります。

x = 0, y = 1;

          x     y
Step 1:   0.5   1
Step 2:   0.5   0.75
Step 3:   0.635 0.75
//and so one

いくつかの数学が含まれていると、lim(x-y) = lim( 1 / 2^n )

したがって、数値は収束しますが、等しくなることはありません。

ただし、これを実際にコンピューターに実装すると、ハードウェアの制限のために同じになります。すべての数値を限られたビット数で表現できるわけではありません。

score 2 · Accepted Answer

場合によります。

要素が離散値を保持している場合、数回の実行後に同じ値に分類される可能性があります。

要素が制限された精度値（floatやdoubleなど）を保持している場合、時間がかかりますが、時間は有限です。

要素が任意の精度の値を保持している場合、アルゴリズムが終了しない可能性があります。（積分のすべての部分を数え、それを一枚の紙にある図に追加する場合、無限の時間、無限に大きな紙、そしてこのアナロジーに対する無限の忍耐が必要です。）

コードと以下のコードにはほとんど違いがありません。

var i = 1;
while (i != 0) 
    i = i / 2;

終了することはありますか？それは本当に実装に依存します。

2 に答える 2