![]() |
|
![]() ![]() ![]() |
|
Frekenbok |
|
|||
![]() Шустрый ![]() Профиль Группа: Участник Сообщений: 51 Регистрация: 29.10.2006 Репутация: нет Всего: 1 |
Привет всем!
Помогите, плиз, разобраться с условием задачи. Привожу условие дословно: Сравнить два слова на русском языке, при помощи последовательности сравнений символов, начиная с первого. Формат входного файла следующий: через запятую указываются два слова на русском языке. Выходной файл должен содержать в отдельных строках ответ на каждый входной набор, два входных слова, разделенные знаком "<" или ">". Пример: Входной файл: асса, лига Выходной файл: асса > лига фильм, право фильм < право По какому признаку определяется, какое из слов больше или меньше? Больше то слово, которое первым стоит по алфавиту? Сравниваем первые символы, если равны, сравниваем вторые и т.д., как в словаре? Верны ли мои рассуждения? Как вы поняли эту задачу. Кажется, что нечто подобное где-то встречалось, но не могу найти - где. |
|||
|
||||
esperant0 |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 714 Регистрация: 20.5.2005 Репутация: 4 Всего: 14 |
лексикографический порядок, как в словаре.
-------------------- Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть. |
|||
|
||||
Frekenbok |
|
|||
![]() Шустрый ![]() Профиль Группа: Участник Сообщений: 51 Регистрация: 29.10.2006 Репутация: нет Всего: 1 |
Вот представляю на ваш суд наброски паскалевского кода. Думаю, что можно как-то оптимизировать. Какие будут предложения?
|
|||
|
||||
esperant0 |
|
|||
![]() Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 714 Регистрация: 20.5.2005 Репутация: 4 Всего: 14 |
Предложение - почитать книгу по оптимизации и с оптимизировать. "Я к сожалению не компайлер и код не компилирую" ;(
-------------------- Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть. |
|||
|
||||
Frekenbok |
|
|||
![]() Шустрый ![]() Профиль Группа: Участник Сообщений: 51 Регистрация: 29.10.2006 Репутация: нет Всего: 1 |
esperant0, спасибо за предложение
![]() ![]() |
|||
|
||||
VaiMR |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 67 Регистрация: 25.11.2006 Репутация: нет Всего: 2 |
А мне всегда казалось, что символы сравниваются по 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 |
|
|||
![]() Шустрый ![]() Профиль Группа: Участник Сообщений: 51 Регистрация: 29.10.2006 Репутация: нет Всего: 1 |
VaiMR, что-то мне твой алгоритм не очень понятен. Получается, букве 'а' в массиве соответствует цифра 1, 'б' - цифра 2 и т.д. А как с ними работать? Вот есть у меня слова 'асса' и 'лига'. Как мне их сопоставить? По твоей записи получается, что m1['а'] должно быть меньше m1['л']? Это как? Или ты под ch1 и ch2 подразумеваешь их ASCII-коды? Тогда они больше размерности массива. В общем, в любом случае нам придется обращаться к кодам символов. Тогда зачем выделять целый массив (33 или 66 байтов!), если можно и так сравнить символы ord[ch1]<ord[ch2] (для паскаля)? Ведь старшей букве в алфавите соответствует больший код ASCII. Исключение - буква ё, но ее в ДОСе я даже ввести не могу с клавиатуры, хотя предусмотреть, конечно, можно. Обрати внимание, что в задаче 'асса'>'лига', хотя код['а']<код['л']. Т.е. здесь получается порядок, обратный ASCII-кодам. Если ты все-таки считаешь свой алгоритм приемлемым, приведи хотя бы кусочек кода. Как ты перебираешь символы? Как определяешь, какой из них больше?
Здесь от перебора символов никуда не денешься. Единственное, что, как мне кажется, можно оптимизировать, - это сравнение равных или частично равных слов, например, 'кот' и 'кот' или 'ром' и 'рома'. Но может, мне просто так кажется? Точно! Вот что значит - выразить свою мысль!! Сначала, до посимвольной проверки, можно определить, какое из слов короче, и попробовать определить, является ли оно подстрокой длинного слова. Например, так:
Жуткое получилось ветвление. Но вот вопрос: что выполнится быстрее - сначала перебор символов (1-й вариант, см. верхний код) или сначала ветвление (2-й вариант)? |
|||
|
||||
VaiMR |
|
|||
Шустрый ![]() Профиль Группа: Участник Сообщений: 67 Регистрация: 25.11.2006 Репутация: нет Всего: 2 |
Извини, невнимательно прочитал задание - нумерация в массиве должна быть обратной.
Все это можно оформить в виде маленькой функции, которой передаются строки, и минимальная длина, а возвращает она результат больше, меньше. |
|||
|
||||
Akina |
|
|||
Советчик ![]() ![]() ![]() ![]() Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Если бы было наоборот - асса < лига и фильм > право - я бы тоже склонялся к теории лексикографического порядка, т.е. если символ дальше от начала алфавита, то он больше. Но в такой постановке, как указано в инит-посте, я даже не знаю что и думать... -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
Frekenbok |
|
|||
![]() Шустрый ![]() Профиль Группа: Участник Сообщений: 51 Регистрация: 29.10.2006 Репутация: нет Всего: 1 |
Всем спасибо
![]() |
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |