Учебно-методический комплекс дисциплины для обучающегося «Языки программирования» для специальности 5В010900 Математика
жүктеу/скачать 1.33 Mb.
|
| Пример 4 (фиксация спецзнаком заменяемого символа)
А={0,1,2,3}. Пусть Р — непустое слово. Трактуя его как запись неотрицательного целого числа в четверичной системе счисления, требуется получить запись этого же числа, но в двоичной системе. Например: 0123 → 00011011 Решение. Как известно, для перевода числа из четверичной системы в двоичную надо каждую четверичную цифру заменить на пару соответствующих ей двоичных цифр: 0→00, 1→ 01, 2→10, 3→ 11. Такая замена, казалось бы, реализуется следующим НАМ: Но этот алгоритм неправильный, в чем можно убедиться на входном слове 0123: Ошибка здесь в том, что после замены четверичной цифры на пару двоичных цифр уже никак нельзя отличить двоичные цифры от четверичных, поэтому наш НАМ начинает заменять и двоичные цифры. Значит, надо как-то отделить ту часть числа, в которой уже была произведена замена, от той части, где замены еще не было. Для этого предлагается пометить слева спецзнаком * ту четверичную цифру, которая сейчас должна быть заменена на пару соответствующих двоичных цифр, а после того как такая замена будет выполнена, спецзнак нужно поместить перед следующей четверичной цифрой: 0123 → *0123 → 00*123 → 0001*23 → 000110*3 → 00011011* Как видно, слева от спецзнака всегда находится та часть числа, которая уже переведена в двоичный вид, а справа - часть, которую еще предстоит заменить. Поэтому никакой путаницы между четверичными и двоичными цифрами уже не будет. Итак, спецзнак * сначала должен быть размещен слева от первой цифры четверичного числа, а затем он должен «перепрыгивать» через очередную четверичную цифру, оставляя слева от себя соответствующие ей двоичные цифры. В конце же, когда справа от * уже не окажется никакой цифры, спецзнак надо уничтожить и остановиться. Как приписать * слева к входному слову и как уничтожить спецзнак с остановом, мы уже знаем по предыдущему примеру, а вот «перепрыгивание» звездочки реализуется с помощью формул вида *α→ βγ*, где α - четверичная цифра, а βγ - соответствующая ей пара двоичных цифр. Итого, получаем следующий алгоритм перевода чисел из четверичной системы в двоичную: Проверим этот НАМ на входном слове 0123: Пример 5 (перемещение спецзнака) А={a,b}. Требуется приписать символ a к концу слова Р. Например: bbab→bbaba Решение. Прежде всего напомним, что формула →a приписывает символ a слева к слову P, а не справа. Чтобы приписать a справа, надо сначала пометить конец слова. Для этого воспользуемся спецзнаком, который поместим в конец P, а затем заменим его на a: Но как поместить спецзнак в конец слова? Делается это так: сначала спецзнак * приписываем слева к слову P, а затем «перегоняем» звездочку через все буквы слова: А как сделать такой перегон? Нетрудно заметить, что «перепрыгивание» звездочки через какой-то символ ξ - это замена пары *ξ на пару ξ*, которая реализуется формулой *ξ→ ξ*. С учетом всего сказанного получаем следующий НАМ: Отметим, что при пустом входном слове этот НАМ сначала введет звездочку, а затем тут же заменит ее на символ a и остановится. жүктеу/скачать 1.33 Mb. Достарыңызбен бөлісу:
|