Поиск:

Ответ в темуСоздание новой темы Создание опроса
> сравнить два русских слова посимвольно, '>' или '<' 
V
    Опции темы
Frekenbok
Дата 13.1.2007, 13:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 51
Регистрация: 29.10.2006

Репутация: нет
Всего: 1



Привет всем! 
Помогите, плиз, разобраться с условием задачи. Привожу условие дословно:
Сравнить два слова на русском языке, при помощи последовательности сравнений символов, начиная с первого. Формат входного файла следующий: через запятую указываются два слова на русском языке. Выходной файл должен содержать в отдельных строках ответ на каждый входной набор, два входных слова, разделенные знаком "<" или ">".  
Пример:
Входной файл: асса, лига                 Выходной файл: асса > лига
                          фильм, право                                       фильм < право

По какому признаку определяется, какое из слов больше или меньше? Больше то слово, которое первым стоит по алфавиту? Сравниваем первые символы, если равны, сравниваем вторые и т.д., как в словаре?  Верны ли мои рассуждения? Как вы поняли эту задачу.
Кажется, что нечто подобное где-то встречалось, но не могу найти - где.
PM MAIL   Вверх
esperant0
Дата 13.1.2007, 15:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 4
Всего: 14



лексикографический порядок, как в словаре.


--------------------
 
 Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer 

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором  а затем стерто и которое он - пользователь не мог видеть. 
PM MAIL   Вверх
Frekenbok
Дата 15.1.2007, 04:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 51
Регистрация: 29.10.2006

Репутация: нет
Всего: 1



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

{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.

PM MAIL   Вверх
esperant0
Дата 15.1.2007, 08:48 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 714
Регистрация: 20.5.2005

Репутация: 4
Всего: 14



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


--------------------
 
 Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer 

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором  а затем стерто и которое он - пользователь не мог видеть. 
PM MAIL   Вверх
Frekenbok
Дата 15.1.2007, 09:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 51
Регистрация: 29.10.2006

Репутация: нет
Всего: 1



esperant0, спасибо за предложение  smile . Это называется - зачем вообще форумы? Можно книжку почитать. Или форум для продвинутых людей? Таким, как я , здесь делать нечего? (Шутка-правда) Может, хотя бы комментарии прочтешь? Из них вроде бы понятен общий алгоритм, или просто предложи свою схему на словах, без всякого кода  smile 
PM MAIL   Вверх
VaiMR
Дата 15.1.2007, 16:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 67
Регистрация: 25.11.2006

Репутация: нет
Всего: 2



Цитата(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 - сравниваемые символы, из одного массива
                                           иначе, если они из разных алфавитов, утановить, что, например, маленькие символы меньше, чем большие 

А еще лучше будет если удастся создать один массив, вместо двух, тогда будет еще проще(просто не помню можно ли так сделать) 
PM MAIL ICQ   Вверх
Frekenbok
Дата 17.1.2007, 14:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 51
Регистрация: 29.10.2006

Репутация: нет
Всего: 1



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-й вариант)?

PM MAIL   Вверх
VaiMR
Дата 17.1.2007, 16:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 67
Регистрация: 25.11.2006

Репутация: нет
Всего: 2



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

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;

Все это можно оформить в виде маленькой функции, которой передаются строки, и минимальная длина, а возвращает она результат больше, меньше.
PM MAIL ICQ   Вверх
Akina
Дата 17.1.2007, 17:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454



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

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


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
Frekenbok
Дата 6.2.2007, 12:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 51
Регистрация: 29.10.2006

Репутация: нет
Всего: 1



Всем спасибо  smile 
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0708 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.