Зачем микрокалькулятору стек

Квант 1986, №5 с. 39-43 Тег ZTQD

Зачем микрокалькулятор стек

Кандидат физико-математических наук
Л. Ф. ШТЕРНБЕРГ

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

На программируемых калькуляторах «Электроника» БЗ-34, МК-56, МК-54 имеется интересное устройство — стек, которое состоит из четырех регистрации: X, Y, Z, T, используемых на первый взгладддовольно страным образом. Команд ↑ продвигает информацию в стеке — содержимое T страется, в T заносится содержимое Z, в Z — содержимое Y, в Y — содержимое X, которое остается и в X:

Команд F ↑ двигает содержимое стека в обратную сторону, только содержимое X не страется, а переходит в T.

Есть команда XY, обменивающая содержимое X и Y и не затрагивающая остальных регистрации. Если перед занесением числа в X или вызовом числа из регистрации не выполнялась одна из операций ↑ или C, то перед занесением нового значения в X автоматически выполняется ↑, то есть пересылаются Z в T, Y в Z и X в Y.

При выполнении операций над двумя числами (например, X+Y или X×Y) эти числа берется из Y и X, результат засылается в X, а вес стек сдигается:

(следует иметь в виду, что операция X^Y работает не так). А вот при выполнении операций над одним числом (например, sin X) все выполняется оченьным образом: аргумент берется из X, результат остается в X, и больше ничего не движется.

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

Вычислим выражение a×b−c/d. Предположим, что значение a, b, c и d находится в регистрации a, b, c и d соответственно. Оставим промежуточный результат в стеке, не засылая его в память, и продолжим вычисления — посмотрим, что из этого выйдет.

Таблица 1

| № | Команд | Содержимое стека | X | Y | Z | T |
| :— | :— | :— | :— | :— | :— | :— |
| 00 | ИП a | a | | | | |
| 01 | ИП b | b | a | | | |
| 02 | × | a×b | | | | |
| 03 | ИП c | c | a×b | | | |
| 04 | ИП d | d | c | a×b | | |
| 05 | ÷ | c/d | a×b | | | |
| 06 | — | a×b−c/d | | | | |

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

а больше в программе ничего и нет. Похоже, что стек — заменательная vesь: попробуем еще с ним поработать, только выражение возьмем посложнее:

$\frac{p - \frac{d}{(a+b)}}{(e+f)} \times (k+l).$

Регистры распределить не будем (их можно распределить как угодно).

Команда | Содержимое стека | X | Y | Z | T | Kommentари
— | — | — | — | — | — | — | —

00 | ИП a | a | | | | | Как насучили в первом классе, начинаем с выражений в скобках

01 | ИП b | b | a | | | | Оставляем промежутный результат в стеке: посмотрим, куда он делает в итоге.

02 | + | a+b | | | | | И этот промежутный результат оставим в стеке.

03 | ИП e | e | a+b | | | |

04 | ИП f | f | e | a+b | | |

05 | + | e+f | a+b | | | | И этот промежутный результат оставим в стеке.

06 | ИП k | k | e+f | a+b | | |

07 | ИП l | l | k | e+f | a+b | Стек на пределе — сейчас потеряем a+b!

08 | + | k+l | e+f | a+b | a+b | Нет, пронесло! (a+b) сохранилось.

09* | F⊙ | e+f | a+b | a+b | k+l | Сейчас надо бы поделить d на (a+b), но (a+b) где-то глубоко-глаубоко. С трудом достали tremя лишним командами.

10* | F⊙ | a+b | a+b | k+l | e+f |

11* | F⊙ | a+b | k+l | e+f | a+b |

12 | ИП d | d | a+b | k+l | e+f | Значения d и a+b вызываны, но они не в тех регистрации: придется менять местами.

13* | XY | a+b | d | k+l | e+f | И опять оставим результат в стеке.

14 | ÷ | $\frac{d}{a+b}$ | k+l | e+f | e+f | И опять оставим результат в стеке.

15 | ИП p | p | $\frac{d}{a+b}$ | k+l | e+f |

