Как в игре «Жизнь» определить предыдущее состояние клеток по текущему? (Одномерное поле)?

Собственно, вопрос следующий: Как по текущему состоянию клеток в игре "Жизнь", определить состояние 1 ход назад?

Правила поведения клеток:
1) Если у клетки 2 живых соседа, то она умирает
2) Если нет живых соседей, то умирает
3) Если есть один живой сосед, то клетка становится живой
4) В иных ситуациях состояние клетки не изменяется

Ход проходит одновременно для всех клеток. То есть состояние всех клеток учитывается по текущему ходу.

Поле, на котором находятся клетки, это одномерный массив.

Допустим текущее состояние: 0 1 1 0, тогда предыдущее будет 1 0 0 1.

Выход за пределы массива, это мертвый сосед.

Подскажите, пожалуйста, алгоритм определения предыдущего состояния поля?
  • Вопрос задан
  • 3838 просмотров
Решения вопроса 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Обозначим текущее состояние как C[1..N], предыдущее как P[1..N], С[0] = P[0] = C[N+1] = P[N+1] = 0 - клетки за пределами поля.
На текущем шаге клетка жива тогда и только тогда, когда на предыдущем шаге у неё был ровно один сосед, то есть C[i] = P[i-1] xor P[i+1] => P[i+1] = C[i] xor P[i-1].
1. P[0] = 0, C[1] известна => P[2] = P[0] xor C[1]. Теперь, зная P[2] можно найти P[4] = P[2] xor C[3] или в общем случае:
для i от 1 до N с шагом 2
    P[i+1] = P[i-1] xor C[i];
Получили все предыдущие значения чётных ячеек.

2a. Для чётных N обратным ходом можно восстановить нечётные ячейки:
для i от N до 1 с шагом -2
    P[i-1] = P[i+1] xor C[i];

2b. Для нечётных N однозначного решения нет. В зависимости от значения P[1] будет получен один из двух вариантов решения:
P[1] = 0; // или 1
для i от 2 до N с шагом 2
    P[i+1] = P[i-1] xor C[i];
Ответ написан
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Верно так:
// Инициализируем C, надо заменить на ввод исходных данных
$C = array(1, 1, 1, 0, 0, 1, 1, 1, 0, 1);
$N = count($C);

// Добавляем в начало и конец нули
array_unshift($C, 0);
$C[] = 0;

// Создаём массив P, заполняем 0 и N+1 элементы нулями
$P[0] = 0;
$P[$N+1] = 0;

// Заполняем чётные ячейки
for ($i = 1; $i <= $N; $i += 2)
    $P[$i+1] = $P[$i-1] ^ $C[$i];

// Заполняем нечётные ячейки
if (($N&1) == 0) {
    // Вариант с чётным количеством ячеек
    for ($i = $N; $i >= 1; $i -= 2)
        $P[$i-1] = $P[$i+1] ^ $C[$i];
} else {
    // Вариант с нечётным количеством ячеек
    $P[1] = 0;
    for ($i = 1; $i <= $N; $i -= 2)
        $P[$i-1] = $P[$i+1] ^ $C[$i];
}

// Выводим результат
for ($i = 1; $i <= $N; $i++)
    print $P[$i];

Получаем 0110100111.
Проверяем, (0110100111) даёт по правилам (1110011101)
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
@GDApsy
программирование на python;linux
Так по-моему никак, можно только с определенной вероятностью предложить варианты какая конфигурация поля привела к текущему состоянию поля, но без памяти детерминированный ответ по-моему дать невозможно.
Ответ написан
Комментировать
opium
@opium
Просто люблю качественно работать
никак нельзя определить
можно найти одно из состояний из которого можно перейти в текущее
Ответ написан
Комментировать
Beholder
@Beholder
Нельзя. Более того, в игре с классическими правилами существуют конфигурации, которые никак нельзя получить ни из каких предыдущих конфигураций (так называемые "сады Эдема").
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
09 нояб. 2024, в 15:14
15000 руб./за проект
09 нояб. 2024, в 14:13
15000 руб./за проект