Возник тут странный прикладной вопрос. Есть чёрный ящик, записывающий состояние некоего объекта в виде последовательности десятичных цифр, причём соседние состояния кодируются сильно непохожими последовательностями. "Состояние" - совокупность чисел, некоторые из которых меняются редко, а другие - намного чаще (как, например, ИНН магазина, номер кассы, дата и сумма в чеке - сумма меняется постоянно у каждого покупателя, номер кассы неизменен в каждой из нескольких касс, а ИНН не меняется никогда). Часть этих чисел известна. Например, так: 1) 51712255207416526376788821 2) 23719759483907506185871421 Или так: 1) 79990475822431435621158520 2) 17188392912903800040690442 При этом 13 цифра слева равномерно распределена в диапазоне 0..3, а если она равна 3 - 14 цифра ограничена 8. Есть также мнение, что, если эти цифры приняли значения 3 и 8, то 11 цифра ограничена 6. Это наводит на мысль о том, что состояние "собирается" в 85-битное число (2^85=38685626227668133590597632), причём старший бит зависит от наиболее динамично меняющейся части состояния, после чего число преобразуется в десятичную форму, и цифры перемешиваются заданным образом. Задача - найти эту перестановку. Я пробовал переставлять цифры парами, исходя из того, что 13 и 14 стоят рядом - получающиеся двоичные числа для двух соседних состояний минимально отличаются 18-19 битами (ожидаемое различие - несколько бит, в пределе - единственный бит). Причём этот минимум достигается на многих разных перестановках, не обязательно совпадающих для разных пар состояний. По-моему, это говорит о том, что, с одной стороны, гипотеза об именно таком способе кодирования верна, а с другой - переставляются не пары, а отдельные цифры. Но перебрать 12! вариантов за приемлемое время можно, а 23! или 24! - уже не получится. Возникает вопрос, как можно сократить переборное поле? Можно ли воспользоваться какой-то информацией, полученной из перестановки пар цифр? Ещё, по-моему, можно как-то воспользоваться тем, что старшие десятичные разряды не влияют на младшие двоичные: 1 = 0x01 100 = 0x64 10000 = 0x 2710 1000000 = 0xF 4240 100000000 = 0x5F5 E100 10000000000 = 0x2 540B E400 1000000000000 = 0xE8 D4A5 1000 100000000000000 = 0x5AF3 107A 4000 10000000000000000 = 0x23 86F2 6FC1 0000 1000000000000000000 = 0xDE0 B6B3 A764 0000 100000000000000000000 = 0x5 6bc7 5e2d 6310 0000 10000000000000000000000 = 0x21e 19e0 c9ba b240 0000 1000000000000000000000000 = 0xd3c2 1bce cced a100 0000 100000000000000000000000000 =0x52 b7d2 dcc8 0cd2 e400 0000 Но пока не соображу никак, каким образом... Any ideas? Добавлено: Tue Jan 26, 2010 8:33 pm |
Первая идея: если состояния можно упорядочить (по времени или порядку записи, например), то имеет смысл провести частотный анализ на число совпадений разрядов соседних чисел. (Из поста понятно, что какие-то закономерности уже были найдены, но имеет смысл просто подсчитать именно числа таких совпадений для всех разрядов) Вопросы общего плана: а что есть этот ящик? Для чего он на самом деле, какие данные в него поступают, когда, как, что за объект? Хотелось бы знать, с чем мы, собственно, работаем - вдруг поможет. Вторая идея: большая разница соседних состояний наводит на грустную мысль о хеш-функции, но это тогда вообще тупиковый вариант. Добавлено: Wed Mar 31, 2010 10:49 pm |
GluckMaker Я тя прекрассно понимаю. Ещё в школе, в 9 ом классе страдал этой вещью. Несколько месяцев провёл за компом составляя огромные таблици в экселе и строча алгоритм в бейсике. Изучал этот вопрос с разных сторон, составлял и моделировал на компе, проверяя свои теории. Пытался создать подобный генератор чисел. Спустя какое-то время завилась девушка, и интерес к "разгрызанию" числового гранита угас. Потом забросил и не возвращался к этому. Может гдето на дискетах остался ещё наработанный материал, если я их найду. хотел както вернутся к этой теме, но боюсь какбы не пришлось начинать с нуля. ЗЫ: Кались чё ломонуть решил? Карточки? телефон? инет? или чё поинтерессней если чё, пиши в ЛС Добавлено: Thu Apr 01, 2010 1:03 am |
Лицензионное соглашение (c)Flyback.org.ru Российское общество любителей высоких напряжений. Использование материалов с данного сайта и форума возможно только с разрешения администрации. |