Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 46
Текст из файла (страница 46)
Предположим, что машина имеет память, состоя1цую из неограниченного числа регистров; Лп Лн Лз и т. д., п что содерясаппе казкдого регистра Л, ость г, ы 'г'. Это можно изобразить так, как это сделано па рнс. 91. Для более ясного изложении удобно разрешить использование Р,. эд многих операпвй, действующих над регистрами, однако па самом деле необходимы лишь дзе операции: Л, -Л„+1, Л -˄— 1. Обозначая содержимое регвстра и до операции и после Ф через г„и г„соответственно, можно описать результаты выполнения этих операций следующим образом: Л„.с — Л„+ 1==г„= г„+ 1, 1г„— 1, если г„) О, Л„ч-Л,— 1 г„=~ — "=1О, если г„= О.
Броме операций, изменяющих зпачоппя регистров памяти, необходимо, чтобы машина имела связь с программок для того, чтобы влиять па ее работу. Необходимой в атом случае является только одна операция, а именно та, которая осуществляет сравнение Л.=О. Однако, как и прежде, мы будем разрешать более общие формы операций такого рода. Результат Л. О справедлив тогда и только тогда, когда г„ О, и это условна используется для управления программами. Ыножество регистров вместе с описанными выше определениями называется машипой с неограниченной памятью (МНП). Программы состоят из конечной совокупности операций, занумерованных от 1 до некоторого люХ.
Мы не будем вдаваться в детали, а выведем-более общие заключения об этих программах. Поэтому не будем давать формального определения такой структуры. Рисунков 9.2 и 3(9 9.8 достаточно, чтобы вонять, какого рода конструкции допустимы в ной. Программа ка рвс. 9.2 яе предпаакачева для выполиевия особо рааумпых вычислеввй, одяако ова укааывает Рас. 9.2 вид блок-схемы программы для вашей машины.
Заметим, что все ото может быть ааписаяо ве обнаательво в виде рисунка. Например, можно пописать: 1: если Вт О то перейтп к 4 виаче перейти к 2 2: Ва - Вт- $ (еатем перейти к 3) 8: В~ - В~ + $ (аатем перейти к 4) 4: если Вт О то перейти и 6 ииаче перейти к 5 5: Вз - Вз - 4 (ватем перейтв к 2) б: ВТОР На рис. 9.3 представлена более общая форма программы, в которую включены макрокоманды Г, в проверки Ть Это могут быть ставдартпыо команды того типа, который уже определен, или же онв могут быть представлены последовательиостью осповпых команд, кото- 804 рым для удобства чтения даны имена (подобно подпрограмме), детали которых уже где-то определены. Такие последовательности будем называть макропоследовательностями.
Сейчас мы можем описать некоторые из этих макролоследовательыостей, которые обеспечат связь с последующими темамя, а также помогут убедить читателя, Ряс. 9.4 Рзс. 9.3 что наше ыебольшое число простых команд на самом деле является достаточно мощным средством.
Пример 1.1. В~ -О может быть реализовано следующим фрагментом программы, где метки х, у и з выбраыы так, чтобы не пересекаться с другими командами в программе: х: если В~ - О то перейти к з ыыаче перейти к у у: Н~ - В~ — 1 (затем перейти к х) 3; В терминах блок-схем этот фрагмент программы изображен на рис.
9.4. П р и м е р 1.2. Сейчас, определяя макрокоманду, удовлетворяющую предыдущему примеру, и включая в явном виде выражения «йо 1оз («перейтп кэ) только тог- 29 д. ктк, г. всзс 306 да, когда мы уклоняемся от выполнения команды «уо 1о пех1!пвьгпс11оп» («перейти к следующей команде»), мы можем дать раскрытие формулы В« - т (для некоторого ты Х): Л;«-О Л, Л, + 1 '+1 т рав Л,+-Л,+1 Очередное расширение множества команд требует испольаования «рабочей памяти». Мы будем предполагать, что по крайней мере в простейших случаях читатель в состоянии придумать подходящую стратеги«о работы с памятью, и, следовательно, не будем спецкально упоминать о том, как выбираются зти дополнительные регистры. Случаи„ когда количество требуемой памяти неизвестно (такие, как стеки и т. и.), будут рассмотрены ниже е).
Пример 1.3. Используя Л, в качестве рабочего регистра, мы можем скопировать содержимое Л, в Л« (Л« -Л,), Делая вто, мы уннчтоя«аем содержимое В«, которое в дальнейшем доля«яо быть восстановлено. Следующая программа осуществляет требуемые вычисления: Л«О х: П В, = О 11«еп до 1о у Л» Л»+ 1 Л» — В,— 1 1иеп цо 1о х у: В« О п»е 11 В, О 11«еп цо 1о з Л«Л«+ 1 В,-Л,+1 В» - Л» — 1 1Ьеа яо 1о и» л: У Сейчас мы вернемся к «собственно» арифметическим вычислениям. Сложение и вычитание строятся непосредственно, однако, поскольку в регистрах существуют огра- ») П дальней«псы буден пспользоезть символы: «Ло 1о з»вЂ” «перейтп и »»; «М (услозие) «Ье«« (оператор)»-«если (услозие), то (оператор)»; «е1«е» †«илзче»; «Й«еп йо Ь »»-«затеи перейти и»а — Прил««. лер.
ннчения на значения величин, опорация вычитания долл на быть несколько модвфпцнрована. Подобным же образом можно выполнить умножение и усеченное деление. Пример 1.4. Сложение П; П.+Л„, имеющее реаультатом г~ = г; «гю моя1ет быть выполнено следующим образом: Л, Л, »и И Л, = О йеп бо 1о у Л~ -Л,+1 Л« - Л~ — 1 йеп яо 1о х Чтобы получить полную программу в термина« основпык команд, мы должны расшифровать макрокоманду «Л, Л„», как это было сделано в примеры 1.3. С атого времени мы пе будем требовать доказательства таких расшифровок.
Подобным образом «ограниченное вычитание» Л,- — Л~ — Л, может быть выполнено как Л, - Л„ х: И П> = О йеп яо 1о у П,-П,-1 П~ ~- Л~ — 1 йеп яо 1о х у: Заметим, что если первоначальные зпачепия П, и В, были такие, что г,( г„то после г, итераций операция Л,— П вЂ” 1 не будет иметь аффекта. Аяалогпчпо П, - Л, » П, может быть представлено как Л, О Л,~-Л, х: ИЛ,=ОйепбоФоу П, П, — 1 Л> Л, + П, йеп до 1о х у: Л, — П~ У В боль-пппстве случаев таким же способом, каким мо:кот быть расширено мпон1ество операций над регнстрамк путем определения макрокоманд, можно также ввести ко- 20« 307 манды сравнения, которые на первый взгляд оказываются более сложными, однако в действительности строятся из последовательностей стандартных операций и операций сравнения. П р и м е р 1.5.
Мы можем записать операцпю «И В! ) ) В, 1Ьеп йо $о х е(ве йо 1о у» («если Н!) Л„то перейти к х; иначе перейти к у») следующим образом; Л! Н! Л! — Н! — Л„ И Л, = О (Ьеп йо 1о у е1ве яо 1о х Этими операциями условного перехода мы можем дополнить наше множество первоначальных арифметических операций вместе с операцией деления «Л, Л,—:Л„, где г, =О, если г,=О».
В нашем случае этой операции соответствует следу!ощий алгоритм: Л! -О И В, — О 1Ьеп йо 1о х йч И Н, ( Н, 1Ьеп до 1о х В, - В, + 1 И Л Л» 1Ьеп но 1о л Н, Н -Н«1Ьеп йо 1о у зс Н! Н! Из менее общего, но необходимого приложения, ко- торое кратко приведено ниже, следуют две операции, связанные с точностью усечення при делении целых чисел. Пример 1,6. Если г,чьО, операция «еслн Л,— де- литель Ль то перейти к х; иначе перейти к р» действу- ет следующим образом: И Л, = О «Ьеп йо «о у Н, - Л! Н! «- В, †: Н„ Н, — Н!«Л, ИЛ! Л, 1Ьеп но(ох е1ве йо(ар При помощи этой (возможно, несколько странной) опе- рации и операции сравнения вида Л, л« (оставленной в качестве упражнения) мы можем проверить, является ли г! простым числом.
зсо Ясно, что можно операцпю «еслн В, простое, то перейти к х; иначе перейти к у» смоделировать следующим образом: И В, = О йеп йо 1о у И Л, = Х 1Ьеп йо 1о у В, В,— 1 х: И В» 1 1Ьеп йо 1о х И Л» делитель Л, 1Ьеп йо 1о у Л, Л» — 1йопйо(оз Х Перед последним примером этого параграфа мы долм<мы упомянуть, как в машине вводятся данные н выводится результат. Предполом<им, что мы хотим вычислить значение теоретико-числовой функции г< У"- Ф™. Значения и и т известны перед началом выполнения соответствующей программы; поэтому мы можем вначале выделить и регистров (в которые должны быть загружены начальные значения перед началом выполнения программы) для входных данных и т регистров (которые не должны быть обяаательно отличными от выбранных вначале) для выходных данных. Когда программа останавливается, мы предполагаем, что некоторый «внешнпй представитель» может выдать «ответы» нз соответствующих мест, Это, конечно, разумный путь моделирования потоков данных в программе, поскольку точно показывает взаимодействие операций ввода-вывода.
С этими соглашеняямн пример 1.7 может рассматриваться илн как полная программа (в которой Л, и В, выбраны как входные и выходные регистры), или как схема для подпрограммы. Пример 1.7. Последовательность команд приведенных неже, помещает и-е простое число в Ль где и является содержимым Л;, предполагается, что и не равно нулю: (Я1аг1) Л, Л,— $ В, 2 х: ИЛ, 01Ьепйо1оу Л, -Л+1 х: И Л, простое йеп йо 1о и» Л, - Л» + 1 йеп яо 1о з пн Я,~-й~ — 1 1йеп яо 1о х у: (е1ор) У Сейчас мы объясним паш очевидный иптерес к простым числам.
1.2. Кодяроваиие программ. Программы п. 1.1 могля работать с элементами иа )т=Х 010). Мы должны объяснить, как в принципе можно любую программу рассматривать в качестве программы такого типа. Это можно сделать, описав способы, при помощи которых различные типы данпых могут быть закодпровапы в алемеиты из )т. Для этого рассматриваем данные предлонгепия пад подходящими алфавитами и, следовательно, почти как постороннее следствие этого процесса получаем также метод для кодирования предложений на языках программирования, а именно сами программы. Осиовпое математическое средство, используемое для этой цели, это теорема о единственности разложения, известная также как основная теорема арифметики. Эта теорема устанавливает, что произвольпый алемепт из )т является или О, или 1 либо может быть выражен единственным образом как произведение упорядоченных простых чисел. Ясно, что если аж УЧО, 1) и п д~ в уз в...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
