algorithm - 这个算法会终止吗？

Question

集合中有不同的值，这个算法(伪代码)会终止吗？

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

请注意，如果我们位于数组末尾，我假设我们将从头开始。

Answer 1

由于这是伪代码，一个包含 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 )

所以数字会收敛，但它们永远不会相等。

但是，如果您真的在计算机上实现它，由于硬件限制，它们会相等 - 并非所有数字都可以用有限的位数表示。