Chapter_03 (1110555), страница 3
Текст из файла (страница 3)
Наши следующие программы для УМ-3 мы также будемдля удобства писать не на "чистом" языке машины, а на таком псевдокоде.3.2.3. Пример 3. Реализация циклаВ качестве следующего примера напишем программу для вычисления начального отрезка гармонического ряда:ny 1/ii 1Наша программа должна вводить значение переменной n и выводить в качестве результата работы y. Для хранения переменных n,y и параметра цикла i выделены ячейки 100, 101 и 102 соответственно. На рис.
3.3 приведена возможная программа для решения этой задачи.№001234567890101234КомандаВВЦВЧВПЕРВЧЦПБВЕЩДЕВСЛВСЛЦБЕЗВЫВСТОП00100 001101 101102 000000 102000 011000 000000 014101 101102 102000 004101 001000 000000 000<1.0>Комментарий000101013100000102000000013000000000001Read(n)y := 0.0i := 1<000> := i–n; формирование wif i>n then goto 011<000> := Real(i)<000> := 1.0/Real(i)y := y+<000>i := i+1Следующая итерация циклаWrite(y)СтопЦелая константа 1Вещественная константа 1.0Рис 3.3. Программа третьего примера.Сделаем некоторые замечания к этой программе.
В этом алгоритме мы реализуем цикл с предусловием, его аналог на Паскале можно записать в виде:y:=0.0; i:=1; while i<=n do begin y:=y+1.0/i; i:=i+1 end;Поэтому при вводе значения n<1 тело цикла не будет выполняться ни одного раза, и наша программа будет выдавать нулевой результат, что не противоречит математическому смыслу поставленной задачи.Заметим далее, что каждый член ряда является по смыслу задачи вещественным числом, в товремя как параметр цикла i – целая величина. В языке машины у нас нет команды деления вещественного числа на целое, поэтому при вычислении величины очередного слагаемого 1.0/i нам пришлось воспользоваться командой ВЕЩ 000 000 102 . Эта команда преобразует значение целойпеременной i в вещественной значение (заметим, что Паскаль машина будет делать это автоматически!). Обратите также внимание, что для нашей учебной машины мы ещё не определили форматпредставления вещественных чисел, (мы сделаем это позже), поэтому в ячейке с адресом 14 стоитпока просто условное обозначение константы 1.0, а не её машинное представление.3.2.4.
Пример 4. Работа с массивамиПусть требуется написать программу для ввода массива x из 100 вещественных чисел и вычислениясуммы всех элементов этого массива:100S x[i]i 1Сделаем естественное предположение, что длина нашей программы не будет превышать 199ячеек, и поместим массив x, начиная с 200-ой ячейки памяти. Вещественную переменную S с начальным значением 0.0 и целую переменную n с начальным значением 100 поместим в конце текста программы (после команды СТОП), и будем вводить в память вместе с командами при нажатии8кнопки ПУСК.1 Таким образом, в качестве счётчика цикла для нас будет удобнее использовать нецелую переменную i, изменяющуюся от 1 до 100, как в приведённой выше формуле, а переменнуюn с начальным значением 100, которая будет изменяться от 100 до 1.
Другими словами, мы реализуем цикл, который на Турбо-Паскале можно было бы записать в видеconst S:real=0.0; n:integer=100;. . .i:=0; repeat S:=S+x[i]; i:=i+1; n:=n-1 until n=0На рис. 3.4 приведён текст этой программы.№001234567890101КомандаВВВСЛВСЛЦВЧЦПБВЫВСТОП000000200 100008 200002 002010 010000 002008 001000 000<0.0>000 000000 000000 001Комментарий000008011009000000000001100000Read(x); массив x в ячейках 200299S := S+x[1]Модификация команды в ячейке 2n := n-1if n>0 then goto 002Write(S)СтопВешественная переменная S = 0.0Целая константа 1Переменная n с начальным значением 100Константа переадресацииРис 3.4. Программа четвёртого примера.Рассматриваемая программа выделяется новым приёмом программирования, она является самомодифицирующейся программой, о которых мы говорили при изучении машины Фон Неймана.Обратим внимание на третью строку программы.
Содержащаяся в ней команда изменяет исходныйкод программы (меняет команду в ячейке с адресом 2) для организации цикла перебора элементовмассива.2 При первом выполнении этой команды она адресуется к первому элементу массива, затемко второму и т.д. Для перехода от одного элемента массива к следующему модифицируемая командарассматривается как целое число, к которому прибавляется специально подобранная константапереадресации.3 Согласно одному из принципов Фон Неймана, числа и команды в учебной машиненеотличимы друг от друга, а, значит, изменяя числовое представление команды, мы можем изменятьи её суть.У такого метода программирования есть один существенный недостаток: модификация кодапрограммы внутри её самой повышает сложность программирования, может привести к путанице ивызвать появление ошибок.
Заметим также, что такую программу нельзя повторно выполнить, просто передав управление на её первую команду, 4 так как нужно будет предварительно восстановитьисходный вид всех модифицированных команд. Кроме того, самомодифицирующуюся программутрудно понимать и вносить в неё изменения. Только представьте себе, что Вам необходимо составить алгоритм для машины Тьюринга, в которой можно изменять команды в клетках таблицы (например, заменить команду движения головки по ленте влево на движение вправо). Настоящий кошмар для современного программиста!1Заметим, что так мы, например, сэкономили в программе ячейку, в которой должна была бы хранитьсякоманда обнуления переменной S.2Как уже говорилось, в теории алгоритмов некоторым аналогом такого исполнителя, например, являетсятакая модификация машины Тьюринга, которая в процессе выполнения алгоритма может изменять клетки своей таблицы.
Доказана теорема о том, что все задачи, которые может решать такая модифицированная машинаТьюринга, может решить и обычная машина Тьюринга, т.е. такие алгоритмические системы эквивалентны.3В выборе этой константы есть небольшая тонкость. Как мы вскоре узнаем, целые числа в нашей машинепредставляются в так называемом дополнительном коде (что это такое, мы скоро изучим). В дополнительномкоде первый бит целого числа определяет его знак, поэтому команды с кодами операций больше 15 будут отрицательными целыми числами, что следует учитывать при подборе константы переадресации.
В нашем примере, однако, команда сложения с кодом операции СЛВ=01 является положительным целым числом, и всёбудет хорошо.4Повторное выполнение находящейся в памяти программы может оказаться весьма полезным, например,при счёте нескольких вариантов задачи с разными входными данными. Вспомните так же, как многие диалоговые программы идут на своё повторное выполнение, задав вопрос "Повторить? (Да/Нет)".9В нашей учебной машине, однако, самомодифицирующаяся программа – это единственныйспособ обработки достаточно больших массивов.
В других архитектурах ЭВМ, с которыми мы познакомимся несколько позже, есть и другие, более эффективные способы работы с массивами, поэтому метод программирования с модификацией команд в современных компьютерах, как уже говорилось, обычно не используется.3.3. Формальное описание учебной машиныПри описании архитектуры нашей учебной ЭВМ УМ-3 на естественном языке многие вопросыостались нераскрытыми.
Что, например, будет происходить после выполнения команды из ячейки садресом 511? Какое значение после нажатия кнопки ПУСК имеют ячейки, расположенные вне введённого массива машинных слов? Как представляются целые и вещественные числа? Как будет, например, выполняться такая машинная команда ввода массива: ВВВ 500 100 000 ?Для ответа на почти все такие вопросы мы приведём формальное описание нашей учебноймашины.
При этом в качестве метаязыка мы будем использовать язык Турбо-Паскаль,1 которыйдолжен быть достаточно хорошо Вам знаком. Другими словами, мы напишем программу на ТурбоПаскале, выполнение которой моделирует работу нашей учебной машины, т.е. наша машина, поопределению, работает "почти так же", как и эта написанная нами программа-модель.Ниже приведена реализация учебной машины на языке Турбо-Паскаль:program УМ_3(input, output);constN = 511;typeAddress = 0..N;Tag = (kom, int, fl);{В машинном слове может хранится команда, целоеили вещественное число}Komanda = packed recordKOP: 0..31;A1, A2, A3: Address;end;Slovo = packed recordcase Tag ofkom: (k: Komanda);int: (i: LongInt)fl: (f: Single);endMemory = array[0..N] of Slovo;varMem: Memory;S, R1, R2: Slovo; {Регистры АЛУ}RK: Komanda; {Регистр команд}RA: Address; {Счётчик адреса}Om: 0..2;{Регистр w}Err: Boolean;beginInput_Program; {Эта процедура должна вводить текст программы с устройстваввода в память по кнопке ПУСК}Om := 0; Err := False; RA := 1; {Начальная установка регистров}with RK dorepeat {Основной цикл выполнения команд}RK := Mem[RA].k;RA := (RA+1) mod (N+1);case KOP of {Анализ кода операции}1Так как наша учебная ЭВМ является не языком, а исполнителем алгоритмов, то в качестве метаязыка необходимо выбрать не просто формальный язык (например, язык синтаксических диаграмм), а формальный алгоритмический язык, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
