ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergey Politov                       2:5015/176.18  11 May 2002  05:09:19
 To : "fat"
 Subject : Re: Hайти решение
 -------------------------------------------------------------------------------- 
 

 
  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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Hайти решение   fat   10 May 2002 02:49:51   Re: Hайти решение   Sergey Politov   11 May 2002 05:09:19