singlepost

Головоломка от braingames.ru (первым решил Александр Щагин) << На главную или назад  

Червяку нужно отправить Письмо Мира птицам, которое состоит из 4 бит данных. Червячиная передача и связь очень ненадежны и любой бит информации (лишь один) может испортиться. Зато размер посылаемого пакета равен 7ми битам.

Как лучше Червяку следует послать данные в пакете, чтобы птицы, зная алгоритм, гарантированно смогли прочитать данные. Хотя возможно один бит (любой) будет поврежден.

118 ответов в теме “Головоломка от braingames.ru (первым решил Александр Щагин)”

  1. 44
    Кирилл Быков ответил:

    Код Хэмиминга, кажися, для этого есть :)

  2. 43
    Сильвестр Сталлоне ответил:

    Да, решение необычное, но, по-моему, верное =) Супер!

  3. 42
    Нгамдкхе Кверос ответил:

    муторно как-то но можно сделать так(надо книжку почитать конечно, слишком криво)

    вобщем идея такая (плюсы все по модулю два)

    п1=д1+д2
    п2=д2+д3
    п3=д3+д4
    п4=д4+д1

    лемма п1+п2+п3+п4=0 (почти очевидно это xor числа со своим циклическим сдвигом)
    так что если ошибка в первой четвёрке, факт ошибки там или её отсутствия в этой части пакета мы установим сразу

    прообраз данных восстанавливается имея, один первый бит данных
    п5=д1;

    п6=п1+п2+п5
    п7=п1+п3+п5

    пусть в первой четвёрке
    - чётное число единичных битов (ошибки нет)
    т.е. п1 п2 п3 п4 – известны достоверно
    — тогда из условия для п6 восстонавливаем п5
    — из условия для п7 восстанавливаем п5
    — берём сам п5, по два из трёх однозначно получаем п5
    —– можно писать ответ
    в первой четвёрке нечётное число единичных битов- ошибка именно здесь
    - достоверно известны п5 п6 п7
    — в уравнения п6 и п7 подставляем данныи и получаем 4 варианта
    —– либо и п6 т п7 верны, тогда ошибка в п4 его инвертируем и пишем ответ
    —– п6 верен п7 нет – ошибка в п3 инвертируем восстанавливаем ответ
    —– п6 неверен п7 верно – ошибка в п2
    —– оба условия для п6 и п7 не выполняются ошибка в п1.

  4. 41
    Сильвестр Сталлоне ответил:

    Надо удалять правильные ответы, чтобы новым было интереснее =)

  5. 40
    Сергей Филимонов ответил:

    "Пацаны, я вас ненавижу" ©
    =)

  6. 39
    Сильвестр Сталлоне ответил:

    Правильно :)

  7. 38
    Сильвестр Сталлоне ответил:

    А вообще, вникать в ваши решения – штука сложная. Давайте договоримся о таких обозначениях:
    П1 П2 П3 П4 П5 П6 П7 – это биты пакета.
    Д1 Д2 Д3 Д4 – это биты данных.

    Соответственно решение #34 (неверное) выглядит примерно так:
    П1 Д1
    П2 Сумма П1 и П3 по модулю 2
    П3 Д2
    П4 Сумма П3 и П5 по модулю 2
    П5 Д3
    П6 Сумма П5 и П7 по модулю 2
    П7 Д4

    Имхо так понятнее получается, нет? :)

  8. 37
    Валерий Тутатчиков ответил:

    например, слово: 1011011
    ошибка в 6 бите, то есть: 1011001
    если в 6, значит неверна сумма 3 и 4 битов исходного сообщения.
    так как сумма 2 и 3 верна (поскольку ошибка возможна только в одном бите), значит 3 бит исходного сообщения (7 в слове) верен, значит ошибка в 6 бите

  9. 36
    Сильвестр Сталлоне ответил:

    Александр, а как правильно? Только не заглядывая в книжку =)

  10. 35
    Валерий Тутатчиков ответил:

    всё, понял свою ошибку )))

  11. 34
    Валерий Тутатчиков ответил:

    запись в строчку: 1 2 3 4 5 6 7
    1, 3, 5, 7 – биты информации
    2, 4, 6 – суммы соседних битов по модулю 2.

    например, имеем сообщение1001
    получаем слово 1100011
    допустим, во время передачи испортился 5 бит: 1100111.
    тогда выписываем сообщение 1 0 1 1,
    считаем суммы по модулю 2 соседних элементов 1 1 0 – они не сходятся с сообщением – определяеи, что ошибка во 2 и 3 сумме, значит ошибочен 3 бит.

  12. 33
    Сильвестр Сталлоне ответил:

    Если ошибка в 6м бите, то как ты определишь, где ошибка, в 6м или в 7м? :)

  13. 32
    Борис Нишлюк ответил:

    Всё, всем спокойной ночи, надеюсь что когда я вернусь решения тут всё ещё не будет :)

  14. 31
    Борис Нишлюк ответил:

    Всё хорошо, люди, думаем дальше. Если ошибка в бите 2 или 3, то система не работает :(

  15. 30
    Сергей Полушкин ответил:

    ну что, есть у кого-нть идеи?

  16. 29
    Борис Нишлюк ответил:

    (решение неверно)

    Иеееес!!! Если я не гоню, то я её решил! Короче заливаю решение:

    Кароче запишем биты в сточку: 1 2 3 4 5 6 7. Первые 4 бита это само слово, а биты 5, 6, 7 – контрольные.
    Изменим бит 5 таким образом, чтобы биты 1, 2, 3, 5 вместе содержали чётное колличество еденичек.
    Изменим бит 6 таким образом, чтобы биты 2, 3, 4, 6 вместе содержали чётное колличество еденичек.
    Изменим бит 7 таким образом, чтобы биты 2, 3, 5, 6, 7 вместе содержали чётное колличество еденичек.

    Всё, теперь допустим это было слово 1001. Соответственно изменяем биты 5, 6, 7 и получаем 1001110. Это слово червячок несёт птицам. Допустим по дороге бит 5 изменился, т.е. он принёс число 1001010. Обратим внимание, что биты 1, 2, 3, 5 содержат нечётное колличество еденичек. Значит один из них ошибочен. Но биты 2, 3, 4, 6 правильны, значит это либо 1 либо 5, ну и 2, 3, 5, 6, 7 также содержат ошибку, значит это 5. Ну и это работает для любой комбинации… походу.
    ЧТД :)

  17. 28
    Борис Нишлюк ответил:

    Чёрт! А раньше сказать не мог?! :)

  18. 27
    Сильвестр Сталлоне ответил:

    Борис, а какое третье значение ты представлял у бита? :) )))

  19. 26
    Сильвестр Сталлоне ответил:

    Денис GooDWiN Гублин, но ведь отправитель не знает, какой номер будет ошибочным. Ошибочным, кстати, может быть как раз один из трех битов для суммы.
    А вообще – алгоритм в студию.

  20. 25
    Борис Нишлюк ответил:

    ну… как обычно нолик либо единичка, но только синенький.

  21. 24
    Сильвестр Сталлоне ответил:

    Ну вот бит и может быть или нулем, или единицей :)

  22. 23
    Борис Нишлюк ответил:

    если он испорчен то он обязательно содержит информацию обратную той которую содержал в начале.

  23. 22
    Сильвестр Сталлоне ответил:

    1) Только 2 значения у бита =)
    2) Всегда приходит 7 бит. Но один из битов может быть неправильным.
    3) Если бит содержит ту информацию, что он содержал в начале, то он уже по факту этого – не испорчен :)

  24. 21
    Денис Гублин ответил:

    суммировать номер ошибочного бита, как раз трех битов хватит

  25. 20
    Сергей Полушкин ответил:

    кажется придумал решение )

  26. 19
    Борис Нишлюк ответил:

    у бита ведь только два значения? :)

  27. 18
    Фархад Муминов ответил:

    вопрос по условию задачи: если бит испорчен, он содержит информацию или нет?

  28. 17
    Антон Кононов ответил:

    про код хемминга в первую очередь думается, когда дублировать каждый бит не получается)))

    зы тоже держусь

  29. 16
    Владимир Щербина ответил:

    а как проверить правильность решения кто-нибудь знает?

  30. 15
    Сильвестр Сталлоне ответил:

    Конечно. Когда ты додумался до решения, это значит, что в случае, если отсутствует любой бит из передаваемых, ты можешь назвать алгоритм, как восстановить этот бит.
    Если на какой-то поломанный бит такого алгоритма не существует – решение неправильное.
    На все существует – правильное :)

  31. 14
    Борис Нишлюк ответил:

    пойду кофе попью. Кому нибудь сделать кофе?

  32. 13
    Сильвестр Сталлоне ответил:

    Сергей, и ты тут :)
    Честно говоря, я не помню код хемминга) до этого дела можно додуматься самому :)

  33. 12
    Борис Нишлюк ответил:

    Конечно можно. Хеминг же додумался как то :)

  34. 11
    Борис Нишлюк ответил:

    да, это именно оно. Но глядеть не честно. Я вон уже минут 40 держусь :)

  35. 10
    Антон Кононов ответил:

    че-та мне подсказывает, что мне надо 1-3 балла решать))

  36. 9
    Сергей Полушкин ответил:

    вроде код Хеминга нужно использовать.
    Шахнов нам это рассказывал. Там как раз на 4 бита полезной информации 3 бита – минимальная контрольная сумма будет для востановления 1 ошибки
    точно алгоритм не помню, но глянуть не проблема
    угадал? )))

  37. 8
    Борис Нишлюк ответил:

    Да я вообще в шоке! …Короче если я долго ничего не напишу щитайте, что я пошёл спать :)

  38. 7
    Сильвестр Сталлоне ответил:

    Ну она на 4ре балла из 5 по мнению braingames. А задача "от Intel 2", по-моему, на 1 или 2 балла. Т.ч. эта чуть посложнее. Но всё равно решаема. И решение красивое :)

  39. 6
    Сильвестр Сталлоне ответил:

    Не сдавайтесь :)

  40. 5
    Борис Нишлюк ответил:

    И я чтото туплю. Удалось вспомнить только, что это возможно, а как именно возможно никаких идей :)

  41. 4
    Владимир Щербина ответил:

    хватит. мне работать надо :)

  42. 3
    Антон Кононов ответил:

    напал тупняк) тоже пойду работать. ща отчет доделаю и подумаю еще

  43. 2
    Борис Нишлюк ответил:

    Это проходят на курсе по булевской алгебре :) Поэтому буду сохранять гордое молчание.

  44. 1
    Сильвестр Сталлоне ответил:

    Постарался изменить текст задачи так, чтобы он совсем не гуглился =) вроде получилось)

Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.