Пример 3. Вычисление таблицы квадратов чисел натураль

118 Э Л Е М Е Н Т А Р Н О Е П Р О Г Р А М М И Р О В А Н И Е [ Г Л . III

ком ан д, т. е. приведение переменных команд к состоянию, исход

ному д л я первого цикла.

Получим программу.

П р о г р а м м а 20

Ч и с л а К о м а и д ы

§ 4] Ц И К Л И Ч Е С К И Е П Р О Ц Е С С Ы , З А В И С Я Щ И Е О Т П А Р А М Е Т Р О В 119

«1 1 п ft + 1 X “ l a l CO —|— 1

“2 1 ft 4 - 2 4 - «1

“2 «1

<*3 N f t + 3 0 ft 4 - 1 p ft 4 - 1

СО -f- 1 I2 ft 4 - 4 «i «3 ft 4 - 1

• ft 4 - 5 Ba P CO -j- 1 r 4 - 1

СО + N N 2 ft-f- б Bo 3 со —f - N

р c b III А

Д л я проверки окончания вычислений мож ет быть т а к ж е использована переменная (к + 1) -я команда, вид которой в начале последнего (N-vo) цикла известен:

ft + 1 X «і <*i co + yV

Поместим теперь в ячейку а 3 код, соответствующий ком анде (к 4- 1), а (к 4- 4 ) -я ко м ан д а зам ен яется командой

ft 4-4 < ft 4-1 «3 к 4-1 Получим п рограмму.

П р о г р а м м а 20х

Ч и с л а К о м а и д ы

С| 1 ft 4-1 X a i «1 CO -j- 1

°2 ^I ft+ 2 4- “i «2 «1

CO -j- 1 I2 ft 4- 3 0 ft 4-1 P ft + 1

• ft⁺4 ft 4-1 _«3 ft + 1

С0 + N N 2 ft 4- 5 ^{B a} P CO + 1 r + 1

р 1 ft 4- 6 ^{B 6} 3 ^с⁰ ^N

Оз _' X «1 а1 со -f- N ft -f- 7 ^{oc m.}

120 Э Л Е М Е Н Т А Р Н О Е П Р О Г Р А М М И Р О В А Н И Е [ Г Л . III

Пример 4. Вычисление значений многочлена с применением команды переадресации. Построим п рограм м у д л я прим ера 2 этого п а р а г р а ф а , воспользовавшись командой п ереадресации.

Р асп о л о ж и м теперь коэффициенты многочлена я 0, а и . . . , а п и х в яч ей ках З У

ш, а -4-1, а 2, . . . , а- \ - п , я

•соответственно; тогда ком анда с номером N 4- 2к п рограм м ы 19 зап и ш ется так:

4- О) й

I t

^(!)

а первая ком анда примет вид ее нечетных команд.

Вычисления значений многочлена, таким образом , мож но р азб и ть па циклы, состоящие пз команд

N + 2к — \

N 2ft-