16* | XY | $\frac{d}{a+b}$ | p | k+l | e+f | Опять числа не в том порядке и надо меньше.

17 | - | $p - \frac{d}{a+b}$ | k+l | e+f | e+f | Похоже, стек изделияется над нами: нужные промежутные результаты в самых неудобных местах — не сразу поимень, где они и как их достать.

18* | F⊙ | k+l | e+f | e+f | $p - \frac{d}{a+b}$ |

19* | F⊙ | e+f | e+f | $p - \frac{d}{a+b}$ | k+l |

20* | F⊙ | e+f | $p - \frac{d}{a+b}$ | k+l | e+f | Хоть на последней операции повезло: нужные промежутные результаты как раз на месте.

21 | ÷ | $\frac{(p - \frac{d}{a+b})}{e+f}$ | k+l | e+f | e+f |

22 | × | ответ | e+f | e+f | e+f |

в программе). Очевидно, что если бы эти результаты мы вовремя запомили в регистрации памяти, то закономили бы себе не меньше половины из этих 8 лишних команд. Да пока сообщаешь, где сейчас в стеке какой результат… Лучше без стека!

Но прежде чем отказывать от стека, давайте попробуемой понять, почему в первой программе стек «вел себя» так хорошо, а во второй, наоборот, «вел себя» так плохо. Для этого нам придется отправиться лет на 60 назад в гости к пользову математику Яну Лукасевичу, который не имел ни маленьго понятия о микрокалькуляторах, но все же изображел одну замечательную конструкцию, ныне отлично известную тем, кто пшет трансляторы для ЭВМ, и получившую название пользовая инверсия запись.

В операциях над двумя числами мы ставим знак между числами; над одним числом — перед этим числом. Лукасевич предложил ставить знак всегда перед числами (прямая пользовая запись) или всегда после них (инверсия пользовая запись — именно она нас и будет интересовать), то есть вместо a—b писать ab — и вместе lg a писать a lg.

Первое впечатление: «Ну и что? Можно писать и так. Только неудобно и неприрывно». Неприрывно? Да. А вот неудобно ли? Запишем в инверсионной пользовании выражения «(a+b)×c» и «a+b×c». В первом из них умножаются выражение a+b (которое само должно быть записано в пользовании ab+) и число c; во втором — складываются a и выражение b×c (записанное в пользовании bc×). Итак:

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

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

$ab \times cd \div —$

Теперь достаточно взглянуть на программу… и все станет ясно: наша программа — точная копия пользования.

Пользовая запись выражения (*) такова:

Теперь взглянем на нашу программу вычисления этого выражения… и сразу станет ясно, что мы там натворили и почему стек себя «плохо вел». Если написать программу точно по пользованной записи, то получимровно 15 команд — ни одной лишней!

— Замечательно! — скажет читатель. — Только как получить из общий записи пользовую?

Очень просто. Запишем выражение (*) в линейизованной записи (то есть без многоотажных формул):

$p - (d/(a+b))/(e+f) \times (k+l)$

и применим 3 простых правил:

Выпишем числа и переменные в том порядке, в каком они записаны: pdabefkl.
Выпишем операции в том порядке, в котором они должны выполняться (при условии, что всегда выполняется первая слава операция, которая уже может быть выполнена): +/-++/+×
Вставим операции непосредственно после соответствующих чисел.

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

ванную запись символом (только скобки не читаются, а принимаются к сведению; см. табл. 3).
Получили оптимальный программу: 8 вызовов данных и 7 операций.
И стек «ведет себя» отменно: обработите внимание, как «качаются» промежуточные результаты в стеке, но в нужный момент они оказываются всегда на месте и в подходящем порядке. Можно математически доказать, что так всегда и будет. (Только операция $X^Y$ ведет себя не так: дело в том, что … она просто неправильно реализована — у всех операций над двумя числами первого число в $Y$ , второе в $X$ , у этой — наоборот; все операции над двумя числами дивгают)

