Re: Найти решение

From

Sergey Politov (2:5015/176.18)

To

"fat"

Date

2002-05-11T05:09:19Z

Area

RU.ALGORITHMS

//Привет fat, // может обсудим *"Найти решение"*?

 U> Матрица 3x3 --> 0    0    1 0    0    0 0    0    0
 U> Цель: алгоритм при котором все элементы либо 0 либо 1. Правила воздействия
 U> на элементы: инверсия (i,j) элемента, при этом инвертируются элементы с
 U> расстоянием 1 от инвертируемого и инвертируемый элемент (i,j). Пример:
 U> 1)инвертируем (1,1) инвертируются (1,2),  (2,1) и (1,1)         2)
 U> инвертируем (2,2) инвертируются (1,2), (2,1), (2,3), (3,2), (2,2).
Задача перевести произвольную матрицу 3x3 в (0,0,1;0,0,0;0,0,0)?
Если да то вот решение.
Я надесь что тебе очевидно, что порядок инверсий не влият на результат,
а потому более одного раза ничего инвертировать нет смысла.
Вообще для матрицы 3x3 сойдет и перебор, но можно и за полином, правда в
этом случае от тормознее.
Так вот за полином делается так:
для каждого элемета мы знаем должен он быть проинвертирован, или нет(в 
зависимости от его начального значения), и какие инверсии на него влияют.
Поэтому можно составить систему над полем Z_{2}, неизвесные отвечают на
вопрос надо инвертировать соответствующий элемент, или нет.
Пример для матрицы (1,1,0;1,0,1;0,1,1)
Система:
для 11 - {1=x11+x12    +x21
для 12 - {1=x11+x12+x13    +x22
для 13 - {1=    x12+x13        +x23
для 21 - {1=x11+       +x21+x22    +x31
для 22 - {0=    x12    +x21+x22+x23    +x32
для 23 - {1=        x13    +x22+x23        +x33
для 31 - {0=           +x21        +x31+x32
для 32 - {1=               +x22    +x31+x32+x33
для 33 - {1=                   +x23    +x32+x33
Решая систему имеем: x=(0,0,1,1,0,0,0,1,0).

np: Iced Earth - When the Night Falls
Искренне Ваш
            Sergey Politov

--- WP/95 Rus 1.78 Релиз 1  Reg.
 * Origin: Человек - побочный продукт любви. (2:5015/176.18)