这个算法会终止吗？

Question

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

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

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

- Franz

---

nextElement() 是做什么的？allElements() 集合是常量吗？ - Roy Dictus

你是如何计算 average(allElements) 的？ - Fahim Parkar

显然，如果所有元素相等，则它不会终止。 - Michael Foukarakis

我认为你想要在循环中使用 curElement = nextElement() [打字错误？]，否则 - 答案是微不足道的：如果你只进入循环一次 - 你会立即退出，因为 currElement 被定义为平均值。 - amit

@amit：不，nextElement()会将curElement指向下一个元素。 - Franz

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 )

所以这些数字收敛，但永远不会相等。

然而，如果你在计算机上实现它，由于硬件限制，它们将变得相等 - 并非所有数字都能用有限数量的位表示。

- Luchian Grigore

---

存在任意精度实数的实现，这将允许实现永远运行。 - user684934

@bdares 我怀疑这一点。它们仍然将数字存储在内存中，无论有多大，它都不是无限的。 - Luchian Grigore

@LuchianGrigore：你可以将数字存储在磁盘/远程集群中，并在需要时进行扩展。从理论上讲，是可以实现的。 - amit

嗯...说得好。@amit 任何现实生活中的存储都是有限的，所以他的论点仍然成立。 - user684934

我想这归结于我们是否考虑在理论机器上运行的理论程序（例如图灵机，具有无限内存），还是在现实机器上运行的真实程序。现实机器有其自身的限制。 - user684934

Answer 2

这要看情况。

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

如果您的元素保存的是有限精度值（例如浮点数或双精度浮点数），那么需要更长的时间，但仍然是有限的。

如果您的元素保存的是任意精度值，那么您的算法可能永远无法完成。（如果您将整数的每一部分加起来并将其添加到纸上的数字中，则需要无限的时间、无限大的纸张和对这个类比的无限耐心。）

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

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

它是否会终止？这主要取决于实现方式。

- user684934