На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Поиск Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Задачка
fenix710
Сообщ. #1 ,
    Full Member
    ***
    Профиль · PM
    Рейтинг (т): 0
    задача:
    На заре развития радио была разработка сигналов для общния между радиолюбителями всего мира. эта система был ???а придумана американским художником Морзе. с развитием вычислительной техники эту систему попытались применить для приема/передачи компьютерной информации. вот что из этого получилось: точка представлена сигналом 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
    albom
    Сообщ. #2 ,
      Senior Member
      ****
      Профиль · PM
      Поощрения: 2 Dgm
      Рейтинг (т): 20
      В коде Морзе есть еще один важный параметр - пауза между закодированными символами. Так как здесь идет сплошной поток данных без пауз, а коды Морзы не являются префиксными, то одназначно определить закончилась декодирование очередного символа, или нет, нельзя.
      Например, 011000 можно декодировать как АБ, ВС, ЕМЕИ.
      UnFleshed_One
      Сообщ. #3 ,

        Full Member
        ***
        Профиль · PM
        Рейтинг (т): 6
        Можно так: парсим с начала строки. Подходят только две буквы: К и Ц. Отрезаем их от основной строки, получаем:
        0100000001000 11000 101110110 10101010000011001001 (К)
        и
        100000001000 11000 101110110 10101010000011001001 (Ц)
        Теперь парсим уже ее.

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

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

        Или тебе ее решить нужно?
        UnFleshed_One
        Сообщ. #4 ,

          Full Member
          ***
          Профиль · PM
          Рейтинг (т): 6
          PS
          При чем здесь Морзе? Он бы в гробу перевереулся :)
          zx1024
          Сообщ. #5 ,
            Junior
            *
            Профиль · PM
            Рейтинг (т): 0
            Нельзя. Код должен быть префиксным. Посмотреть хотя бы на 11000. То ли "7", то ли "ГЕЕ", то ли "ЧЕ", то ли "ТТС" и т.д. Вот если только использовать лексический, синтаксический и семантический анализы полученных предложений. Но это слишком накладно по времени.
            zx1024
            Сообщ. #6 ,
              Junior
              *
              Профиль · PM
              Рейтинг (т): 0
              А чего это народу так много на форуме?(это, конечно, хорошо) Пока свой ответ писал уже трое ответили (только не надо про тормоза).
              albom
              Сообщ. #7 ,
                Senior Member
                ****
                Профиль · PM
                Поощрения: 2 Dgm
                Рейтинг (т): 20
                Наверно, народ только и ждет, что бы кому-нибудь ответить. :)
                Только я не понял, к кому обращен 3-ий пост? Причем здесь гроб?
                Сообщение отредактировано: albom -
                zx1024
                Сообщ. #8 ,
                  Junior
                  *
                  Профиль · PM
                  Рейтинг (т): 0
                  >UnFleshed_One.
                  >Можно так: парсим с начала строки. Подходят только две буквы: К и Ц.
                  А как же "Н" и "Н"?
                  UnFleshed_One
                  Сообщ. #9 ,

                    Full Member
                    ***
                    Профиль · PM
                    Рейтинг (т): 6
                    > Только я не понял, к кому обращен 3-ой пост? Причем здесь гроб?

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

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

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

                    Это если речь идет о той единственной строке.
                    Сообщение отредактировано: UnFleshed_One -
                    UnFleshed_One
                    Сообщ. #10 ,

                      Full Member
                      ***
                      Профиль · PM
                      Рейтинг (т): 6
                      > А как же "Н" и "Н"?

                      Просто третий вариант.
                      zx1024
                      Сообщ. #11 ,
                        Junior
                        *
                        Профиль · PM
                        Рейтинг (т): 0
                        UnFleshed_One
                        Не спорю. Число вариантов в любом случае будет конечно. Но научить программу выбрать единственно верный будет ой как сложно.
                        А если она будет находить 0.000000001\% всех предложений (у которых всего 1 вариант), то на кой она нужна.
                        UnFleshed_One
                        Сообщ. #12 ,

                          Full Member
                          ***
                          Профиль · PM
                          Рейтинг (т): 6
                          > А если она будет находить 0.000000001\% всех предложений (у которых всего 1 вариант), то на кой она нужна.

                          Я полагаю расшифровать нужно только одну строку :)
                          1010100000001000 11000 101110110 10101010000011001001
                          albom
                          Сообщ. #13 ,
                            Senior Member
                            ****
                            Профиль · PM
                            Поощрения: 2 Dgm
                            Рейтинг (т): 20
                            Взял я вот эту строчку 10101000000010001100010111011010101010000011001001. И за пять минут нашел, что ей соответствует более 4 миллионов вариантов. И как из них выбрать нужный?
                            zx1024
                            Сообщ. #14 ,
                              Junior
                              *
                              Профиль · PM
                              Рейтинг (т): 0
                              Я считаю так. Программно можно найти все слова (это, как правильно заметил UnFleshed_One, классическая рекурсия). Исключить из всего этого текст совсем несуразный (напр., подряд "ЦЦ", "ЫЫ" и т.д.). А дальше человек сам быстрее найдёт связный текст, чем человечество создаст искуственный интеллект. А напрямую решить задачу (для произвольного кода) нельзя.
                              UnFleshed_One
                              Сообщ. #15 ,

                                Full Member
                                ***
                                Профиль · PM
                                Рейтинг (т): 6
                                Вручную? Они все ровно укладываются? А те у которых хвосты (типа 1) остаются отбросил?
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (2) [1] 2  все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0460 ]   [ 15 queries used ]   [ Generated: 1.09.24, 00:31 GMT ]  
                                Powered by Invision Power Board(U) v1.2 © 2003  IPS, Inc.