ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Antony Victoroff                     2:5030/953.300 10 Jan 2002  18:30:48
 To : Evgeniy Jirnov
 Subject : Re: Гхм...
 -------------------------------------------------------------------------------- 
 

 
  Ответ на письмо Evgeniy Jirnov к All (Четверг Январь 10 2002 02:23)
 
  EJ> Условие: Есть доски с клетками. Размер досок: 10x15 клеток(к примеру).
  EJ> Hа
  EJ>          досках есть закрашенные и незакрашенные клетки(абсолютно от
  EJ> балды). Из
  EJ>          всех этих досок выбрали одну(назовем "оригинал").
 
  EJ> Задача:  Hайти наиболее похожую по размещению закрашенных и
  EJ> незакрашенных
  EJ>          клеток по отношению к оригиналу доску из всего множества
  EJ> досок.
 
  EJ> Решение: Кто подскажет?
  EJ> P.S. Понятно что надо вычислять какую-то хэш-функцию для каждой доски,
  EJ> а потом сравнивать, но не знаю как ее вычислять...
 
 очень тупой и надежный вариант :
 представляем доску как набор бит (0|1). в твоем случае число - 150 бит.
 степень похожести - расстояние между наборами (досками) по Хэеммингу.
 чем меньше расстояние - тем больше похожи доски.
 расстояние по хэммингу - число несовпадающих бит.
 
 покажу на примере с 3 досками 3*3. (9 бит)
 
 А. 010101110
 B. 011011110
 C. 010011110
 
 A XOR B = 001110000, расстояние = 3
 A XOR C = 000110000, расстояние = 2
 B XOR C = 001000000, расстояние = 1
 
 из этих трех досок наиболее похожи друг на друга - B и C,
 а на доску A наиболее похожа доска C.
 
 вообщем так.
 а чтобы не возиться с битами :) поюзай std::bitset.
 расстояние = (bitset1 ^ bitset2).count();
 
                                                 С уважением, Антон.
                                                        2:5030/3000.
 
 ... [home:latonita@mail.ru] [work:latonita@star.spb.ru] [ICQ#13382973]
 ---
  * Origin: 2:5030/3000 (2:5030/953.300)
 
 

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

Тема:    Автор:    Дата:    Гхм...   Evgeniy Jirnov   10 Jan 2002 03:23:32   Re: Гхм...   Nick Kovaliov   10 Jan 2002 09:48:51   Re: Гхм...   Alexey Danov   10 Jan 2002 09:55:01   Re: Гхм...   Antony Victoroff   10 Jan 2002 17:39:22   Re: Гхм...   Antony Victoroff   10 Jan 2002 18:30:48   Гхм...   Evgeniy Jirnov   13 Jan 2002 04:32:02   Re: Гхм...   Antony Victoroff   14 Jan 2002 16:59:47   Гхм...   Nickita A Startcev   28 Jan 2002 18:36:42