Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > сравнить два русских слова посимвольно


Автор: Frekenbok 13.1.2007, 13:47
Привет всем! 
Помогите, плиз, разобраться с условием задачи. Привожу условие дословно:
Сравнить два слова на русском языке, при помощи последовательности сравнений символов, начиная с первого. Формат входного файла следующий: через запятую указываются два слова на русском языке. Выходной файл должен содержать в отдельных строках ответ на каждый входной набор, два входных слова, разделенные знаком "<" или ">".  
Пример:
Входной файл: асса, лига                 Выходной файл: асса > лига
                          фильм, право                                       фильм < право
По какому признаку определяется, какое из слов больше или меньше? Больше то слово, которое первым стоит по алфавиту? Сравниваем первые символы, если равны, сравниваем вторые и т.д., как в словаре?  Верны ли мои рассуждения? Как вы поняли эту задачу.
Кажется, что нечто подобное где-то встречалось, но не могу найти - где.

Автор: esperant0 13.1.2007, 15:20
лексикографический порядок, как в словаре.

Автор: Frekenbok 15.1.2007, 04:55
Вот представляю на ваш суд наброски паскалевского кода. Думаю, что можно как-то оптимизировать. Какие будут предложения?
Код

{sravnenie dvuh russkih slov posimvol'no }
program rus_slova;
uses crt;
var
  s, w1, w2: string; {s - строка из файла ,w1 - первое слово,w2-второе слово}
  i, j, len: integer; {len - длина самого короткого слова из двух (в одной строке)}
        f,g: text;

{---------------сравнение символов с индексом i------------------}
function comp(w1,w2:string; i: integer): integer;
 begin
   if ord(w1[i])<ord(w2[i]) then comp:=1 {если код ASCII первого символа меньше, то он первый по алф.}
    else
     if ord(w1[i])>ord(w2[i]) then comp:=2 {если код ASCII второго символа меньше, то он первый по алф.}
      else comp:=0; {иначе равны}
 end;

begin
 clrscr;
 assign(f,'slova.txt');
 reset(f);
 assign(g,'compare.txt');
 rewrite(g);
 while not eof(f) do
   begin
     readln(f,s);  
{-------разделяем строку на 2 слова-------------}
     i:=pos(',',s);
     if i=0 then
       begin
         writeln('V stroke "',s,'" net zapyatoi!');
       end
     else
       begin
         w1:=copy(s,1,i-1);
         w2:=copy(s,i+1, length(s));
         if length(w1)>length(w2) then len:=length(w2) {находим длину короткого слова}
           else len:=length(w1);
{----------сравниваем посимвольно--------------}
         i:=1;
         repeat
           case comp(w1,w2,i) of
             0: i:=i+1; { переходим к след. символу}
             1: begin   { символ из первого слова первый по алф.}
                    writeln(g,w1,'>',w2);
                     break; {выходим из цикла сравнения символов}
                end;
             2: begin  { символ из второго слова первый по алф.}
                     writeln(g,w1,'<',w2);
                      break;
                end;
             end;
         until (i>len);  
         if (i>len) then  {если все проверенные символы равны}
          begin
           if length(w1)=length(w2) then writeln(g,w1,'=',w2)  { если длины слов равны, то слова одинаковые}
            else
              if length(w1)>length(w2) then writeln(g,w1,'<',w2) {первым по алф. стоит слово, которое короче}
               else writeln(g,w1,'>',w2);
         end;
      end;
   end;  writeln('Sravnenie vypolneno!');
 readkey;
 close(f);
 close(g);
end.

Автор: esperant0 15.1.2007, 08:48
Предложение - почитать книгу по оптимизации и с оптимизировать. "Я к сожалению не компайлер и код не компилирую" ;(

Автор: Frekenbok 15.1.2007, 09:20
esperant0, спасибо за предложение  smile . Это называется - зачем вообще форумы? Можно книжку почитать. Или форум для продвинутых людей? Таким, как я , здесь делать нечего? (Шутка-правда) Может, хотя бы комментарии прочтешь? Из них вроде бы понятен общий алгоритм, или просто предложи свою схему на словах, без всякого кода  smile 

Автор: VaiMR 15.1.2007, 16:56
Цитата(esperant0 @ 13.1.2007,  15:20)
лексикографический порядок, как в словаре.

А мне всегда казалось, что символы сравниваются по ASCII коду, и тогда латинские символы будут упорядочены в лексикографическом порядке, так как они общие для всех кодовых страниц (находятся в первых 128 кодах), а вот с кириллицей не так. Например, в кодовой странице 866 - DOS А(128) - Я(159), а(160) - п(175), р(224) - я(239), Ё(240), ё(241). Поэтому так работать трудновато, хотя возможно.

Мое предложение работать так: 
Создать массивы: 
на паскале от 'а'..'я', и 'А'..'Я'
типа byte и заполнить их по порядку числами 1,2,3,4,5,6

затем просто сравнивать: m1[ch1]<m1[ch2], где ch1 и ch2 - сравниваемые символы, из одного массива
                                           m2[ch1]<m2[ch2], где ch1 и ch2 - сравниваемые символы, из одного массива
                                           иначе, если они из разных алфавитов, утановить, что, например, маленькие символы меньше, чем большие 

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

Автор: Frekenbok 17.1.2007, 14:53
VaiMR, что-то мне твой алгоритм не очень понятен. Получается, букве 'а' в массиве соответствует цифра 1, 'б' - цифра 2 и т.д. А как с ними работать? Вот есть у меня слова 'асса' и 'лига'. Как мне их сопоставить? По твоей записи получается, что m1['а'] должно быть меньше  m1['л']? Это как? Или ты под ch1 и ch2 подразумеваешь их ASCII-коды? Тогда они больше размерности массива. В общем, в любом случае нам придется обращаться к кодам символов. Тогда зачем выделять целый массив (33 или 66 байтов!), если можно и так сравнить символы ord[ch1]<ord[ch2] (для паскаля)? Ведь старшей букве в алфавите соответствует больший код ASCII. Исключение - буква ё, но ее в ДОСе я даже ввести не могу с клавиатуры, хотя предусмотреть, конечно, можно. Обрати внимание, что в задаче 'асса'>'лига', хотя код['а']<код['л']. Т.е. здесь получается порядок, обратный ASCII-кодам. Если ты все-таки считаешь свой алгоритм приемлемым, приведи хотя бы кусочек кода. Как ты перебираешь символы? Как определяешь, какой из них больше?
Здесь от перебора символов никуда не денешься. Единственное, что, как мне кажется, можно оптимизировать, - это сравнение равных или частично равных слов, например, 'кот' и 'кот' или 'ром' и 'рома'. Но может, мне просто так кажется?
Точно! Вот что значит - выразить свою мысль!! Сначала, до посимвольной проверки, можно определить, какое из слов короче, и попробовать определить, является ли оно подстрокой длинного слова. Например, так:
Код

len1, len2: integer;
len1:=length(w1);
len2:=length(w2);
if( len1=len2) and (pos(w1,w2)=1) then writeln(g,w1,'=',w2) {слова равны}
  else
     if (len1>len2) and (pos(w2,w1)=1) then writeln(g,w1,'<',w2) {короткое слово стоит первым}
       else 
           if (len2>len1) and (pos(w1,w2)=1) then writeln(g,w1,'>',w2)
              else ... {сравниваем посимвольно}

Жуткое получилось ветвление. Но вот вопрос: что выполнится быстрее - сначала перебор символов (1-й вариант, см. верхний код) или сначала ветвление (2-й вариант)?

Автор: VaiMR 17.1.2007, 16:45
Извини, невнимательно прочитал задание - нумерация в массиве должна быть обратной.
Код

len1, len2,i: integer;    
len1:=length(w1);    
len2:=length(w2);

if len1<len2
 then
  begin
   for i:=1 to len1 do
    if m1[w1[i]]>m1[w2[i]]
     then
      {первое слово больше второго, запоминаем результат, выходим}
     else
      if m1[w1[i]]<m1[w2[i]]
       then
        {второе слово больше первого, запоминаем результат, выходим};
   {Если еще не вышли,то первые len1 символов слов совпадают - и второе слово больше - у него больше символов}
  end
 else
  begin
   for i:=1 to len2 do
    if m1[w1[i]]>m1[w2[i]]
     then
      {первое слово больше второго, запоминаем результат, выходим}
     else
      if m1[w1[i]]<m1[w2[i]]
       then
        {второе слово больше первого, запоминаем результат, выходим};
    {Если еще не вышли,то первые len2 символов слов совпадают - и первое слово больше - у него больше символов}
  end;

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

Автор: Akina 17.1.2007, 17:18
Цитата(Frekenbok @  13.1.2007,  14:47 Найти цитируемый пост)
Пример:
Входной файл: асса, лига              Выходной файл: асса > лига
              фильм, право                           фильм < право

Если бы было наоборот - асса < лига и фильм > право - я бы тоже склонялся к теории лексикографического порядка, т.е. если символ дальше от начала алфавита, то он больше. Но в такой постановке, как указано в инит-посте, я даже не знаю что и думать...

Автор: Frekenbok 6.2.2007, 12:59
Всем спасибо  smile 

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)