ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrey Dashkovsky                    2:5002/46.4    02 Sep 2001  00:17:16
 To : Daniel Kamperov
 Subject : Re: Задача
 -------------------------------------------------------------------------------- 
 

 27 Авг 01 21:54, you wrote to Igor V. Rafienko:
 
  DK> В воскресенье, 26 августа 2001 го в 17:11 Igor V. Rafienko писал к
  DK> Daniel Kamperov:
  >>> Задача: активируя различные элементы, привести значения всех
  >>> элементов матрицы к одному числу - 0 или 1. Можно это сделать
  >>> как-то, кроме перебора?
  IR>> Да: можно построить _все_ решения (их, кстати, всего 512. В
  IR>> случае с 4x4, конфигураций -- 65536, а решений -- 4096, поэтому,
  IR>> даже там можно все построить) и проверить принадлежит ли вводная
  IR>> конфигурация множеству решений. Hо опять же, для 3x3 с 2мя
  IR>> значениями _все_ конфигурации можно свести к 0 или 1.
  DK> Хм. А есть ли алгоритм поизящней? Hапример, подходящий для человека?
  DK> (Они все красивые).
 
 Вообщем, если я правильно понял, это то же самое, что и в братьях пилотах с
 открыванием сейфа, могу предложить 2 алгоритма, оба расчитанны на сейф с чётным
 размером.
 
 1. если мы инвертируем все элементы на столбце и на строке, т.е. по кресту, то
 элемент по центру инвертируется, а остальные не изменятся. Этот алгоритм
 придуман мною, и если его использовать на нечётном, то можно наким образом
 использовать его на чётном квадрате, попутно инвертируя эл-ты на последней
 строке и столбце, и после этого если можно собрать инвертируя правый нижний эл-т
 , то решение есть, если нет, то решения нет. Этот вариант не доказан, поэтому
 это только моё предположение.
 2. это известный алгоритм, автора не знаю, причём этот алгоритм только для
 чётной размерности, для нечётной я не пробовал, суть следующая:
 а) запоминаем все эл-ты, которые стоят не так как надо.
 б) инвертируем только эти эл-ты
 в), г), - тоже, что и а), б), т.е. второй приём. За два приёма всё собирается.
 
 Andrey
 
 ... Она крякнула и ножки диван-кровати подломились =( (q) SS
 --- GoldED+/386 1.1.4.7
  * Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
 
 

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

Тема:    Автор:    Дата:    Задача   Daniel Kamperov   24 Aug 2001 20:26:30   Задача   Max Alekseyev   25 Aug 2001 16:43:52   Re: Задача   Igor V. Rafienko   26 Aug 2001 17:11:44   Задача   Daniel Kamperov   27 Aug 2001 22:54:10   Re: Задача   Andrey Dashkovsky   02 Sep 2001 00:17:16   Задача   Vadim Guchenko   26 Aug 2001 19:38:32   Задача   Kluchnikov Eugene   26 Aug 2001 19:17:59   Re: Задача   Igor V. Rafienko   27 Aug 2001 13:51:26   Задача   Kluchnikov Eugene   27 Aug 2001 18:15:49   Задача   Vladimir Namkhoev   27 Aug 2001 20:03:53   Re: Задача   Igor V. Rafienko   28 Aug 2001 05:00:26   Задача   Vladimir Namkhoev   29 Aug 2001 09:57:13   Задача   Vladimir Namkhoev   28 Aug 2001 10:37:31   Задача   Vladimir Namkhoev   28 Aug 2001 11:50:47   Задача   Vladimir Namkhoev   28 Aug 2001 12:50:41   Задача   Igor Popyrko   27 Aug 2001 21:00:00