Как проверить, завершена ли программа?

Есть ли общее правило, которое можно использовать для определения этого? Например:Как проверить, завершена ли программа?

int i = 10; 
while (i > 1) { 
    if (i%2 == 0) i = i/2; 
    else i = 3*i - 1; 
}

источник

2010-09-26 fastcodejava

Интересно, что определенная программа _will_ работает навсегда. Поскольку '3i-1' больше, чем' i' для всех 'i> 0', это всегда будет увеличивать значение. И единственный способ получить 0 из операции 'i/2' (для' i> 0') - начать с 'i == 1'. И если 'i == 1', вы не будете _use_' 'i = i/2', так как' i' является нечетным. Гипотеза collatz должна начинаться с 'while (i> 1)', а не 0. – paxdiablo

@paxdiablo Изменено на 'while (i> 1)' – fastcodejava

'i% 2' равно 0, когда' i' равно 1, когда 'i' нечетно, поэтому строка 'i = i/2' будет выполняться только тогда, когда' i' является нечетным. Кроме того, Collatz также известен как проблема 3n * plus * 1. – Olathe

Это halting problem. Не существует алгоритма, способного делать то, что вы просите.

В частности, если бы существовал такой алгоритм, то collatz conjecture, связанный с функцией в вашем вопросе, был бы тривиальным (или, по крайней мере, намного проще).

источник

2010-09-26 06:16:27 aaronasterling

Зачем это произошло? Это потому, что я был немного в руке с моей грамматикой? Я действительно ценю ход с 4787 до 4785. Круглые цифры хороши. – aaronasterling

@UncleO. Заголовок вопроса: «Как проверить, завершен ли алгоритм?». Первое предложение в вопросе: «Существует ли общее правило, которое можно использовать для определения этого?». Это проблема с остановкой. Не позволяйте присутствию конкретного примера путать вас. Также обратите внимание, что OP читает мой ответ, а затем _selected_ он отвечает на вопрос. – aaronasterling

Я думал, что это был хороший ответ, учитывая вопрос. +1 – JoshD

Возможно, вы имеете в виду проблему остановки. Короче говоря, нет общего способа определить, остановится ли программа. Выезд this article.

источник

2010-09-26 06:17:00 JoshD

Зачем это проголосовало? Это потому, что это похоже на ответ Аарона? Мы поставили их в течение нескольких секунд друг от друга! Я бы хотел получить обратную связь ... – JoshD

В общем, «нет». Как и все остальные, с вашим конкретным примером можно доказать, что это не прекращается, так как i будет только меньше, если i является четным (или если i является неположительным и нечетным, но с учетом начальных условий это никогда не произойдет). Наименьшее положительное четное число равно 2, после этого оно будет повернуто на 1 для следующей итерации, где оно будет затем повернуто на 2.

Интересно, что вы не проверяете гипотезу Collatz, поскольку вы повторяете «halve if даже 3 * n-1, если нечетное ", и гипотеза Collatz итерации" уменьшает половину, если четно, 3 * n + 1, если нечетно ". Я не могу найти эту последовательность, обсуждаемую с быстрым поиском.

источник

2010-09-26 08:51:34 Vatine

Как проверить, завершена ли программа?

ответ

Смежные вопросы