> ЗЫ А чем тебе мой алгоритм проверки повторяемости не > подошел(в этой нитке я его написал) ? - когда запоминаем > первое состояние и каждый раз прокручиваем эволюцию до > состояния текущее - 1 и сверяемся с ними ? Долго, что-ли ? > Так можно не проверять на каждом N-ом шаге все N-1 > состояний, а, как тут уже предлагали, хранить типа > CRC[1]..CRC[N-1] и только в том случае, если совпали CRCN > и, скажем, CRC[J], прокрутить до J-го состояния(получить > его еще раз) и сравнить. Да, пока что кардинально другого варианта не нашлось. Еще подожду и если не будет других вариантов реализую этот.
Прием вариантов - до последнего сообщения в нитке :)
P.S. Экономнее будет при совпадении CRC[J] и CRC[N] запомнить массив и подождать N-J шагов и сравнить, так как повторная прокрутка может занять много времени; а также хранить не все CRC а лишь последние (н.р. 100 последних)
Но для такого варианта будет медленно работать вот такой случай: массив практически полностью состоит из устойчивых конфигураций(они не меняются) и в нем есть достаточно свободного пространства, в котором находится планер-каждые 4 хода планер сдвигается на одну клетку по диагонали, все остальное неизменно=> CRC повторяется каждые 4 хода=> каждые 4 хода будет сравниватся массив, а до периодичности еще может быть очень много ходов(не раньше, чем планер долетит до устойчивых конфигураций).
Как с этим бороться, пока не знаю. Может хранить CRC отдельно четных, отдельно нечетных строк, и может аналогично для столбцов? или даже CRC всего, CRC каждой второй, каждой третьей, пятой, седьмой,.. строки/столбца, сколько именно-экспериментально узнать.
Какие есть соображения по этой проблеме?
|