Задача Word2

 
Під час  уроку інформатики два учні, не слухаючи пояснень вчителя, грають в таку гру. Кожен з них в своєму зошиті записує два обраних ними разом слова  і намагається за певну кількість ходів з першого слова отримати друге. Виграє той, хто зробить мінімальну кількість ходів. Хід – це одна з таких операцій:1.замінити якийсь символ з першого слова  якимось символом другого слова;2. викреслити якийсь символ з першого слова;3. ставити якийсь символ з другого слова після або перед якимось символом першого слова. Наприклад, для перетворення слова “limuzin” в слово “buzina” необхідно виконати такі дії: 
Перетворення Номер операції
limuzin
imuzin
ibuzin
ibuzina 
=>
=>
=>
=>
imuzin
ibuzin

ibuzina
buzina
2
1
3
2
       
 
 







Спробуйте написати програму, яка знаходить  мінімальну кількість ходів для перетворення одного заданного слова в інше.
Технічні умови  Програма читає з клавіатури дві стрічки довжиною не більше 104   символів кожна і виводить на екран єдине число – мінімальну кількість ходів. 

Приклад        Введення      Виведення
  

 limuzin buzina

 4 

© LIKT 1998-2018