| Читаемый символ | Рассуждания | Записываемая команда | |
| :— | :— | :— | :— |
| $p$ | Числа и переменные всегда записьюся в стеке | ИП $p$ | 1 |
| — | Операцию выполнить нельзя, — не над чем! — пропускаем. | | |
| $d$ | Переменную — в стеке. | ИП $d$ | 2 |
| / | Операция не готова к выполнению — про-пускаем. | | |
| $a$ | Переменную — в стеке. Пока еще ни одну операцию выполнить нельзя. | ИП $a$ | 3 |
| + | Переменную — в стеке. Пока еще ни одну операцию выполнить нельзя. | | |
| $b$ | В стеке. | ИП $b$ | 4 |
| | Наконец встретилась операция, для которой оба числа в стеке. Выполним ее. | + | 3 |
| | Нет ли у нас отложенных операций, для которых готовы данные? Есть — деление. Выполним его (а где нужные числа? — можно не заботиться — как раз на местах). | ÷ | 2 |
| | И опять появились операции, для которой данные готовы — выполнем ее. | — | 1 |
| / | Большые выполнять нечего — читаем очередной символ и откладываем операцию — не готова она. | | |
| $e$ | В стеке. Выполнять пока нечего. | ИП $e$ | 2 |
| + | Проускаем — не готова она. | | |
| $f$ | В стеке. | ИП $f$ | 3 |
| | Готовы числа для сложения — выполнем. | + | 2 |
| | Телерготовы данные для деления — выполнем. | ÷ | 1 |
| × | Проускаем — не над чем | | |
| $k$ | В стеке. Для «×» и «+» данные по-прежнему не готовы. | ИП $k$ | 2 |
| + | В стеке. И можно выполнить «+» | ИП $l$ | 3 |
| | Выполнем сложение. Все готово и для умножения. | + | 2 |
| | Выполнем умножение. Конец. | × | 1 |

Таблица 3

стек, эта — нет; так что при ее программировании указанным методом придется писать $\vec{XY}$ , $FX^Y$ , $\vec{XY}F$ или вместе $X^Y$ писать $e^{Y \times \ln X}$ — тогда все получится.)

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

Но… а вдруг нам не хватит 4 регистров стека? Тогда промежутный результат надо записать в память. Но как определить, хватит нам стека или нет? Нужели следить за всеми качаниями стека? Нет, на самом деле все прошел: взглянем на столбец таблицы, над которым нет заголовка; — в нем какие-то цифры — они показывают, сколько регистрации стека занято (всю таблицу стека писать не надо, а эти цифры писать надо). Правило заполнения столбца очень простое: какая команда ИП добавляет единицу, какая операция над двумя числами умензыет предыдущое число на единицу, операции над одним числом не изменяют его. И если появилось число 5, то в этот момент при очередном «качке» стека один из промежутных результатов будет утеран.

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

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

О математике гармоничских колебаний
(Начало см. на c. 9)

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

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

Использовая площадь…
(Начало см. на c. 16)

Уражнения

Данные правильный треугольник $ABC$ и точка $O$ внутри него; $A', B'$ и $C'$ — проекции этой точки на высоты $AA_1$ , $BB_1$ и $CC_1$ соответственно. Докажите, что величана $AA' + BB' + CC'$ не зависит от выбора точки $O$ .
Докажите, что в выпуклом многоугольнике, все углы которого равны, сумма длини перпендикуров, опущенных из любой внутренней точки $O$ на стороны многоугольника (или на их продолжения), не зависит от положения точки $O$ .
Докажите, что если противоположные стороны четырехугольника не параллельны, то середина отрезка, соединяющего точки пересечения противоположных сторон, лежит на прямой, соединяющей середины диагоналей.
Докажите, что дляна бисектрисы угла $B$ треугольника $ABC$ равна $\frac{2ac}{a+c} \cos \frac{\beta}{2}$ .
Докажите с помощью площади, что каждая медиана треугольника делится любой другой медианной в отношении 2:1, считая от вершины, и тем самым медианы треугольника пересекаются в одной точке.
На стороне $AC$ треугольника $ABC$ взята точка $D$ . Докажите, что сумма радиусов вписанных окружностей треугольников $ABD$ и $BCD$ больше радиуса вписанной окружности треугольника $ABC$ .