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