| Aleko |
| Отправлено: 27.11.2005, 22:18 |
|
Не зарегистрирован
|
Кто поможет неопытному в среде Builder C++ написать программу следующую: "Проверить, можно ли получить слово x из слова y путем перестановки букв".
Я так понимаю, что это надо с помощью массива ее делать. |
|
| AVC |
| Отправлено: 28.11.2005, 09:09 |
|
Ветеран
Группа: Модератор
Сообщений: 1583
|
Достаточно посмотреть являются ли все символы второго слова подмножеством символов первого. |
|
| Aleko |
| Отправлено: 28.11.2005, 21:55 |
|
Не зарегистрирован
|
Да это в принципе все понятно — мне нужен хотя бы примерный вариант кода. |
|
| AVC |
| Отправлено: 29.11.2005, 09:17 |
|
Ветеран
Группа: Модератор
Сообщений: 1583
|
Кода или алгоритма?
Возможный алгоритм:
// слово — это последовательность символов,
// ограниченная 0x00 и не содержащая символа ' '
//
// слово1/2 это указатели на массивы символов,
// удовлетворяющие условию см. выше
temp_слово1 = копия(слово1);
int pos; // может быть char* pos
for (char *cp=слово2; *cp; cp++)
{ if ((pos = поиск_символа_в_стороке(temp_слово1, *cp) != найдено)
return "нельзя составить слово2 из символов слово1";
*(temp_слово1+pos) = ' ';
}
return "можно составить слово2 из символов слово1";
|
|
| Георгий |
| Отправлено: 29.11.2005, 22:46 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
т.е. тебе нужна програмка вроде той, что я приложил?
|
|
| Георгий |
| Отправлено: 29.11.2005, 22:47 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
а вот к ней словарь — его надо скопировать в теже папку, где и программа находится
|
|
| Aleko |
| Отправлено: 30.11.2005, 01:47 |
|
Не зарегистрирован
|
Ну немного не так, т.к. нужна программа, которая бы проверяла слово X и выводила: "Можно получить слово Y" или "Нельзя получить слово Y".
Т.е. это слово Y не надо получать. А так программа очень даже интересная получилась.
И лучше конечно это в виде кода посмотреть, а не .exe. |
|
| Георгий |
| Отправлено: 30.11.2005, 02:38 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
ну она так и работает — берёт слово из словаря и спроверяет можноли из букв исходного слова составить словарное.
была такая телепередача "звёздный час" и в финале 2 финалистам предлагалось из букв слова составить как можно больше других слов. как то раз решил я с ними с помошью своей проги посоревноваться...
игроки в общей сложности 30 слов придумали, а прога.... 240 
эту прогу написал на первом курсе — почти 6 лет назад. с друзьями соревновался, кто более быстрый алгоритм сделает.
эталонная программа была написана одним из них на паскале и из слова "перпендикулярность" составляла другие слова около 4 часов.
в результате небольших изысканий было придумано 2 алгоритма — оба очень простые, но существенно отличающиеся. реализовав их на C++ получили смешные времена работы — из слова "перпендикулярность" по словарю составлялись слова не больше 100ms т.е. в 150 000 раз быстрее чем эталонная программа, более того, обнаружили что эталонная работает с ошибками  некоторые слова она не правильно проверяла.
алгоритм №1
идея: вычёркиваем из эталонного слова буквы, что есть в словарном слове.
алгоритм:
1. i=0
2. берём i-тую букву словарного слова
3. ищем её в эталонном слове
3.1 если нашли, то вычёркиваем (заменяем на любой не символьный литерал, например на '_' нижний подчерк) её из эталонного слова
3.2 если не нашли, то из букв эталонного слова нельзя составить словарное
4. переходим на следующую букву словарного слова, если дошли до его конца, то из букв эталонного слова можно составить словарное
алгоритм №2
идея:упорядочим буквы словарного и эталонного слова в порядке их возрастания и двигаясь строго от начала паралельно сравниваем символы строк с переходом по эталонной строке вперёд, если нет совпадения. если первой закончилась эталонная строка, то нельзя составить из эталонной словарную, в противном случае можно.
например:
эталонная : парк
словарная : рак
после сортировки:
эталонная : акпр
словарная: акр
берём первую букву словарного и ищем такую же в эталонном и находим на первой позиции
остаётся
эталонная : кпр
словарная: кр
берём следующую из словарной и так же ищем.
остаётся:
эталонная: пр
словарная: р
берём следующую из словарной и остаётся:
эталонная: п
словарная : закончилась
т.к. словарная закончилась, то делаем вывод, что из букв эталонной можно составить словарное слово.
алгоритм №2 более сложный, но и более оптимальный по сравнению с 1м алгоритмом. он выполняет сравнение проверку за один проход и только читает строки, не модифицируя их. но для своей работы он требует предварительной сортировки букв слов.
результаты эксперимантов показали, что никакой практической разницы в скорости нет. алгоритм №2 быстрее работает на длинных эталонных словах, а №1 на коротких. но эта разница выращалась либо в 0.020 ms работы, либо в 0.030 ms т.е. практически никакой разницы не было.
что-то я от темы отвлёкся в общем — в проге реализован алгоритм №2 (это как раз я его придумал) реализация алгоритма — всего 10 строчек + ещё на 100 строк обвязка — загрузить файл, показать менюшку и т.п.
|
|
| Aleko |
| Отправлено: 30.11.2005, 13:08 |
|
Не зарегистрирован
|
Реализовать мою программу надо по другому. Т.е. вводим слово X в Edit1, потом вводим слово Y в Edit2. После чего нажимаем на кнопку и идет проверка : можно ли из слова X получить Y. В Label запишется результат, т.е. выведется. Эти слова не надо получать: просто сказать, что да, можно или нет, нельзя. Т.е. не надо подключать библиотеку. Сравнивать только 2 заданных слова. |
|
| Георгий |
| Отправлено: 30.11.2005, 21:04 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
у меня там внутри есть функция, которая получает на вход слова X и Y и говорит можно ли из букув слова X составить слово Y. т.е. именно то, что тебе надо по заданию |
|
| Aleko |
| Отправлено: 30.11.2005, 22:32 |
|
Не зарегистрирован
|
А какая именно функция, а то порылся, не со всем разобрался. |
|
