Задачка

задача:
На заре развития радио была разработка сигналов для общния между радиолюбителями всего мира. эта система был ???а придумана американским художником Морзе. с развитием вычислительной техники эту систему попытались применить для приема/передачи компьютерной информации. вот что из этого получилось: точка представлена сигналом 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 - 05.09.03, 19:41

>UnFleshed_One.
>Можно так: парсим с начала строки. Подходят только две буквы: К и Ц.
А как же "Н" и "Н"?

> Только я не понял, к кому обращен 3-ой пост? Причем здесь гроб?

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

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

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

Это если речь идет о той единственной строке.

Сообщение отредактировано: UnFleshed_One - 05.09.03, 19:53

> А как же "Н" и "Н"?

Просто третий вариант.

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

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

Я полагаю расшифровать нужно только одну строку
1010100000001000 11000 101110110 10101010000011001001

Взял я вот эту строчку 10101000000010001100010111011010101010000011001001. И за пять минут нашел, что ей соответствует более 4 миллионов вариантов. И как из них выбрать нужный?

Я считаю так. Программно можно найти все слова (это, как правильно заметил UnFleshed_One, классическая рекурсия). Исключить из всего этого текст совсем несуразный (напр., подряд "ЦЦ", "ЫЫ" и т.д.). А дальше человек сам быстрее найдёт связный текст, чем человечество создаст искуственный интеллект. А напрямую решить задачу (для произвольного кода) нельзя.

Вручную? Они все ровно укладываются? А те у которых хвосты (типа 1) остаются отбросил?

Цитата UnFleshed_One, 06.09.03, 00:15:13

Вручную? Они все ровно укладываются? А те у которых хвосты (типа 1) остаются отбросил?

Зачем вручную? Написал программу, перебирает ~250000 комбинаций/сек. Все строчки укладываются ровно. Хвостов нигде нет.

Не должно, задачи так не ставятся, где-то должна быть наё@ка. :

Неужели все пять миллионов заканчиваются на А и У? (мне самому лень писать ).

Значит так. Программа перебрала меньше 0.1\% (примерно, конечно), а уже нашла 30 миллионов вариантов! И все они подходят под исходную строку!
Даже если предположить, что исходная строка

Цитата

1010100000001000 11000 101110110 10101010000011001001

, а не

Цитата

10101000000010001100010111011010101010000011001001

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

На всякий случай вот эта программа (FreePascal):

const ss:ansistring='А - 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,';
//ss -  эта наша таблица кодировки
 
const //t='1010100000001000 11000 101110110 10101010000011001001';
           t='10101000000010001100010111011010101010000011001001';
 
// t - строчка для разбора
var s,q:array[1..50]of ansistring; // буквы и и их коды соответственно
    k,l,h:integer;  // k - число кодовых символов
    f:ansistring;   // времменая строка
    r:string;        //результат
    z:Longint;
 
///// самая главная функция
///// декодирует строчку t начиная с позиции i (учитывает пробелы)
procedure decode(i:integer);
 var x:integer;
     zzz:boolean;
 begin
 if i=length(t)+1 then // Все? Строчка закончилать?
  begin          
  inc (z);
  if z and 63=0 then
   writeln(z,' ',r);
  exit;
  end;
 
 zzz:=false;
 for x:=1 to k do                      //Поиск следующего кода
  if copy(t,i,length(q[x]))=q[x] then
   begin
   r:=r+s[x];
   decode(i+length(q[x]));
   r:=copy(r,1,length(r)-1);
   zzz:=true;
   end;
 
 if (not zzz)and(t[i]=' ') then decode(i+1);    //обработка случая с пробелом в строке t
 end;
 
 
begin
//начало
k:=0;
f:=ss;
 
// парсинг строки ss; заполнение массивов q и s
repeat
l:=pos(',',f);
if l=0 then
 break;
inc(k);
h:=pos(' ',f);
s[k]:=copy(f,1,h-1);
delete(f,1,h+2);
l:=pos(',',f);
q[k]:=copy(f,1,l-1);
delete(f,1,l+1);
until length(f)=0;
 
//Просто посмотрим, правильно ли сработал разбор строки ss
for l:=1 to k do
 writeln(s[l],'      ',q[l]);
 
r:='';  // результата еще нет
z:=0; // найдено 0 решений
decode(1); // начинаем поиск с первого символа
 
end.

Сообщение отредактировано: albom - 05.09.03, 20:57

А можно немного комментариев, давно паскаль не видел...

Вот fenix710 офигеет, когда с утра увидит столько "ответоов".
И не старайтесь. Полного решения (программы) всё равно (за одну ночь) не напишите.
Т.к. решения в чистом виде просто не существует. albom, ты же сам в своём первом сообщении писал, что это невозможно.

А можно немного комментариев, давно паскаль не видел...

Добавил коментарии, должно хватить....

Цитата zx1024, 06.09.03, 00:51:53

Вот fenix710 офигеет, когда с утра увидит столько "ответоов".
И не старайтесь. Полного решения (программы) всё равно (за одну ночь) не напишите.
Т.к. решения в чистом виде просто не существует. albom, ты же сам в своём первом сообщении писал, что это невозможно.

А мы еще анализатор какой-нибудь попробуем к проге прикрутить. Вдруг поможет.  ;)

Да, неслабо... Действительно вариантов море. Все дело в 'T' которая там каждой бочке затычка... (предлагаю ее отбросить )

