Слова (Паскаль)

[Паскалька^^]

Первое слово необходимо преобразовать во второе, используя наименьшее количество следующих действий:
1.удалений символа;
2.замен символа на любой другой.
Ваша программа должна
запросить исходное слово (до 20 символов), которое будет преобразовываться;
запросить слово, которое нужно получить;
для найденного самого короткого преобразования выполненного по правилам сообщить:
число удалений;
число замен;
для контроля слово, образовавшееся после выполнения всех удалений и слово-результат,
или сообщить, что преобразование невозможно.

Пример. Исходные данные: корова, свора. Ответ: удалений 1, замен 3, после удаления – коова, итог –свора.

[Sasha_Smirnov]

Люблю вот такие головоломки — но только с заменами! Удаления плавят мозг.

С нетерпением жду, что выдаст форум. Спасибо за задачу!

[LeBron]

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

Сообщение от Sasha_Smirnov

Люблю вот такие головоломки — но только с заменами! Удаления плавят мозг.
С нетерпением жду, что выдаст форум. Спасибо за задачу!

В чем, собственно, головоломка? У меня на алгоритмическое решение ушло 15 секунд, так как сдесь не надо никаких особенных "уловок". Естественно, если думать над решением, которое будет работать для слов из 10000 символов, то надо юзать спецалгоритмы или "мощную логику". А сдесь ничего такого не надо.

[Паскалька^^]

LeBron, в том и дело, что пока что мыслей нет....хотелось бы какую-либо наводку узнать...

[LeBron]

Сообщение от Паскалька^^

LeBron, в том и дело, что пока что мыслей нет....хотелось бы какую-либо наводку узнать...

С 20 символами можно писать даже полный перебор, даже "тупой полный перебор", просто сгенерить все возможные упорядоченные комбинации с этих 20 букв, и для каждой проверять, если в нее входит столько букв, сколько в нашем образце, то посчитать количество букв-совпадений. Для 20 букв - миллион комбинаций, вместе с самой генерацией и даже с проверкой результата - при прямых руках 50 млн операций, если не меньше. Работать будет быстрее, чем за секунду.
Можно и оптимальнее, но не вижу смысла.

[Паскалька^^]

ну по сути нужно сначала запросить два слова(строки длиной <20).
Далее сравнить их длины...как сказано выше...
и далее входить в цикл сравнения 2х слов, если это возможно. а вот именно с заменами и удалениями проблемы...

[LeBron]

Сообщение от Паскалька^^

ну по сути нужно сначала запросить два слова(строки длиной <20).
Далее сравнить их длины...как сказано выше...
и далее входить в цикл сравнения 2х слов, если это возможно. а вот именно с заменами и удалениями проблемы...

Начало верное. Вы растете в моих глазах, даже приятно помогать такому человеку О каком цикле идет речь? Имеете ввиду посимвольное сравнение строк для подсчета количества различий? По поводу замен и удалений - никто фактически и не просит их делать, главное - подсчитать количество. Для полного перебора заводим дополнительное хранилище на лучший "образец после удаления", если у нас получился вариант с лучшим ответом, чем был раньше - просто меняем "образец" в хранилище.

[Паскалька^^]

Да, я хочу сосчитать различия...
Ещё у меня вопрос по поводу наименьшего количества действий...
Как бы это более оптимально выразить?

[LeBron]

Сообщение от Паскалька^^

Да, я хочу сосчитать различия...
Ещё у меня вопрос по поводу наименьшего количества действий...
Как бы это более оптимально выразить?

Различия разумно считать только для слов равной длины, примерно так:

for i:=1 to length(st) do if st[i]<>st1[i] then inc(ans);

внчале нулевая переменная ans будет хранить число различий. По поводу наименьшего количества действий - понятно, что для удаления лишних символов всегда нужно одинаковое количество действий (равное числу этих символов), следовательно, нужно так удалять символы, что бы получилось "слово", наиболее близкое к конечной цели.

[Паскалька^^]

LeBron, спасибо)) сейчас ещё подумаю и отпишусь..