Прекратится ли этот алгоритм?

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;

Это когда-нибудь прекратится? Это действительно зависит от реализации.