Список разделов Flyback.org.ru » Мат. каф. » Теория чисел
Тему сейчас просматривают - зарегистрированных: 0, скрытых: 0 и гостей: 0
Зарегестрированные - Нет
тема: Теория чисел
Ответить с цитатой

GluckMaker
 


Возник тут странный прикладной вопрос. Есть чёрный ящик, записывающий состояние некоего объекта в виде последовательности десятичных цифр, причём соседние состояния кодируются сильно непохожими последовательностями. "Состояние" - совокупность чисел, некоторые из которых меняются редко, а другие - намного чаще (как, например, ИНН магазина, номер кассы, дата и сумма в чеке - сумма меняется постоянно у каждого покупателя, номер кассы неизменен в каждой из нескольких касс, а ИНН не меняется никогда). Часть этих чисел известна.
Например, так:
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
Ответить с цитатой

Alexey_F
 


Первая идея: если состояния можно упорядочить (по времени или порядку записи, например), то имеет смысл провести частотный анализ на число совпадений разрядов соседних чисел. (Из поста понятно, что какие-то закономерности уже были найдены, но имеет смысл просто подсчитать именно числа таких совпадений для всех разрядов)

Вопросы общего плана: а что есть этот ящик? Для чего он на самом деле, какие данные в него поступают, когда, как, что за объект? Хотелось бы знать, с чем мы, собственно, работаем - вдруг поможет.

Вторая идея: большая разница соседних состояний наводит на грустную мысль о хеш-функции, но это тогда вообще тупиковый вариант.

Добавлено: Wed Mar 31, 2010 10:49 pm
Ответить с цитатой

Wat.
 


GluckMaker смех Я тя прекрассно понимаю. Ещё в школе, в 9 ом классе страдал этой вещью. Несколько месяцев провёл за компом составляя огромные таблици в экселе и строча алгоритм в бейсике. Изучал этот вопрос с разных сторон, составлял и моделировал на компе, проверяя свои теории. Пытался создать подобный генератор чисел. Спустя какое-то время завилась девушка, и интерес к "разгрызанию" числового гранита угас. Потом забросил и не возвращался к этому. Может гдето на дискетах остался ещё наработанный материал, если я их найду. не знаю хотел както вернутся к этой теме, но боюсь какбы не пришлось начинать с нуля.

ЗЫ: Кались смех чё ломонуть решил? Карточки? телефон? инет? или чё поинтерессней смех мнмн гнев
если чё, пиши в ЛС

Добавлено: Thu Apr 01, 2010 1:03 am
Список разделов Flyback.org.ru » Мат. каф. » Теория чисел
    Просмотр темы целиком



Лицензионное соглашение

(c)Flyback.org.ru
Российское общество любителей высоких напряжений.
Использование материалов с данного сайта и форума возможно только с разрешения администрации.