#include "stdafx.h"<br>#include <string><br>#include <stdio.h><br>#include <fstream><br><br>using namespace std;<br>ofstream of;<br><br>string letters[][2]=<br>{<br>      "A","01","Б","1000","В","011","Г","110","Д","100","Е","0","Ж","0001","З","1100",<br>      "И","00","Й","0111","К","101","Л","0100","М","11","Н","10","О","111","П","0110",<br>      "Р","010","С","000","Т","1","У","001","Ф","0010","Х","0000","Ц","1010","Ч","1110",<br>      "Ш","1111","Щ","1101","Ь","1001","Ы","1011","Э","00100","Ю","0011","Я","0101",<br>      "1","01111","2","00111","3","00011","4","00001","5","00000","6","10000","7","11000",<br>      "8","11100","9","11110","0","111111"," ","01000" <br>};<br><br>void<br>find(string s,string decoded)<br>{<br>      for(int i=0;i<42;i++) // checking every letter<br>      {<br>            for(int j=0;j<letters[i][1].length();j++)<br>            {<br>                  if(s[j]!=letters[i][1][j])break;<br>            }<br>            if(j==letters[i][1].length()) // if all bytes matching<br>            {<br>                  decoded+=letters[i][0];      // found one letter<br>                  string str=s.substr(j,-1);    // cut it<br>                  if(str=="")<br>                  {<br>                        of<<decoded.c_str()<<"\n"; // finish<br>                        continue;<br>                  }<br>                  else<br>                        find(str,decoded); // next letter<br>            }<br>      }<br>}<br><br>int <br>main(int argc, char* argv[])<br>{<br>      string s("10101000000010001100010111011010101010000011001001");<br>      of.open("res.txt");<br><br>      find(s,"");<br>      return 0;<br>}

Сообщение отредактировано: UnFleshed_One - 05.09.03, 21:56

Цитата fenix710, 05.09.03, 21:54:33

задача:
На заре развития радио была разработка сигналов для общния между радиолюбителями всего мира. эта система был ???а придумана американским художником Морзе. с развитием вычислительной техники эту систему попытались применить для приема/передачи компьютерной информации. вот что из этого получилось: точка представлена сигналом 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

Плохая таблица
Наилучший вариант представления символов в Unicode.

Столько ответов и все к одному ---) НЕльзя

!) Во-первых кто сказал что цц не могут идти подряд ?????
 
  может быть передается закодированоое сообщение и там и цц и юю

2) код не только не префексный  но и не постфиксный ведь тогда можно было бы раскадировать с  конца

3) если мне память не изменяет то это известная проблема соответствий Поста
которая в общем случае не решаема

Цитата fenix710, 05.09.03, 21:54:33

задача:
На заре развития радио была разработка сигналов для общния между радиолюбителями всего мира. эта система был ???а придумана американским художником Морзе. с развитием вычислительной техники эту систему попытались применить для приема/передачи компьютерной информации. вот что из этого получилось: точка представлена сигналом 0, тире - сигналом 1...

Данное описание кода Морзе не полное и использоваться для кодирования чего либо не может. Код Морзе основан на длительностях сигналов.
Есть минимальная длительность сигнала (импульса).
Длительность точки равна минимальной длительности.
Длительность импульса тире равна трем минимальным длительностям.
Пауза между импульсами кода одного символа равна минимальной длительности.
Пауза между символами равна тройной минимальной длительности.
Пауза между словами равна пяти минимальным длительностям.

Заменив только точку нулем, а тире единицей, теряется более половины информации.

Для передачи цифровой информации есть более эффективные и помехозащищенные методы кодирования (и модуляции) , манчестерский код, манчестерский-2, с востановлением нуля/единици, ...  Совместно с контролем четности/нечетности, контрольной суммой, мажоритарным контролем, контролем по модулю 2, кодами обнаружения и воссановления ошибок (коды Хемминга).

Сообщение отредактировано: m - 07.09.03, 14:56

Цитата albom, 06.09.03, 00:11:10

Взял я вот эту строчку 10101000000010001100010111011010101010000011001001. И за пять минут нашел, что ей соответствует более 4 миллионов вариантов. И как из них выбрать нужный?

ответ единственный:
КА5ЕА3ЕЕААГГКАА5ГАЕА

Цитата

ответ единственный:
КА5ЕА3ЕЕААГГКАА5ГАЕА

И как же ты нашел этот ответ???

Ммм да, не на ту кнопочку нажимал.
Если пробелы считать разделителями, имеется 48 498 610 288 128 вариантов.

А вот программка

<br>decode([],[]).<br>decode(Str,[X|Xs]):- cod(X,Xc), append(Xc,Rest,Str), decode(Rest,Xs).<br><br>cod('А', "01").<br>cod('Б', "1000").<br>cod('В', "011").<br>ну и т д.<br>

> ответ единственный:
КА5ЕА3ЕЕААГГКАА5ГАЕА

А моя мне сотни мегабайт ответов выдает...

А на чем программка?

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

Цитата wormball, 08.09.03, 18:06:24

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

да!
а если сообщение закодировано???

то какие частоты считать???

тогда лучше сразу повеситься

Цитата UnFleshed_One, 08.09.03, 17:49:17

> ответ единственный:
КА5ЕА3ЕЕААГГКАА5ГАЕА

А моя мне сотни мегабайт ответов выдает...

А на чем программка?

Все ответы ни на один винт не поместятся.
Программка на прологе. Там после получения ответа надо на ';' нажимать, чтобы следующий получить а я на enter - вот и облажался.

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