K
Цикл может далеко не с первого состояния начаться
Внимательно - стартовое состояние перезаписывается
Size: a a a
2020 October 03
@N
Внимательно - стартовое состояние перезаписывается
Условия, что обязательно приходим в стартовое — не было
A
Это норм, если цикл длины не больше S -- мы же на каждой итерации сравниваем
K
Условия, что обязательно приходим в стартовое — не было
Стартовое - не совсем стартовое, оно каждые s+1 шаг пересчитывается
@N
Стартовое - не совсем стартовое, оно каждые s+1 шаг пересчитывается
А, ну если так сформулировать, то да
K
Можно от ограничения на s избавиться, время от времени его увеличивая
@N
Можно от ограничения на s избавиться, время от времени его увеличивая
Можно просто с двумя поинтерами бегать, один ходит на 1 шаг вперёд, другой на 2. Расстояние между ними каждый раз увеличивается на 1
K
Более хуже
@N
Более хуже
Если же бегаем по нодам в памяти (которые поинтеры куда-то), а не по айдишникам состояний, то можно воспользоваться хаком, что память, выделенная из кучи, выровнена так, чтобы корректно ссылаться даблы: таким образом, последние 3 бита нулевые и их можно использовать как флаги
@N
Тогда вообще найдем первое же зацикливание
m
Можно просто с двумя поинтерами бегать, один ходит на 1 шаг вперёд, другой на 2. Расстояние между ними каждый раз увеличивается на 1
Такие алгоритмы в этой задаче приводят к тому что нужно хранить все промежуточные состояния, потому что откатить программу к предыдущему состоянию и сделать переход сложно.
A
не, два поинтера это тут два экземпляра состояний. Просто придется дважды делать вычисления
A
то есть есть цикл вида
while some_condition(state):
state = iterate(state)
A
вместо этого мы храним state1 и state2
A
while some_condition(state1):
state1 = iterate(state1)
if some_condition(state1):
break
state2 = iterate(state2)
state1 = iterate(state1)
if state1 == state2:
print("Got loop")
break
A
на каждой итерации цикла state1 продвигается вперед дважды (и на каждом продвижении может выйти с окончанием цикла), а state2 однократно. Получается, что для "нормального" случая у нас в 1.5 раз больше вычислений
m
не, два поинтера это тут два экземпляра состояний. Просто придется дважды делать вычисления
Вопрос в том можно ли сохранить все состояние или у нас есть только хеш через который
iterate не реализовать. Если говорить о программе на нативном языке, у нее полный стейт - это вся память и регистры. Технически их можно и сохранить и восстановить, но это сложно и дорого.A
ну это если у нас есть разные сайдэффекты
A
если же у нас вычисление можно локализовать, то и решить таким образом тоже можно
A
речь в этом случае не о полном стейте, а об условном состоянии некоторого автомата, из которого можно вычислить без сайдэффектов следующее состояние