Первое слово необходимо преобразовать во второе, используя наименьшее количество следующих действий:
1.удалений символа;
2.замен символа на любой другой.
Ваша программа должна
запросить исходное слово (до 20 символов), которое будет преобразовываться;
запросить слово, которое нужно получить;
для найденного самого короткого преобразования выполненного по правилам сообщить:
число удалений;
число замен;
для контроля слово, образовавшееся после выполнения всех удалений и слово-результат,
или сообщить, что преобразование невозможно.
Пример. Исходные данные: корова, свора. Ответ: удалений 1, замен 3, после удаления – коова, итог –свора.
2 случая я рассмотрела….с 3им проблемы…(там, где звёздочки, нужно вставить ещё несколько условий)
Program P3;
const
n=20;
var
a,b:string[n];
i,j,k:integer;
del1,fin:string[n];
del,ch:integer;
begin
writeln ('Vvedite nachalnoe slovo',a);
read(a);
writeln ('Vvedite konechnoe slovo',b);
read(b);
if length(a)<length(b) then
writeln ('Preobrazovanie nevozmozhno')
else
begin
if a=b then
ch:=0;
del1:=a;
fin:=b;
del:=0;
begin
for i:=1 to length(a) do
begin
if a[i]<>b[i] then
ch:=ch+1;
end;
end;
end;
if length(a)>length(b) then
del:=length(a)-length(b);
**************************************************************
writeln('Delete – ',del,', Change – ',ch,', After delete – ',del1,', Final – ',fin);
end.
16 ноября 2009 в 0:03
На Паскале – нет, я недостаточно им владею. C или Python – могу, но не сейчас.
16 ноября 2009 в 0:00
Вообщем так я и не решила….А не могли бы Вы написать мне правильный код?…А то обидно, что так и не узнала правильного решения…
Хоть на будущее буду знать….
14 ноября 2009 в 9:00
Неверно по двум причинам. Первое, фрагмент
repeat
for i:=0 to length(a) do
begin
if a[i]<>b[i] then
delete(a,i,1);
end;
until length(a)>=length(b);
будет делать не то, что ты имеешь в виду. Он может удалить больше символов, чем требуется.
Вторая, это не то, что нужно для оптимального решения. Вот скажем, рассмотрим преобразование
aabccd -> aaecc
Оно делается за одно удаление (d) и одну замену. А вот если ты удалишь первую несовпадающую букву – b – то оно потребует две замены вместо одной, что неоптимально.
14 ноября 2009 в 8:05
Tanya ✖♥ Bass, проблема в том, какие именно символы удалять из строки a. Фактически, то, как делать 2 и 3 оптимально выше я и описал. Дополню только, что надо еще запоминать путь (т. е. выбранный вариант – 1 или 2) для восстановления результата удаления.
14 ноября 2009 в 8:05
Денис "Марсианин" Лисов,
вот посмотрите…Я считаю, что это выглядит примерно так…Но здесь есть какая-то ошибка, которую я никак не могу найти…
Program P3;
uses
crt;
var
a,b:string;
i,j,k:integer;
del1,fin:string;
del,ch:integer;
flag:boolean;
begin
writeln ('Vvedite nachalnoe slovo',a);
read(a);
writeln ('Vvedite konechnoe slovo',b);
read(b);
if (length(a)>=20) or (length(b)>=20) then
flag:=false;
if length(a)<length(b) then
writeln ('Preobrazovanie nevozmozhno')
else
begin
if a=b then
ch:=0;
del1:=a;
fin:=b;
del:=0;
begin
for i:=1 to length(a) do
begin
if a[i]<>b[i] then
ch:=ch+1;
end;
end;
end;
if length(a)>length(b) then
del:=length(a)-length(b);
repeat
for i:=0 to length(a) do
begin
if a[i]<>b[i] then
delete(a,i,1);
end;
until length(a)>=length(b);
del1:=a;
fori:=1 to length(a) do
begin
if a[i]<>b[i] then
ch:=ch+1;
end;
writeln('Delete – ',del,', Change – ',ch,', After delete – ',del1,', Final – ',fin);
end.
14 ноября 2009 в 8:02
так….у меня в программе написаны все варианты решения кроме того, где length(a)>length(b)..Причё количество удалений найти очень легко, del:=Length(a)-length(b)..
Далее у меня была вот такая мысль:
1. Сравнить строки а и b
2. Удалить несовпадающие символы и строки a, причём делать это пока length(a) не станет равно length(b)
3. Сосчитать кол-во несовпадений в полученных строках (теперь уже равной длины)
4.Вывести строку a и результат 3-го пункта
а вот как это реализовать у меня не получается…
14 ноября 2009 в 2:03
хм. Попробую реализовать. Утро вечера мудренее.
14 ноября 2009 в 2:02
Итоговое решение требует времени порядка n*k, где длина входной строки n+k, целевой – n.
14 ноября 2009 в 2:01
И по времени тоже не прокатит, даже для 20 символов. Рост времени – быстрее экспоненты.
14 ноября 2009 в 2:01
Как нам путем преобразования получить нужную строку? Есть всего два варианта:
1. Если первый символ исходной строки удаляется, то задача сводится к задаче получить нужную строку из исходной строки без первого символа и решается за такое же число замен – рекурсия.
2. Если первый символ исходной строки сохраняется, то задача сводится к задаче получить нужную строку без первого символа из исходной строки без первого символа и требует либо столько же замен, либо на одну больше, в зависимости от того, совпадают ли первые символы. Опять рекурсия.
При этом требуется учесть несколько специальных случаев, наобходимых для завершения рекурсии:
a. Если длины строк равны, то вариант 1 невозможен и остается только вариант 2.
b. Если требуется получить строку длины 0, то это делается за 0 замен вне зависимости от длины исходной строки.
Пока эта рекурсия будет идти очень медленно. Почему? Потому что множество вариантов будет рассчитываться неоднократно. Нужно оптимизировать.
Заметим, что нам в ходе решения требуются решения задачи:
За сколько замен (плюс сколько-то удалений) можно превратить последние n+k символов входной строки в последние n символов целевой строки?
При этом мы ищем решение с заранее известными n и n+k (длины целевой и входной строк), а рекурсия ссылается на ту же задачу для n'=n, k'=k-1 (если k' >=0) и n'=n-1, k'=k (если n' >=0).
Следовательно, нам достаточно будет посчитать решения этой задачи для k и n от 0 до начальных значений. Начиная счет от 0, мы тем самым превращаем нашу задачу в последовательное заполнение массива по известному алгоритму вплоть до получения требуемого значения.
14 ноября 2009 в 2:00
Алгоритм неверный.
Контрпример:
acccbb -> aabb
Должно быть 2 del 1 swaps. А программа выдает?
14 ноября 2009 в 2:00
google "динамическое программирование". Или могу здесь обрисовать идею решения задачи.
14 ноября 2009 в 2:00
обрисуй здесь пожалуйста.
14 ноября 2009 в 1:05
Корректность сходу проверить не могу, но алгоритм крайне медленный.
14 ноября 2009 в 1:05
> (до 20 символов)
Для двадцати символов наверное покатит. А где можно почитать про более верные варианты?
14 ноября 2009 в 1:00
Чёрт, я не учёл, что можно удалять с середины. Тогда программа значительно усложняется.
//nopaste.info/d26e6d7659.html
рекурсия во все поля!
14 ноября 2009 в 1:00
Может опять где-то оплашал, лучше посмотрите. Указанные контр-примеры проходят.
14 ноября 2009 в 0:04
Идей у меня на этот счёт было много….Но все они оказались не оптимальными, либо очень сложными, либо я не знала как их оформить технически…
14 ноября 2009 в 0:04
Попробуй найти примеры динамического программирования и понять, как это делается…
14 ноября 2009 в 0:03
Тут нужно либо перебрать все варианты вырезания букв – но это может быть очень долго – либо применить какую-то хитрую идею. Динамическое программирование – это идея.
14 ноября 2009 в 0:02
Я в программировании новичок)))
Так что не особо знаю различные подходы к решению задач…
14 ноября 2009 в 0:01
Денис "Марсианин" Лисов, да, действительно, программа работает не очень правильно….
в данный момент перерабатываю…))
14 ноября 2009 в 0:01
Мне кажется, что задача на динамическое программирование. По крайней мере, такой подход позволит решить задачу за достаточно малое время.
14 ноября 2009 в 0:00
Все хорошо, только вот алгоритм неверный, как мне кажется.
Парочка контрпримеров:
aaaaa -> bbb
Должно быть 2 del 3 swaps, а программа что выдает?
aaccbb -> aabb
Должно быть 2 del 0 swaps, а программа что выдает?
13 ноября 2009 в 23:00
Я имел ввиду послушать.
Я вообще до некоторого времени думал что басисток не бывает =).
Даже спеллчекер говорит что не знает слов "басистка" "басисток".
13 ноября 2009 в 23:00
Басистки бывааают)))
И барабанщицы тоже))
13 ноября 2009 в 22:03
Есть чем похвастаться?
13 ноября 2009 в 22:03
Если Вы о стаже игры (не только на басу) – есть))
А если о том, чего бы послушать, то в данный момент записанных вещей нет(
13 ноября 2009 в 22:02
Большое спасибо)
Да, правда)
13 ноября 2009 в 22:00
Держи
//nopaste.info/ed449ec85f.html
А ты что, правда на басу играешь?