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 )

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

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

Answer 2

这取决于。

如果您的元素具有离散值，那么它们很可能会在几次运行后落入相同的值。

如果您的元素具有有限的精度值（例如浮点数或双精度值），则需要更长的时间，但时间有限。

如果您的元素具有任意精度值，那么您的算法可能永远不会完成。（如果你把积分的每一部分都数出来，然后把它加到一张纸上的一个数字上，你需要无限的时间，无限大的纸，以及对这个类比的无限耐心。）

您的代码与以下代码几乎没有区别：

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

它会终止吗？这真的取决于实施。