На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Задачка
    задача:
    На заре развития радио была разработка сигналов для общния между радиолюбителями всего мира. эта система был ???а придумана американским художником Морзе. с развитием вычислительной техники эту систему попытались применить для приема/передачи компьютерной информации. вот что из этого получилось: точка представлена сигналом 0, тире - сигналом 1.
    получена последовательность сигналов:
    1010100000001000 11000 101110110 10101010000011001001
    можнл ли, используя нижеуказанную таблицу, расшифровать полуенный код, и что из этого выйдет.
    А - 01, Б - 1000, В - 011, Г - 110, Д - 100, Е - 0, Ж - 0001, З -1100, И - 00, Й - 0111, К - 101, Л - 0100, М - 11, Н - 10, О - 111, П - 0110, Р - 010, С - 000, Т - 1, У - 001, Ф - 0010, Х - 0000, Ц - 1010, Ч - 1110, Ш - 1111, Щ - 1101, Ь - 1001, Ы - 1011, Э - 00100, Ю - 0011, Я - 0101, 1 - 01111, 2 - 00111, 3 - 00011, 4 - 00001, 5 - 00000, 6 - 10000, 7 - 11000, 8 - 11100, 9 - 11110, 0 - 111111, разделитель - 01000
      В коде Морзе есть еще один важный параметр - пауза между закодированными символами. Так как здесь идет сплошной поток данных без пауз, а коды Морзы не являются префиксными, то одназначно определить закончилась декодирование очередного символа, или нет, нельзя.
      Например, 011000 можно декодировать как АБ, ВС, ЕМЕИ.
        Можно так: парсим с начала строки. Подходят только две буквы: К и Ц. Отрезаем их от основной строки, получаем:
        0100000001000 11000 101110110 10101010000011001001 (К)
        и
        100000001000 11000 101110110 10101010000011001001 (Ц)
        Теперь парсим уже ее.

        Классическая рекурсия.

        Если в конце концов все буквы уложатся ровно единственным образом -- то да, можно расшифровать (эту) строку. Если не уложатся -- нельзя. Если вариантов несколько -- пишем еще и спеллчекер :).

        Или тебе ее решить нужно?
          PS
          При чем здесь Морзе? Он бы в гробу перевереулся :)
            Нельзя. Код должен быть префиксным. Посмотреть хотя бы на 11000. То ли "7", то ли "ГЕЕ", то ли "ЧЕ", то ли "ТТС" и т.д. Вот если только использовать лексический, синтаксический и семантический анализы полученных предложений. Но это слишком накладно по времени.
              А чего это народу так много на форуме?(это, конечно, хорошо) Пока свой ответ писал уже трое ответили (только не надо про тормоза).
                Наверно, народ только и ждет, что бы кому-нибудь ответить. :)
                Только я не понял, к кому обращен 3-ий пост? Причем здесь гроб?
                Сообщение отредактировано: albom -
                  >UnFleshed_One.
                  >Можно так: парсим с начала строки. Подходят только две буквы: К и Ц.
                  А как же "Н" и "Н"?
                    > Только я не понял, к кому обращен 3-ой пост? Причем здесь гроб?

                    Притом что Морзе придумал не криптоалгоритм, а средство связи :). А составители задачи как обычно объем текста набирали :).

                    > Нельзя. Код должен быть префиксным. Посмотреть хотя бы на 11000. То ли "7", то ли "ГЕЕ", то ли "ЧЕ", то ли "ТТС" и т.д. Вот если только использовать лексический, синтаксический и семантический анализы полученных предложений. Но это слишком накладно по времени.

                    Необязательно нельзя. Есть шанс, что цепочка замыкается малым числом вариантов. А применение психлогического анализа (составителей) позволяет предположить что число вариантов очень даже конечно. (Чуть ли не 1).

                    Это если речь идет о той единственной строке.
                    Сообщение отредактировано: UnFleshed_One -
                      > А как же "Н" и "Н"?

                      Просто третий вариант.
                        UnFleshed_One
                        Не спорю. Число вариантов в любом случае будет конечно. Но научить программу выбрать единственно верный будет ой как сложно.
                        А если она будет находить 0.000000001\% всех предложений (у которых всего 1 вариант), то на кой она нужна.
                          > А если она будет находить 0.000000001\% всех предложений (у которых всего 1 вариант), то на кой она нужна.

                          Я полагаю расшифровать нужно только одну строку :)
                          1010100000001000 11000 101110110 10101010000011001001
                            Взял я вот эту строчку 10101000000010001100010111011010101010000011001001. И за пять минут нашел, что ей соответствует более 4 миллионов вариантов. И как из них выбрать нужный?
                              Я считаю так. Программно можно найти все слова (это, как правильно заметил UnFleshed_One, классическая рекурсия). Исключить из всего этого текст совсем несуразный (напр., подряд "ЦЦ", "ЫЫ" и т.д.). А дальше человек сам быстрее найдёт связный текст, чем человечество создаст искуственный интеллект. А напрямую решить задачу (для произвольного кода) нельзя.
                                Вручную? Они все ровно укладываются? А те у которых хвосты (типа 1) остаются отбросил?
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0348 ]   [ 15 queries used ]   [ Generated: 21.05.24, 08:08 GMT ]