 |
Тема 4.8 Реализация через последовательность команд «Сравнение – Ветвление».
|
|
|
|
Тема 4. 8 Реализация через последовательность команд «Сравнение – Ветвление».
Составить программу, которая требует ввести два числа. Если первое число больше второго, то программа печатает слово больше. Если первое число меньше второго, то программа печатает слово меньше. А если числа равны, программа напечатает сообщение Эти числа равны.
Как вы уже наверное догадались, в решении этой задачи вам придется обратиться к оператору выбора if else.
| #include < iostream> using namespace std; int main() { setlocale (LC_ALL, " RUS" ); int chislo1, chislo2; cout< < " \t\t\tСравнение чисел используя оператор ветвления\n"; cout< < endl; cout< < " Введите 1 число: "; cin> > chislo1; cout< < endl; cout< < " Введите 2 число: "; cin> > chislo2; cout< < endl; if (chislo1> chislo2) { cout< < " БОЛЬШЕ" < < endl; } else if (chislo1< chislo2) { cout< < " МЕНЬШЕ" < < endl; } else { cout< < " Эти числа равны" < < endl; } cout< < endl; return 0; } |
Тема 4. 9 Реализация через таблицу адресов переходов
Если адрес перехода или вызова подпрограммы является частью самой команды (как данные в командах с непосредственным операндом), это - непосредственный переход. Если адрес перехода команды содержится в регистре или ячейке памяти, это - косвенный переход, так как команда требует загрузки адреса, извлекаемого из некоторого промежуточного места хранения; программа не может перейти прямо в необходимое место, и должна идти туда косвенно.
Существует два метода вычисления адреса перехода. Если в команде указано значение адреса, это абсолютный переход, т. е. переход по абсолютному адресу. Команда может указать место перехода, как некоторое расстояние от нее самой. Этот метод перехода называется относительным переходом.
|
|
|
Преимущество относительных переходов заключается в том, что программа наиболее часто переходит к близлежащим ячейкам; команда перехода может использовать однобайтовое смещение. Если смещение трактуется, как число в дополнительном коде, то двухбайтовая команда относительного перехода (один байт - код операции, и один байт - смещение) может выполнить переход на 127 байт вперед или на 128 байт назад внутри программы. Микропроцессор 8088 имеет два типа относительных переходов: один имеет однобайтовое смещение, другой - двухбайтовое.
В микропроцессоре 8088 все условные переходы имеют однобайтовое смещение. Иногда это неудобно, например в случае условного перехода к ячейке, находящейся на расстоянии в 150 байт от текущего места. В таких случаях программа должна использовать пару переходов, условный и безусловный; далее приводится пример такого метода перехода. В обычных же случаях однобайтовые смещения условных переходов в микропроцессоре 8088 минимизируют объем программы, необходимой для реализации любой заданной функции.
При расчете смещения относительного перехода микропроцессор 8088 отсчитывает смещения от значения указателя команд, которое получится после выполнения команды. Рисунок 4. 26 показывает разные примеры команд относительного перехода. Если точка перехода следует непосредственно за переходом, смещение равно 0. При переходе к самой команде перехода смещение равно -2. При двухбайтовом смещении переход может быть сделан в диапазоне -32768 - 32767 байт от значения регистра IP после выполнения команды перехода.
Тема 5. Реализация через две таблица: адресов переходов и значений.
Перейдем теперь к рассмотрению задачи синтеза дискретного устройства с памятью, которая формулируется так: по словесному описанию алгоритма работы требуется построить схему. Первая проблема, которая здесь возникает, — переход от словесного описания работы схемы к табличному его заданию.
|
|
|
Пусть требуется построить многотактную схему МС (рис. 4. 15, а) с одним входом (кнопка х) и одним выходом (лампа z). Алгоритм работы схемы: лампа z горит после нечетного числа нажатий кнопки х и не горит после четного числа нажатий. Построим ТП (табл. 4. 12) и ТВ (табл. 4. 13) схемы. Нам известно только число столбцов таблиц (два), так как схема имеет один вход. Число строк неизвестно и его требуется определить в процессе построения. Будем нумеровать строки таблиц (состояния схемы) десятичными числами.
Рис. 4. 15. Многотактные схемы
Таблица 4. 12
| S | X | |
| (1) | ||
| (2) | ||
| (3) | ||
| (4) | ||
Таблица 4. 13
| S | X | |
Введем начальное состояние схемы 1, которое имеет смысл «кнопка х не нажималась и лампа z не горела». В таблицах появляется строка 1 и две клетки, которые требуется заполнить. Рассмотрим клетку (0, 1) на пересечении столбца 0 и строки 1. Так как кнопка не нажата (х=0), то z =0 и состояние 1 должно сохраняться до тех пор, пока кнопка не будет нажата. Поэтому в данной клетке в ТП проставляют устойчивое состояние 1, а в ТВ — значение z = 0.
Рассмотрим теперь клетку (1, 1) на пересечении столбца 1 и строки 1. Схема была в начальном состоянии 1 и нажимается кнопка х. В соответствии с алгоритмом работы лампа загорается, поэтому в ТВ в данной клетке проставляем z= 1. Для запоминания факта нажатия кнопки введем новое состояние схемы 2, которое имеет смысл «кнопка нажата нечетное число раз». Схема из состояния 1 переходит в состояние 2. Поэтому в клетке (1, 1) проставляем s— 2 и в таблицах вводим строку 2. Клетка (1, 2) соответствует устойчивому состоянию и в ТП в ней записываем 5 = 2, а в ТВ — z = 1.
Рассмотрим клетку (0, 2). Схема была в состоянии 2, и кнопка х отпускается. Лампа продолжает гореть, поэтому в ТВ в данной клетке проставляем z = 1. Чтобы запомнить факт отпускания кнопки, введем новое состояние схемы 3, которое имеет смысл «кнопка отпущена после нечетного числа нажатий». Схема из состояния 2 переходит в состояние 3. Поэтому в клетке (0, 2) проставляем 5=3 и в таблицах вводим строку 3. Клетка (0, 3) соответствует устойчивому состоянию и в ТП в ней записываем 5 = 3, а в ТВ — z = 1.
|
|
|
Рассмотрим клетку (1, 3). Схема была в состоянии 3 и кнопка нажимается второй раз. В соответствии с алгоритмом работы лампа гаснет, поэтому в ТВ в данной клетке записываем z = 0. Для запоминания факта нажатия кнопки второй раз введем новое состояние схемы 4, которое имеет смысл «кнопка нажата четное число раз». Поэтому в клетке (1, 3) проставляем s — 4 и в таблицах вводим строку 4. Клетка (1, 4) соответствует устойчивому состоянию схемы и в ТП в ней записываем 5 = 4, а в ТВ — z— 1.
Рассмотрим клетку (0, 4). Схема была в состоянии 4, и кнопка отпускается. Лампа не горит, поэтому в ТВ в данной клетке проставляем z=0. Для запоминания факта отпускания кнопки можно ввести новое состояние схемы 5. Однако это состояние можно, очевидно, отождествить с начальным состоянием 1, смысл которого таким образом уточняется «кнопка отпущена после четного числа нажатий». Схема из состояния 4 переходит в состояние 1. Поэтому в клетке (0, 4) проставляем s= 1, и на этом процесс построения ТП и ТВ заканчиваем.
Таким образом, процесс построения ТП и ТВ завершается, когда все новые состояния, которые вводятся при рассмотрении незаполненных еще клеток ТП, можно отождествить с ранее введенными. При этом надо стремиться к минимальному числу строк, так как от последних зависит число ЭП, необходимых для построения схемы.
Алгоритм 4. 2. Построение ТП и ТВ по словесному описанию работы многотактной схемы.
1. Введение начального состояния схемы s{.
2. /'= 1 (присвоение текущему индексу i значения 1).
3. Рассмотрение и заполнение в ТП и ТВ всех клеток строки 5, -. Введение, если это необходимо, новых состояний схемы, которые нумеруют возрастающими индексами.
4. /=/+ 1.
5. Существует ли состояние с индексом /? Если да, то переходят к п. 3, если нет, — то к п. 6.
6. Конец.
Пример 4. 1. Построить ТП и ТВ многотактной схемы, имеющей два входа Xj и х2 и один выход z (рис. 4. 15, б). Алгоритм работы схемы: если вход х2= 1, выход z повторяет значение входа х{; если х2 = 0, выход z сохраняет свое последнее значение. В любой момент времени может измениться состояние не более одного входа.
|
|
|
Применим алгоритм 4. 2. Введем начальное состояние схемы 1, которое имеет смысл «входы Xj и х2 равны 0, а выход z в предыдущий момент времени был равен 0». В этой формулировке значение выхода z указывается в предыдущий момент времени, так как от этого значения зависит работа схемы. Несмотря на то что для начального состояния предыдущего момента не было, схема будет приходить в состояние (1) в процессе своей работы в последующие моменты времени. При построении ТП (табл. 4. 14) и ТВ (табл. 4. 15) вводим следующие состояния: (2) «Xj = 0, х2 = 1, значение выхода z в предыдущий момент времени безразлично»; (3) «Xj = 1, х2 = 0, в предыдущий момент времени z = 0»; (4) «Xj = 1, х2= 1, значение выхода z в предыдущий момент времени безразлично; (5) «xt = 1, х2 = = 0, в предыдущий момент времени z — 1», (6) «xt = 0, х2 = 0, в предыдущий момент времени z=l». Для состояний 2 и 4 значение выхода z в предыдущий момент времени безразлично, так как при х2 = 1 выход z повторяет значение х, независимо от своего значения в предыдущий момент времени.
Таблица 4. 14
| S | х1х2 | |||
| (1) | ~ | |||
| (2) | ~ | |||
| ~ | (3) | |||
| ~ | (4) | |||
| ~ | (5) | |||
| (6) | ~ | |||
Таблица 4. 15
| S | xlx2 | |||
| ~ | ||||
| ~ | ||||
| ~ | ||||
| ~ | ||||
| ~ | ||||
| ~ | ||||
Клетки таблиц, где проставлены знаки безразличного состояния ~, соответствуют полным состояниям, в которые схема не попадает в процессе работы вследствие невозможности одновременного изменения обоих входов. Данные клетки по этой причине могут быть заполнены произвольно.
Таблицы переходов и выходов, построенные по алгоритму 4. 2, имеют в общем случае не минимальное число строк. Поэтому их называют первичными, и следующим этапом синтеза является минимизация числа этих строк. Сравним, например, строки 1 и 2 в табл. 4. 14 и 4. 15. Ясно, что безразличные состояния этих строк можно заполнить так, что строки будут совпадать в обеих таблицах. Состояния, соответствующие одинаковым строкам, являются эквивалентными. Два состояния Sj и Sj называют эквивалентными, если поведение схемы, находящейся в состоянии sjf и поведение схемы, находящейся в состоянии Sj, совпадают для всех допустимых входных последовательностей. Эквивалентные состояния (строки) могут быть объединены и заменены одним состоянием (одной строкой).
Две строки ТП и ТВ называют совместимыми, если они имеют непротиворечивое размещение цифр, т. е. в одном столбце этих строк записаны одинаковые цифры или в одной строке записана цифра, а в другой — знак безразличного состояния. В табл. 4. 14 и 4. 15 имеются следующие пары совместимых строк: (1, 2), (1, 3), (2, 3), (4, 5), (4, 6) и (5, 6).
|
|
|
Максимальным подмножеством совместимых строк Етах назовем подмножество строк, удовлетворяющее двум условиям: любые две строки подмножества являются совместимыми; среди строк, не принадлежащих Етах, нет такой, которая совместима со всеми строками из Етах.
В табл. 4. 14 имеются два максимальных подмножества: Етах] = = {1, 2, 3} и Етах2 ={4, 5, 6}. Все строки максимального подмножества могут быть объединены. В объединенной строке должны быть записаны устойчивые состояния во всех столбцах, в которых были устойчивые состояния хотя бы в одной из объединяемых строк. В результате объединения в рассматриваемом примере получаем минимизированные ТП (табл. 4. 16) и ТВ (табл. 4. 17).
|
|
|