X ^(О а (0

4- 0) а + ft <0

К о м ан д а N 4- 2к имеет переменный второй адрес, который при переходе от цикла к циклу долж ен быть увеличен на ед и ницу. Д л я построения циклической программы дополним ко

манды N 4- 1, /V + 2 yV + 1

N + 2

X (0 а (0

+ 0) ОС 1 (!)

ком ан дой переадресации

N + 3 0 N 1М ^{N + 2}

где в ячейку {3,i помещено вспомогательное число Рч

Ц И К Л И Ч Е С К И Е П Р О Ц Е С С Ы , З А В И С Я Щ И Е О Т П А Р А М Е Т Р О В 1 2 1

Д л я окончания расчетов воспользуемся тем ж е счетчиком, что и в предыдущей программе, чем програм м а цикла будет заверш ена.

Однако для возможности повторных вычислений по данной п рограмме ее следует пополнить командой (ие входящей в цикл), восстанавливающ ей исходное состояние переменной (А/ + 2) -и команды.

Это можно сделать двум я различны ми способами.

1. Восстановление переменной ком анды программы с по

мощью команды переадресации. Д л я восстановления к исход

ному виду (N + 2)-й ком анды выполним после окончания цикли

ческого процесса ком анду

Ө N -f - 2 Ps N + 2

где в ячейку З У (Зг, помещено вспомогательное число

Рз п

Получим программу.

П р о г р а м м а 21

Ч и с л а К о м а и д ы

Л' N _Рз Рч Рз

(О «0 / ( * ) N + 1 X ^to «1 <0

a -f- 1 «1 ;V + 2 + (0 а + 1 (0

а + 2 а 2 Л' + З 0 N + 2 Р. ЛГ + 2

• yV -f-4 _Рз _Рг N

а —|— ti а п Лг -f- 5 ө N + 2 Рз N + 2

Р. 1 Я + С ост.

Рз п

Р2 п

и ⁰ ^k

р., 1

122 Э Л Е М Е Н Т А Р Н О Е П Р О Г Р А М М И Р О В А Н И Е [ Г Л . III

Ч исло используемых в программе ячеек мож ет быть у м ень

шено, если в качестве единицы д ля счетчика — ячейки |3.$ — при

нять единицу второго адреса — ячейку (Зі, и в качестве кон

с та н ты для сравнения So — соответственно константу (З5.

П р о г р а м м а 21j

Чи с л а Ко м а н д ы

«1 ^{Л '} N ₊ _Рз _Р. _Рз

О ) «0 / ( * ) N + 1 X 0) «1 ^О)

0 + 1 ^{я ,} N + 2 _■ь (I) а + 1 (0

• ^N^{+ 3} ^/V⁺² ^Pi ^{N +}²

С£ + П ЛГ + 4 _Рз _р2 N

Р. ¹ ^{/V + 5} ^Ө ^N⁺ ² Рг ^ЛГ⁺ ²

Р2 ^п ^{7V + 6} ^ост.

Рз ⁰

2. Восстановление переменной команды с помощью зас ы л ки в ее адрес соответствующего кода.

Поместим в ячейку З У (3 вспомогательное число -Ь (1) а + 1 0)

и дополним п рограмму из ком анд N, N + 1, N + 4 т а к н а зы ва ем о й командой засылки:

0 Р ЛГ + 2

В результате выполнения этой команды п рограмма, с о д е р ж а щ а я переменную команду, приобретает исходный вид, пригод

ный д ля повторных вычислений по пей. При этом, разумеется, перед началом повторных вычислений н а д л е ж ащ и м образом д о л ж н ы быть подготовлены т а к ж е и числа.

§ 4 ] ЦИКЛИЧЕСКИЕ ПРОЦ ЕСС Ы, ЗАВИСЯЩИЕ ОТ ПАРАМЕТРОВ 1 2 3

П р о г р а м м а 22

Ч и с л а К о м а и д ы

«1 ^X N 4- Рз Pi Рз

О ) «0 / И N + 1 X ^со «1 ^(О

а —1 «1 N -1-2 + ^ы ^{а -f- 1} ^О)

л ^ДГ⁺ ³ ⁰ ^N+ ² _Р. N + 2

а-\-п _«я _{W + 4} _Рз _Р₂ _N

Р> 1 _{N + 5}

0 Р ^N+ ²

Р2 ' п _{N + 6} _ост.

Рз 0

Р 1 + (О а —{— 1 ш

К а к в первом, т а к и во втором случае к ом ан да восстановления м о ж ет быть разм ещ е н а перед ком ан дам и цикла. В первом слу

чае в связи с этим надо н а д л е ж а щ е изменять соответствующую переменную команду. Во втором — безразлично, какой код по

мещен в эту ячейку. Таким образом, по количеству вводимой информации второй способ восстановления переменных команд более рациональный. Кроме этого, в случае возм ож ны х сбоев в работе машины второй способ ока зы в ае тся т а к ж е эф ф екти в

нее: внесенная константа на место искаженного кода команды в осстанавливает его к истинному виду, тогда к а к по первому способу появившийся сбой в переменной ком анде командой восстановления пе будет устранен.

П ро гр ам м а 22 м ож ет быть сокращ ена, если воспользоваться тем обстоятельством, что окончание расчетов д о л ж н о произойти

после того, когда ком ан да N + 2 примет вид

4~ О) а -f- п <i>

Таким образом, из программы 22 можно выбросить ко

манду N (и ячейку рз), а д л я выяснения окончания расчетов и передачи управления н ачалу нового цикла использовать сра вн е

ние переменной команды с постоянной, соответствующей коду 7.

П р о г р а м м а 221

Ч и с л а К о м а н д ы

124 Э Л Е М Е Н Т А Р Н О Е П Р О Г Р А М М И Р О В А Н И Е [ Г Л . III

«I X А -+ 1 со «1 0)

О) Яо / ( * > А '+ 2 + 0) а + 1 0)

а -{- 1 «1 Лг + 3 Ө N 2 р. Л '4 - 2

•

N + 4 < N 4 - 2 Т Л Г4-1

a -f- П «я N - Ь 5 Ө А 4 - 2 Р» N 2

N + 6 ост.

Pi ¹

?‘2 п

7 J -1 (0 а - п <>>

П оставленн ая з а д а ч а мож ет быть решена иначе путем в ы д е

лен и я так называемой стандартной ячейки. Л именно, выделим станд артн ую ячейку З У 3, в которую в начале к а ж д о г о t-ro цикла вычислений будем последовательно заносить ко э ф ф и циенты а п i = 1, 2, . . . , п, с помощью команды переноса

Н~ а 4 - / 0

(н ач ал ьное состояние ячейки о безразлично).

Первый адрес этой команды — переменный, в связи с чем п рограмму цикла дополним командой переадресации

(* * ) 0 ( * ) Р. ( * )

где в ячейке З У (Зі помещ ается <:1» IIА. Н ачальн ое состояние команды ( * ) д олж но быть следующим:

( * )

+ а 4 - 1

^В

§ 4] Ц И К Л И Ч Е С К И Е П Р О Ц Е С С Ы , З А В И С Я Щ И Е О Т П А Р А М Е Т Р О В 1 2 5

К ом ан ду (-Х-) поместить после команды в последнем случае в ячейке З У а 4- 1 вначале д олж н о быть помещено число а и а в первом адресе команды ( ) — номер а + 2.

П р о г р а м м а 222 Ч и с л а

а X

« 4 - 1 _{й \}

а -{ - п ап

(0 ^(I^q / ( х )

0 ^{рабочая}

Pi 1

р2 + ос -j— ^ 5

Рз ^4_ « 4 - 1 ^?>

N + 1

N + 2

N -f- 3 N 4- 4

Аг 4 - 5 N 4 - 6

К о м а и л ы

+ а 4 - 1 0

X ⁰⁾ а (0

+ ^о) 0 со

Ө ^N Р. ^N

< N р2 ^N

0 Рз ^N

ост.

Здесь д ля выяснения окончания циклического процесса нами использована переменная ком ан да программы. П оследняя про

грам м а имеет одной командой больше; однако во многих слу

чаях такое осуществление программы д л я циклического процесса, зависящ его от п арам етра, бывает удобным и приводит к зн ачи тельному сокращению программы. Следующий пример приведен с целыо иллюстрации данного положения.

Пример 5. Вычисление суммы s =

у

^{х) + л}

х У х , ( * 1 - а )

Вычисления естественно рас п а да ю тся на /?. циклов: в /г-м цикле (к — 1, 2, п) вычисляется /г-е сл агаем ое

Ak X/. V х к( хк — а)

и прибавляется к сумме предыдущих слагаем ы х s k . Очевидно, команды, осущ ествляю щ ие вычисления, в ка ж д о м из циклов будут зависеть от номера ц икла.

Д л я построения циклической программы разм естим д ан ны е следующим образом:

1 2 6 Э Л Е М Е Н Т А Р Н О Е П Р О Г Р А М М И Р О В А Н И Е [ Г Л . I l l

К® ячейки a -f- 1 а + 2 . . . а - \ - п Р

Е е со дер ж и м о е *1 х п а

и выделим оперативную ячейку о д л я накопления суммы, в ко- которую вначале поместим 0.

П р о гр а м м а вычислений на /г-м цикле будет след ую щ ая:

N + 1 X a -f- к а 4~ к (01

Хк I, И

N + 2 X (01 а 4 - к «1 Ж3_А1 II

N + 3 + <„1

Р

а)1 х :1 + а

А '-Ь 4 V а 4 - к ы2 v ~ k I

ЛГ-f- 5 X «2 а 4" к С02 x k Y ~ k 11

Л Г + 6 — a -f- к

Р

^м3 ^{х к — а} ^I

N + 7 X О) 2 _«3 (lb х к У Т к ( х к — а)

N + 8 : О), а>2 0), л к

7V 9 + О) (О, Cl) Sk

Зд ес ь справа в таблице у казан ы адреса команд, зав и ся щ и х от п а р ам етр а — номера цикла.

В связи с наличием переменных адрссов п рограм м а цикла д о л ж н а быть пополнена соответствующими ком андам и переад- ресации. При этом легко заметить, что число констант п ер еа д р е

сации мож ет быть уменьшено, если, воспользовавшись ко м м у тативностью операции умножения, I и ІІЛ команд N + 2 и N + 5 переставить местами.

Д л я выяснения окончания расчетов воспользуемся одной из переменных команд, например (N 4 - 2 ) -й, д л я чего в ячейку З У 7 поместим соответствующую вспомогательную константу

X «1 (X —|— и 0)1

П рограм м а будет иметь вид:

П р о г р а м м а 2 3

Ч и с л а К о м а н д ы

§ 4 ] Ц И К Л И Ч Е С К И Е П Р О Ц Е С С Ы , З А В И С Я Щ И Е О Т П А Р А М Е Т Р О В 1 2 7

а + 1

Х\

^Аг⁺¹ ^А

а

^{+ 1} а -f- 1 ^со.

„ J О

« Г - Д'2

N +

² ^X « 4 -1 «1 »1

N

^{+ 3} + 0), _р со,

« /I

Хп N

^{-f- 4}

V

^{а + 1} ^СОо

р а N

^{-f- 5} ^X ^{а 4~ 1} ⁰⁾² ^со2

О) 0

N

^{-I- Г)} ^— ^{« 4 - 1} Р С°3

(0,

N

^{+ 7} ^X ^со2 ^с»3 ^со2

{t>2 рабочие

N

^{+ 8} ^о), ^СО² ^СО,

N

^{-{- 9} + со СО, СО

7 X а -)- п <0, <*>,

N

^-!-¹⁰ ®

N

^{4- 1} 7i

N

⁺¹

7 i 1 1 ЛГ + Н ©

N

^{4- 2} 72

N

^{4 - 2}

72 1 W + 1 2

N

^{4 - 4} 72

N

^{4 - 4}

N

^4-13 0 Л7 4~ 5 ₇₂ ЛГ + 5

Л' + 14 © А + 6 ₇₂

N

^{4 - 6}

7 V + 15 / V + 2 72 / V + 1

N

^4-16 ^ост.

Если по данной программе возможны повторные вычисления, например в том случае, когда д а н н а я группа ком ан д явл яется промежуточным этапом вычислений внутри некоторого другого ц икла, то она д о л ж н а быть дополнена соответствующими пятью ком ан да м и восстановления, а совокупность чисел — н а д л е ж а щими константами восстановления.

В оспользуемся теперь приемом засы лки в стандартную ячейку. С этой целью выделим стандартную ячейку З У (оп ера

тивную) 5 и дополним цикл командой переноса

"Т*Г а + 1 0

1 2 8 Э Л Е М Е Н Т А Р Н О Е П Р О Г Р А М М И Р О В А Н И Е [ Г Л . III

Теперь ком анды N + 1, N + 2, N + 4, /V + 5, JV + б становятся не зав и ся щ им и от п ар ам етр а и вместо пяти ком анд п е р е а д р е с а ции в п рограм м у следует включить команду

Ө N ъ N

В месте с тем отпадает надобность в константе переадресации.

П олучим программу.

П р о г р а м м а 23х

Ч и с л а К о м а н д ы

а —{— *1 а + 2 -V2

а + п X tl

Р а

со 0 5

со.

со2 ^■^{рабочие}

0>з

Ti 1

Ь + а + П 0

N + а + 1 О

N + 1 X о 0 со,

N + 2 X 0 со. «1

дг + з + со, _р со,

N + 4 V О со2

W + 5 X 0 со2 ^{СО 2}

N + 6 — г> р ^со3

N + 7 X ^С|)2 С°3 (Og

N + 8 : ш, ^С02 О),

N + 9 + ^(О ^со, ^со

W + 1 0 ө N ₇₁ N

ЛГ + 11 < N ₇₂ N

N + 12 ост.

Экономия в ячейках получается еще большей, если имеется необ

ходимость в восстановлении переменных команд. Зам етим, что в данной программе за счет изменения порядка вычислений мо

ж е т быть сэкономлена одна р аб оч ая ячейка.

Пример 6. Вычисление интеграла

/ = / у (ІХ, г д е у = * 1 + л; + Г ~ А: * ^ 6

П о формуле Симпсона

§ 4] Ц И К Л И Ч Е С К И Е П Р О Ц Е С С Ы , З А В И С Я Щ И Е О Т П А Р А М Е Т Р О В 129

I

^{У dx} = -г (Уо Н-4)»! -J- 2у2 + 4 у 3 + • • • 2 ^ - 2 + ^ 2 « - і + > '2«) (31) д ля заданного числа делений 2«; у ( х г), х t = х 0 + і/г,

^ __6 — а

~ ~ 2 п

Поскольку вычисления у t д л я всех значений i — 0, 1 , 2 , . . .,2 я могут быть выполнены с помощью одной и той ж е группы команд, представляется естественным предварительное вычисле

ние этих величин с запоминанием, после которого остаются вычисления по ф орм уле (31). О дн ако в таком случае понадо

бится 2п + 1 ячеек З У д ля зап ом и н ан ия величин у г

П р о г р а м м а 2 4

Ч и с л а К о м а и д ы

«, со2 (О -f- 1

р а б о  чие

к + 1 k + 2 k + 3 k 4- 4 к 4 - 5 к 4 - G к 4 - 7

к 4- 8 к + 9

X

^а ^а ^(О,

Р

^©1

«

2 (»2 «о

—

Р

^{« j}

V (О, ©1

—

<’>о

^{« j} ^О),

н ~

Р

^а ^ю²

(О, о) 4-1

+ а 7 а

1 + 4

(-4)

1+.V, УI ХІ+ 1

Число ячеек, необходимых д л я зап ом и н ан ия величин г/£, мож ет быть значительно сокращено, если мы примем следую щую схему вычислений:

ДSi — ~0Г ІУ-2ІҺ + ^Уіі+І +3'2< + 2)>

s t- 4 - A s t-; i = 0, 1, 1; s0 = О, (32) I = s n.

9 Зак. 1166- Э л ем ен т ы п р о гр а м м и р о в а н и я

130 Э Л Е М Е Н Т А Р Н О Е П Р О Г Р А М М И Р О В А Н И Е [ Г Л . III

Теперь д л я перехода от вычислений величин у 2і, У²¹+²к ВЬІ' числению s t-+1 необходимо уд ер ж и в ать в памяти лиш ь величины s i> Учі> У21+1* УҺі+2' Вычисление по схеме (32) мож но разб и ть на р яд циклов: на t-м цикле вычисляется величина A sf и п р и б а в л я е тся к s r О бщ ее число циклов равно п.

Вычисление величин у 2і, У%і+\>> Уы+²> необходимых д л я под

счета Д-9;, в свою очередь можно выполнить с помощью ц икли ческой программы из трех циклов. Действительно, выделим д л я этих величин последовательность ячеек со + 1 , со + 2, со + 3.

Т огда п рограм м а (Л) д л я вычисления в ел и ч и н ыу 21 м о ж ет быть использована для вычисления y 2i.и и у21+2, если над командой, со д ер ж ащ е й адрес со + 1, произвести соответствующую п ер еа д ресацию. В связи с этим дополним программу (Л) командой переадресации

где

К ом ан ды

где

ft + 10 + к + 8 о к -f- 8

к -f-11 к + 1 2

• 1

< f t + 8 ° 2 ft + 1

+ 5 3 ft⁺ ⁸

: с о , ш 2 CD -f- 3

О ) , Ь>2 0 + 1

выполняют трехкратное повторение цикла и восстановление пе

ременной команды д л я повторных вычислений на следующем шаге. П оскольку па следующем шаге вновь понадобится вели

чина y 2i+1, введем в программу команду

k + 1 3 — a T a

восстанавли ваю щ ую необходимое значение аргумента. Д л я в ы яснения момента п рекращ ен и я расчетов воспользуемся извест

ным значением х на последнем цикле х — 1.

Получим программу. 2 4 ь П р о г р а м м а 24j

§ 4] Ц И К Л И Ч Е С К И Е П Р О Ц Е С С Ы , З А В И С Я Щ И Е О Т П А Р А М Е Т Р О В 131

Ч и с л а К о м а н д ы

а Хо к + 1 X ^a ^a ^CO,

р ¹ к + 2 4 - P CO, CO2

7 Һ к -f- 3 V ^<■>2 w2

СО, ft+ 4 — P , w, 0>|

со2 ft 5 V CO, <0,

(1) -f- 1 У 21 ft+ 6 — co2 <0, <0,

to -{- 2 У2І+1 f t + 7 4 - p a (i>2

СО — 3 У2І+2 ft+ 8 CO, (■>2 (l) 4' 1

1 ft+ 9 4 - a 7 a

о2 СО, _«2 СО -{— 3 ft - f 10 0 ft 4- 8 5. ft + 8

^3 СО, со2 « 1 ft 4 - 1 1 ft-I- 8 r,2 ft 4 - 1

р. 4 ft-fr 12 0 03 ft 4 - 8

Рй ^Л/3 ^ft⁴^{- 13} — a 7 a

Рз ⁰ ft -b 14 X ^<o⁴^*² P. CO,

ft H- 15 4 - CO, <•> -f- 1 со, ft + 16 4 - CO, <o 4 - 3 o>,

ft -f- 17 X ^CO, P2 CO,

ft 4- 18 + Рз ^CO, Рз

ft 4 - 1 9 < a P ft 4 - 1

ft 4 - 2 0 /7 Рз

ft 4 - 2 1 ocm.

1 3 2 Э Л Е М Е Н Т А Р Н О Е П Р О Г Р А М М И Р О В А Н И Е [ Г Л . III

Н едостатком приведенной программы является то, что величина У п ь исп ользован н ая на і-м шаге (как содерж им ое ячейки

<о + 3) и в стреч аю щ аяся в расчетах на (г + 1)-м шаге (к ак сод ерж им ое ячейки го-1-1), каж д ы й раз повторно вычисляется д л я всех хI = л'о 4- ill, на что расходуется рабочее время м а шины. Кроме того, наличие переменной (к -f 8) -й команды в л е чет за собой работу команд к + 10 переадресации и к -f 12 вос

становления и т а к ж е требует соответствующего зап олн ен ия ячеек 5i, о3.

В связи с изложенным примем следующий прием построения п рограм м ы , так назы ваемы й прием «циркуляции величин в ста н д ар тн ы х ячейках».

Поместим вычисляемое значение у в ячейку о> 4- 4 и введем в п рограм м у команды переноса

к 4 - Ю + а>+ 2 0> -f- 1

ft 4 - 1 1 4~ со -J- 3 со -j— 2

ft 4 - 1 2 4 - <о -j- 4 О) -f- 3

или

Г П s<.) 4 - 2 3 О) 1

и команды

к -|- 13

к 4 - 14

— (1 (1

0 ft 4-1

где в ячейку о вначале помещается код «—0», обеспечивающий д вукратное повторение цикла. Теперь отпадает надобность в ком ан дах переадресации и восстановления, а т а к ж е в ком ан де к + 13 и высвобождаю тся ячейки, использованные в качестве вспомогательных констант. Получаем программу 242.

Ц И К Л И Ч Е С К И Е П Р О Ц Е С С Ы , З А В И С Я Щ И Е О Т П А Р А М Е Т Р О В 133

П р о г р а м м а 24а

Ч и с л а К о м а и д ы

а л'о

о 1

7 Һ

*>,

СО,

< 0 + 1 У 2/

■СО 4 ~ 2 У2/+І

<0 ~ 3 Уо У 2 /+ г

0 —0

0Pi 4

V2о п 3

^3 0

А + 1 X ^а ^а ^со.

А + 2 4- Р О), со2 j

А 4 - 3

V

^(л)

2

^{СО 2}

k -f- 4 — И ^со, ^со,

А 4 - 5

V

^со. со,

/г -(- 6 — со2 0), 0),

А 4 - 7 4 р а С02

Л+ 8 со. 0)2 со 4 - 4

Л+ 9 4 ^а 7 а

4

^{- ю} 4 ^{со 4 - 2} ^СО4 “ 1

А 4 - 11 -т- со

4

^{~ з} со+ 2

к 4 - 12 4 ^{со 4 “ 4} ^со^{4 ~ з}

/г Н- 13 — 5 0

к + 14 <■ 0 А 4 - 1

к + 15 X ^со4" 2 j р , со.

к 4 - 1C) 4 со, с о 4 ~ 1 со,

/с 4 - 1 7 1 со, <.. 4 - з <■),

А 4 - 18 X ^со. ^ОlJ2 со,

А 4 - 19 4- ^Рз ^СО, Рз

А 4 - 20 < а р к 4-1

А 4 - 2 1

п

Рз

А 4 - 22 ост.

По д а н н о й п р о г р а м м е в ел и ч и н а у 0, н е о б х о д и м а я д л я в ы ч и слений на первом ш а г е , п р е д в а р и т е л ь н о вычисляется и п о м е щ а е т с я в я ч е й к у w-j- З . Во и з б е ж а н и е этих вычислений м о ж н о

1 3 4 Э Л Е М Е Н Т А Р Н О Е П Р О Г Р А М М И Р О В А Н И Е [ Г Л . I II

изм ен и ть ко м ан д ы , у п р а в л я ю щ и е п овторени ем в н у т р е н н е г о ц и к л а , так и м о б р азо м , чтобы вн утре н н и й цикл на первом ш а г е вы п о л н ял ся три р а з а , а на п о с л е д у ю щ и х ш а г а х — д в а р а з а .

П р и в ед ем од н о из в о зм о ж н ы х построений т а к о г о р о д а . П оместим в я ч е й к у о в ел и ч и н у «3» и вместо к о м а н д & + 1 3 >

/ г + 1 4 д о п о л н и м п р о г р а м м у к о м а н д а м и

k + 13 — 0

£ + 14 < Ъ А + 1

* : + 15 + й2 ь

гд е в я ч е й к у о2 п ом ещ ен о число «2».

К о м а н д а к -j- 15 в о сста н а вл и в ает со д е р ж и м о е яч ей ки о к в и д у , н е о б х о д и м о м у д л я выполнения вычислений, п о с л е д у ю щ и х за первым циклом . В таком с л у ч а е н ач ал ь н о е за п о л н е н и е я ч е й к и ш + З н есу щ еств ен н о .

Пример 7. Сдвиг последоват ел ьн ости чисел av а2, . . . , ап.

Ч и с л а а х, а 2, . . . , а п (в м а ш и н е с ф и кси рован н ой зап ятой ) с д в и н у т ь влево на т а к о е число р а з р я д о в (одно и то ж е д л я в сех чисел), чтобы по край н ей м ере одно из них стало по м о д у л ю б о л ь ш е или рав н о .

Р е ш е н и е п оставленной з а д а ч и р а с п а д а е т с я на р я д ц ик лов, в к а ж д о м из которы х д о л ж н о быть п роверен о усл ов и е

1 < < < и ) = л ( а 1 < ^ ) л ••• Л Р , ( а , < | ) . (33) и если это услови е выполнено, г р у п п а чисел с д в и га ется на один р а з р я д влево. При невыполнении услови я (33) расчеты п р е к р а щ а ю т с я .

В д ан н о м прим ере число ц ик лов з а р а н е е не известно. П р о в е р к а услови я, о п р е д е л я ю щ е г о число циклов, д о л ж н а п р о и зв о д и ть ся в н а ч а л е ц ик ла, так ка к возм ож ен сл у ч ай , к о г д а число ц и к лов о к а ж е т с я равным нулю . К ак мы имели в п рограм м е 9, в таком с л у ч а е цикл д о л ж е н быть д опол н ен в кон ц е ко м ан д о й б езусл ов н ой п ер ед ач и у п р а в л е н и я его первой ком ан де.

Поместим в яч ей ки З У alt а2, . . . , ап величины a v . . . , а п соот

ветственно, в я ч е й к у р — число І . Т о г д а п р о гр а м м а р е ш е н и я поставленной з а д а ч и п р ед став л ен а п рограм м ой 25.

П р о г р а м м а 25.

Ч и с л а К о м а н д ы

§ 4] Ц И К Л И Ч Е С К И Е П Р О Ц Е С С Ы , З А В И С Я Щ И Е О Т П А Р А М Е Т Р О В 135

«1 «1 N 4 -1 1<1 Р «1 /V 4 - 2п 4 - 2

«2 «2 ^{N 4 - 2} 1 < 1 Р а2 N + 2/1 4 - 2

• • _\

ап ап N п 1<1 Р ап А 4 - 2« 4 - 2

Р ₂¹ ^N 4- п 4~ 1 * «1 Р

N 4 - л 4- 2 «2 Р Ctj

N + 2/1 *<1 ¹

N4 - 2/1 4 - 1 К 1 / V 4 - 1

N 4 - 2п 4 - 2 ост.

Команды /V + 1 -г- N 4- п осущ ествляют проверку выполнения сложного условия (33); команды /V + п + 1 н- N + 2п выполняют сдвиг группы ячеек а 4- 1, . . а 4- п влево на один разряд. Из математической логики известно соотношение

P j A P o A . . . А Р п = Р , V P 2 V . . . V Ptl,

иллюстрирующ ее то обстоятельство, что невыполнение сложного условия Р = / \ P j возможно лиш ь при условии невыполнения одного из элементарны х условий Р\, Ро...Р п.

Это наглядно иллюстрируется группой команд N + \, . . . . . . , N + п. П ередача управления на ком анду N 4 - 2 « + 2 в оз

м ож на лиш ь при невыполнении по крайней мерс одного из э л е ментарных условий P i ...Рп ,

Если теперь величины а и « 2, • • а п разм естить в последова

тельность ячеек, номера которых об разую т арифметическую прогрессию, например в последовательность а 4 -1 , а 4-2, . . . . . . , а 4- п, то д ля каж дой из групп команд N + \ - i - N + n и N 4- п 4- 1 N 4- 2п могут быть построены циклические про

гр ам м ы с одинаковы м числом циклов, равным п.

1 3 6 Э Л Е М Е Н Т А Р Н О Е П Р О Г Р А М М И Р О В А Н И Е [ Г Л . I II

П р о г р а м м а 252

Ч и с л а • Ко м а и д ы

a -f- 1 a\ N + 7

а + 2 а г N + 1 + 7 7i i

iV + 2 К І Р а+ 1 N + 13

а + п _«я А + 3 ₀ N + 2 Һ Лг + 2

Р 1

2 ЛГ + 4 _{• | < 1} 7 72 Л ' + 1

7 ⁰ N -f- 5 ₊ — — 7

Ti ¹ ЛГ + 6 + 7 7i 7

72 n ЛГ + 7 • а+ 1 Р а + 1

5i ¹ N + 8

82 1 1 ЛГ + 9 K I 7 72 N + 6

а -(- 1 Р а + 1 Л Г + 1 1 ₀ — Лг + .7

А + 12

К ! N

ЛГ + 13 ост.

Преимущ ество последней программы состоит в том, что она сод ерж и т небольшое количество команд, которые не за в и с я т от количества рассматриваемы х чисел в группе. З а ви си м ы м от этого числа оказы вается лиш ь содержимое ячейки 72, с о д е р ж а щей константу д л я сравнения счетчика 7. О дн ако в отличие от предыдущ их программ д а н н а я программа имеет переменные команды , в связи с чем д л я вычислений ее команды д о лж н ы быть помещены в оперативную память.

Пример 8. Проверка выполнения неравенств я 0> 0, « і > 0 . . .

« „ > 0. Пусть дан а последовательность величин а і (і = 0, I, 2, . . . , п ) ка к функций параметров к\ и вида

a l — (34)

Проверить выполнение неравенств

(35)

Ц И К Л И Ч Е С К И Е П Р О Ц Е С С Ы , З А В И С Я Щ И Е О Т П А Р А М Е Т Р О В 137 При этом требуется в случае, когда условие (35) не выпол

няется, н апечатать условный знак, и если оно выполнено, пере

д а т ь управление некоторой команде.

Р асп ол ож и м дан ны е парам етры в ячейку ЗУ:

ячейки С о держ ан и е

Г + І «/0

S - р / а п

t + І «/2

р 4-1 Р/

<1 + 1 'ІІ

v - | - i Ч

Проверка указан ного условия (35), естественно, разби вается на ряд циклов: в г-м цикле, і = 0, 1, . . . , п, определяется знак коэффициента уравн ен ия a L. Если a t > 0 и І < п (проверка не

обходимого призн ака еще не зак о н ч ен а), управление передается следующему циклу. Если а1 О (что о зн ач ает невыполнение указанного усл ов и я), печатается условный зн а к и вычисления п рекращ аю тся. Наконец, если сң> 0, і = п, управление пере

дается согласно условию ком анде N.

Цикл, естественно, дополняется соответствующими ком ан д ам и переадресации, обеспечивающими н а д л е ж а щ е е состояние

памяти при переходе от цикла к циклу. Д л я сокращ ения числа ком анд в многочленах (34) предварительно сделаны возможные вынесения за скобки, а именно, вычисления коэффициентов a t

ведутся по ф орм ул ам

й / = й / 0 + (a ll Pt^2 “Ь Т J ll) “Ь /‘’г (а <2 Н~ о), І — 0 , 1 , . . . , 11.

П р о г р а м м а 2 6

Ч и с л а К о м а и д ы

т + 1 aio к 4 - 1 X Р Ч О»,

S - г І ап к + 2 + S (О, О),

І + І а i2 к + 3 X <1 6| 0)2

Р 4* i Р/ к -Ь 4 4 - <0, <о2 (.)[

•<? 4 - i ІІ М - 5 \ /

А О», £ | <1>,

138 ЭЛ ЕМЕНТАРНОЕ ПР ОГР АММИРОВАНИЕ [ Г Л . III

Ч и с л а К о м а н д ы

1* -f- І Һ * 4 - 6 + г со, О),

е 1 к, к -f- ! X ^V е2 СО2

е2 *2 к 4 - 8 + t (|)2 0>2

условный

знак к 4 - 9 X е2 «2

д ^IА ^{* 4 - 1 0} ^-f- ^<0, ⁽⁰² ^(О,

е X р + п е2 10, * 4 - 1 1 0 * 4 - 1 д * 4 - 1

* 4 - 1 2 0 * 4 - 2 д * 4 - 2

* 4 - 1 3 0 ^{* 4 - 3} д * 4 - 3

* 4 - И 0 ^{* 4 - 6} д * 4 - 6

* 4 - 1 5 0 ^{* 4 - 7} д * 4 - 7

* 4 - 1 6 0 ^{* 4 - 8} д * 4 - 8

* 4 - 1 7 О), — * 4 - 2 0

* 4 - 1 8 < * 4 - 1 6 ^{* 4 - 1}

к 4 - 19 — — N

* 4" 20 П _*1

* 4 - 2 1 ост.

Зд ес ь мы имеем пример циклического процесса, за к а п ч и в а ю щегося по слож ному логическому условию: либо на г-м цикле, і = 0, 1, п, по признаку — коэффициент a t <1 0, либо на п-м цикле по счетчику, если a t > 0 для всех i = 0, 1, . . п.

П ри этом в зависимости от способа окончания циклического процесса управление передается разным командам.

В ы в о д ы

1. Цикличность программ вычислительных процессов, з а в и с я щих от п арам етров, достигается б ла года ря упорядоченному р а з мещению в ячейках З У зависящ их от п арам етров величин к применению ком анд переадресации.

В Л О К - С Х Е М Н О Е П Р О Г Р А М М И Р О В А Н И Е 1 3 9

2. П рограм м ы циклических процессов со д ер ж ат команды, подготавливаю щ ие в каж д ом цикле заполнение чисел З У и пере

менных команд д л я выполнения следующего цикла.

3. Д л я построения логических условий, определяю щих окон

чание параметрических циклических процессов, могут быть ис

пользованы переменные команды программы.

4. Д л я повторного применения изменяемой циклической про

грам м ы необходимо предусматривать восстановление перемен

ных команд. В таком случае в п рограмму вводятся (пе в ходя

щие в цикл) команды восстановления, которые осуществляются:

а) с помощью операции переадресации, б) с помощью засылки в адрес переменной команды соответствующего кода. Впрочем, восстановление переменных команд мож ет осущ ествляться пу

тем операции повторного ввода всей программы из внешнего во внутреннее ЗУ.

5. В результате применения операции засы лки зависящ их от п арам етра величин в стандартны е ячейки вычислительная часть программы мож ет быть сделан а неизменной; при этом во многих случаях уменьш ается число переменных ком анд программы, чем достигается экономия в ячейках ЗУ.

У п р а ж н е н и я

1. Составить циклическую программу для вычисления суммы

І = 1

2. Составить программу для вычисления значении многочлена с п ереда

чей управления от цикла к циклу командой « = :•>, или «УПЧ», или «УПП».

3. Составить программу для вычисления интеграла

г /* , X Sin X

J у ' гдс у = т + ^ '

по формуле Симпсона для различных видов условных передач управления.

4. Составить программу для рассмотренного в тексте примера 7 (про

грамма 2 5 |), используя для окончания внутренних циклов зар ан ее известный вид переменных команд.

5. Составить программу для рассмотренного в тексте примера 7 в сл у

чае, когда число сдвигов учитывается (с запоминанием м асш таба) для м а

шины с условной передачей управления по числу; для машин с операцией условной передачи управления по неравенству.

§ 5. Блок-схемное программирование и передача управления на подпрограммы

При составлении программ д ля сложны х зад ач удобно поль

зоваться разбиением программы на так н азы ваем ы е блоки.

Б л о к о м н азы вается такой участок программы, к которому п еред ач а управления от других блоков в озм ож н а лиш ь к его

140 Э Л Е М Е Н Т А Р Н О Е П Р О Г Р А М М И Р О В А Н И Е [ Г Л . ИГ

первой ком анде и передача управления от которого другим б лок ам в озм ож н а лиш ь от его последней команды. Внутри б лок а д опускаю тся передачи управления как условные, т а к и б езусл ов

ные, не связан ны е с выходом на другие блоки.

По блокам вначале составляется блок-схема программы, на которой д ля наглядности стрелками у казы в аю тся в о зм о ж н ы е переходы между блоками, а затем последовательно с о с та

вл яю тся программы для всех блоков. Удобно т а к ж е в м естах разветвлений на каж дой из стрелок указы вать условие, при ко

тором происходит передача управления к данному блоку.

При блок-схемном программировании можно достичь сущ ест

венного сокращ ения программ за счет выделения групп ком анд, повторяю щ ихся в процессе решения задачи, в отдельные блоки.

Так и е повторяющиеся группы команд принято н азы вать подпро

грам м ам и . Наличие специальных команд передачи уп рав л ен и я на подпрограммы облегчает их повторное использование при программировании.

Если д а н н а я группа ком анд представляет интерес с точки зрен и я решения многих задач, то такие тщательно проверенные подпрограм мы удобно хранить в виде библиотеки па с п ец и ал ь ных перф окартах или перфолентах или иметь в памяти в виде станд артн ы х (быстропаборных) блоков во внутренней части З У или в специально отведенных местах внешней памяти. При составлении новой программы библиотечные подпрограммы м о гут включаться в нес как часть, не требую щ ая повторной про

верки, что весьма сок ращ ает время ввода и проверки программы . Пусть после команды к .основной программы требуется пе

рейти к выполнению некоторой подпрограммы, к оторая з а н и мает т ком анд и зад ан а в условных адресах 1, 2, . . . , т. Мы м ож ем просто включить подпрограмму в основную програм м у, сделав се первую команду ( / г + 1 ) - й командой основной про

грамм ы , в т о р у ю — (k + 2)-й и т. д. При этом д олж ны быть со

ответственно изменены, а именно, увеличены на величину к, те ад рес а «этой» подпрограммы, в которых указан ы номера к ом ан д (а не чисел) — адреса команд передач управления (ус

ловных и безусловных) и ком анд переадресации. Такое вклю че

ние подпрограммы в основную программу требует, во-первых, п реобразования команд подпрограммы и, во-вторых, при необ

ходимости повторных вычислений по подпрограмме приводит к повторению всех команд подпрограммы, соответственно уд ли няя программу.

Д л я тех же целей можно поступить иначе. Р азм ести м команды подпрограммы в фиксированных (свободных) яч ей ках З У от ti -1-1 до п + т и забронируем еще одну ячейку с номером п + т + 1, в которую поместим так назы ваемую ком анду в оз

вр а т а к основной программе. В ячейке к + 2 основной про-

граммы поместим команду безусловного перехода к подпро

грамм е

§ 5 ] Г . Л О К - С Х Е М Н О Е П Р О Г Р А М М И Р О В А Н И Е 1 4 1

БГІ и + 1

а п {к + 1) -й ячейке — команду, п одготавливаю щ ую ( « + т + 1)-ю команду д ля н ад л е ж ащ ег о в озврата к (к + 3 )-й ком ан де основной программы, например команду

0 тг п -f- in -f~ 1 j где 7 — номер ячейки, сод ерж ащ ей код

Б П к + 3

Приведем пример программы с неоднократно повторяемыми обращениями к п одпрограммам.

Пусть по группе ком анд Q производятся вычисления некото

рой функции от аргумента, сод ерж ащ егося в ячейке а, и при ре

шении задачи встречаются вычисления значений этой функции от двух различных аргументов, помещ аемых в процессе вычисле

ний в ячейки р и 7.

Рассмотрим детал ьн о блок-схему такой программы с выделе

нием группы ком анд Q в подпрограмму.

Обозначим группу команд, производящих вычисления до пер

вого обращения к подпрограмме Q, через А, группу команд, производящих вычисления меж ду первым и вторым обращением к подпрограмме, через В и последующие вычисления после второго обращ ения к подпрограмме через С: схема вычислений, таким образом, имеет вид

A Q B Q C . (36)

Пусть к а ж д а я из групп состоит:

А — из р команд;

В— из г ком анд;

С— из s команд;

Q — из т ком анд.

При выполнении вычислений без выделения подпрограммы Q п рограмма будет состоять из р + г + 5 + 2т команд. (В о зм о ж ные условные и безусловные передачи управления, пе с в я з а н ные с переходом на подпрограмму, которые могут встречаться

142 Э Л Е М Е Н Т А Р Н О Е П Р О Г Р А М М И Р О В А Н И Е [ Г Л . ' I I

внутри любой из указан ны х групп команд, в данном рас см отре

нии мы оставляем в стороне.)

Д л я автоматического выполнения вычислений на машине с выделением подпрограммы Q требуются дополнительные ком ан ды :

1) команды, выполняющие перед обращением к п одп ро

г р ам м е засы л ку аргумента, находящегося соответственно в ячей

ка х (3 и 7, в ячейку а;

2) команды, выполняющие переход к подпрограмме;

3) команды, выполняющие возврат от подпрограммы к д а л ь нейшим вычислениям по программе (к группам ком анд В — по

сле первого обращ ения к подпрограмме и к С — после второго).

В ы д ел яя особо эти команды, обозначим через а\ и Ь\

команды, осуществляющие засы л ку аргумента из ячеек р и | в специально отведенную для аргумента подпрограммы ячейку а;

а 2 и. Ь2 — команды, обеспечивающие н ад леж ащ ий в о з в р а т - и з подпрограм мы к основной программе; а 3 и 63 — команды б е з

условного перехода к 'подпрограмме.

Кроме того, в подпрограмму д о л ж н а быть введена перем ен

ная ком ан да q — команда «возврата» к основной программе, подгота вл и в аем а я командами а2 и Ь2.

Схема программы будет иметь вид

A a la 2azQ q B b xb.Jbi QqC. (37)

Число ком анд в программе, согласно (37), будет равно p + r + s + m + 7.

Дополнительно д ля подготовки команды в озврата понадо

б я тся две константы, коды которых соответствуют ком ан да м безусловного перехода к первой команде группы В или С; мы поместим их в ячейки 71 и 70. Н а блок-схеме (рис. 14) стрелкам и у к а з а н порядок выполнения команд; взаимодействие соответ

ствующих ком анд и команды «возврата» от п одпрограм мы к основной программе указано пунктиром. Выделенные ком анды в схеме приведены в развернутом виде в одном из в озм ож н ы х

вариантов.

В ячейках 71 и 72 помещены коды:

В принятом размещении команд в памяти подпрограмма Q помещ ается в ячейках N + 1, N + 2, . . . , N + т, где

р г -Ь s -J- 6«

Б П р + 4

Б П Р + г + 7

In document ЭЛЕМЕНТЫ ПРОГРАММИРОВАНИЯ (бет 116-181)