ВУЗ:
Составители:
Рубрика:
78
принимал на вход строки текста и формировал выходные
строки , в зависимости от программы заложенной в него в
это время. Чип для этого компьютера создавался
исключительно по RISC технологии и поэтому набор
команд был представлен всего тремя инструкциями:
- Удалить символ в указанной позиции.
- Вставить символ в указанную позицию.
- Изменить символ в указанной позиции на другой.
Программа для этого компьютера должна была бытьь
написана в форме машинного кода, каждая инструкция которого
имеет формат «ZXdd», где Z представляет собой код
инструкции ( соответственно D, I, C ), X – это символ и dd
представляет собой двухзначное число - позицию. Программа
заканчивается специальной инструкцией для останова в виде
литеры ‘E’.
Для примера рассмотрим преобразование строки “abcde” в
строку “bcgfe”. Это может быть выполнено серией команд C(
change ), но программа будет не самая оптимальная. Следующая
программа будет лучше:
Abcde
Da01 Bcde
Cg03 Bcge
If04 bcgfe
E bcgfe
Напишите программу, которая будет читать две строки и
находить минимальную по количеству инструкций программу,
необходимую для преобразования первой строки во вторую. Так
как решение может быть неоднозначно, достаточно найти одно
решение.
