|
Задача Word2
Во время урока информатики два ученика, не слушая пояснений учителя, играют в такую игру. Каждый из них в своей тетради записывает два выбранных ими вместеслова и пытается за определенное количество ходов из первого слова получить второе. Выигрывает тот, кто сделает минимальное количество ходов.
Ход – это одна из таких операций:
1.заменить какой-то символ из первого слова каким-то символом второго слова;
2. вычеркнуть какой-либо символ из первого слова;
3. Вставить какой-нибудь символ из второго слова после либо перед каким-нибудь символом первого слова. Например, для преобразования слова “limuzin” в слово “buzina” необходимо выполнить такие действия:
|
Преобразование
|
Номер операции
|
|
limuzin
imuzin
ibuzin
ibuzina
|
Þ
Þ
Þ
Þ
|
imuzin
ibuzin
ibuzina
buzina
|
2
1
3
2
|
Попробуйте написать программу, которая находит минимальное количество ходов для преобразования одного заданного слова в другое.
Технические условия. Программа читает с клавиатуры две строчки длиной не более 104 символов каждая и выводит на экран единственное число – минимальное количество ходов.
|
Пример
|
Ввод
|
Вывод
|
|
|
limuzin
buzina
|
4
|
| 
