Не верю, что эта задача нерешаема

Sharp
Даю подобную задачку, есть 2 разных серийника.

в первой строке идут 2 первых буквы серийника и чексумма
во 2ой строке продолжение и чексумма.

Код (Text):

1. S30700F0F8 FE 4541 8C
2. S31300F0F9 00 36303034393737 00 462E25480000B1
3.                 это серийник    
4. S30700F0F8 FE 4546 87
5. S31300F0F9 00 36303133373039 00 7A127A1700007C
6.                 это серийник

Теперь собственно вопрос найти алгоритм подщета чексуммы.
Если нужны еще примеры могу выложить хоть 10ток.

 

Низнаю низнаю, для кого простой, а для кого нет. Вы же сами запутались толи 8й толи 1й бит? Пересобирание байтов не встречал ниразу в протоколах.

+1
Сорец в студию!

 

Номер бита, который нужно выкидывать, становится очевидным, если сравнить первый и третий пакеты.
PaCHER: если алгоритм содержит одну или две простых операции по преобразованию данных, как в обсуждаемой задаче, можно попробовать.
im1111: Я точно указал, какой бит является контролем четности. Взгляните на коды Хэмминга, там используется тот же подход — вставка битов для детектирования и исправления ошибок.

Вас интересует авторское решение? Вот оно:

Код (Text):

1. function bin2word($b, $off){
2.     return intval(substr($b, $off, 8), 2) + (intval(substr($b, $off+8, 8), 2) << 8);
3. }
4.  
5. function parse($src){
6.     $res = "";
7.     if(substr($src, 0, 5) == "4D 53"){
8.         foreach(explode(" ", substr($src, 6)) as $byte){
9.             $byte = base_convert($byte, 16, 2);
10.             if(substr_count($byte, "1") % 2 == 0){
11.                 $res .= strval(sprintf("%07s", substr($byte, 0, -1)));
12.             } else return false;
13.         }
14.     } else return false;
15.     return $res;
16. }
17.  
18. $src = file_get_contents("input.txt");
19. if(($res = parse($src)) !== false){
20.     $sw = array_fill(0, bin2word($res, 0) + 1, false);
21.     $lsw = bin2word($res, 16);
22.     for($i = 0; $i < $lsw; $i++){
23.         $sw[bin2word($res, $i*16 + 32)] = true;
24.     }
25.     file_put_contents("output.txt", substr(implode(" ", array_keys($sw, false)), 2));
26. } else file_put_contents("output.txt", "ERROR");

Громадное, правда? К слову, только 1/5 решений была меньше.

 

Только здесь сложность растет экспоненциально от размера программы. Сможете перебрать все программы на перле из 26 строчек?

 

Sharp

Щяс сам пробую но кажется что это опять для экстрасенсов.

 

halyavin, вы пишете программы, перебирая их? СзМ

 

Вы задачу определения протокола решаете сразу написанием правильной программы? Мне кажется нормальному человеку понятно, что я говорил о задаче восстановления протокола, а не о реализации стандартного алгоритма.

 

Пожалуйста, расскажите Ваши рассуждения поподробнее, почему так?

Мои рассуждения такие - в пакете поменялись данные (в данном случае один бит - но это всего лишь случайность, могло поменяться и больше бит) и так, как есть сигнал об ошибке, то в пакете существует где-то контрольная сумма. А возможно, контрольной суммы и нет, а ошибка определяется по "неправильности" данных в пакете.

 

не партесь, не то что заждача не имеет решения просто в ней не хватает логики, когда занимался задачами(их решением) так из книги по олимпиадным задачам нашел 6 задач которые вообще не решаються лишь потому что не хватает условий, все банально просто. И ещё ни когда не смотрите на примеры, парой автор збивает этим при решении задачи.

 

В попытках найти эту контрольную сумму вы и придете к выводу, что контрольная сумма — ничто иное, как этот самый бит.

 

05 81 00 60 00 09 00 05 00 03 00 00

В пакете :
00000101 10000001 00000000 01100000 00000000 00001001 00000000 00000101 00000000 00000011 00000000 00000000

прогон через ваш алгоритм :
0000010 1000000 0000000 0110000 0000000 0000100 0000000 0000010 0000000 0000001 0000000 0000000

Выход:
00000101 00000000 00000011 00000000 00000001 00000000 00000010 00000000 00000100 00000000 0000

В HEXe :
05 00 03 00 01 00 02 00 04 00

Какаято охинея - тоже самое получалось при переводе в восьмеричную систему (см выше) Объясните...

а где 900 свичей ?

----
Вопрос снимается ... всё встает на свои места после фразы : "Вопрос для олимпиады"... Пакеты не имеет смысл расматривать как часть рабочего протокола ( добавивив ещё с 2-3 и можно запутаться окончательно =), а как просто набор данных связанных одной закономерностью =) (Читать такие задачи на трезвую голову надо)

P.S.
Понял свою ошибку =)

P.P.S.
Задача былабы более понятна еслибы автор сделалбы какойнибудь намек на выше сказанное, например либо в пакеты добавил какойнить "номер подсети" или чтонить из раздела древьев =) вобщем наверное что-то что дало бы повод не искать чёрную кошку в тёмной комнате , особенно в той где её нет =)

 

Действительно, искать в этой задаче черных кошек очень опасно, т.к. пока не словишь ее за хвост, будешь уверен, что уже схватил. Нумерология — опаснейшее занятие.

 

Я просил написать Ваши конкретные рассуждения по указанию того, что биты - это контрольная сумма. А Вы пишете "если бы, да кабы...". Опять у Вас присутствует слово "ДОГАДАТЬСЯ". Извините, но ЕСЛИ это задача на ЛОГИКУ, то всяких догагадок и гаданий быть не должно. Все решение должно сводиться к виду "если-то..., так как х=у, то...". И никаких "может быть... а вдруг..."

Цетральным решением в данной задаче является высказывание "предположим, что старшие биты являются контрольной суммой...". Вы уже собрали статистику, насклько данное высказывание может встретиться, при решении Вашей задачи. Как вы убедились, вероятность этого предположения пракитически стремиться к нулю

 

Sharp
Какая, простите, "НУМЕРОЛОГИЯ" ?

 

Это не тест на владение азами логики, а задача. В задачах обязательно надо до чего-то догадываться, перебирать возможные варианты и проверять их. Логи аськи с объяснением одного из возможных путей решения http://ifolder.ru/3070641
Нумерология, применительно к математике — поиск все большего числа все более сложных «закономерностей» в каких-то числах вместо поиска общего закона, ими управляющего. Занятие ею часто встречается среди специалистов по теории чисел.