Песни о Паскале

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

В) Постройте механизмы очереди и стека на базе массива символов, а не на базе строки. Какие дополнительные переменные здесь понадобятся?

Глава 46 Огромные числа

Давно минули времена, когда для счета всем хватало своих пальцев – первого «калькулятора» человечества, а наши потребности в счете все растут и растут…

Сколько звезд на небе?

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

Первый из них – тип LongInt – длинное целое число. Наибольшее значение для этого типа чисел составляет 2'147’483’647, то есть несколько больше двух миллиардов. Маловато будет, – рассудили мудрецы, и продолжили поиск.

Вскоре они наткнулись на другой тип чисел – Extended, который мог вмещать сказочные значения – вплоть до 10⁴⁹³²! Иначе говоря, эти числа могли содержать почти пять тысяч цифр! Но радость математиков была недолгой; рассмотрев тип Extended пристальней, они отвергли его. Оказалось, что из этих пяти тысяч цифр только первые двадцать – точные (их называют значащими), а остальные не внушают доверия, и могут быть замены чем угодно, хоть нулями.

Есть ли толк от этих неточных чисел? Есть. Дело в том, что в инженерных и научных расчетах этой точности вполне хватает. Но здесь был иной случай, – требовался абсолютно точный подсчет, государь не терпел огрехов. «Точность – вежливость королей!» – говаривал он. И программисты ткнулись, как обычно, в тупик.

Сложение «в столбик» никто не отменял

Выход из тупика нашелся случайно. Один из королевских программистов помогал сынишке справиться со школьными уроками – складывали числа «в столбик». Тут его и осенило: почему бы и нам, – смекнул папаша, – не складывать числа тем же способом? Так тряхнем стариной и вспомним это сложение «в столбик»? Рис. 102 освежит вашу память.

Рис.102 – Пример сложения в столбик

Итак, сложение чисел начинаем с младшего, то есть крайнего правого разряда. Если сумма двух цифр превысит девять, то в разряд результата записываем остаток от деления этой суммы на 10 (то есть цифры от 0 до 9), а к следующему разряду добавляем перенос.

Если обозначить складываемые цифры буквами A и B, то алгоритм сложения «в столбик» для одного разряда с учетом предыдущего переноса запишется так:

      цифра := (A + B + перенос) mod 10
      перенос := (A + B + перенос) div 10

Напомню, что операция MOD вычисляет остаток от деления одного целого числа на другое, а операция DIV – частное с отбрасыванием остатка. Перед сложением самого младшего разряда перенос берётся равным нулю. Обратите внимание, что условный оператор здесь излишен.

Великая стройка

Уловив основную идею – действия «в столбик», – программисты задумались над хранением цифр огромного числа. Они рассмотрели два равно подходящих средства: либо массив байтов, каждый из которых будет содержать числа от 0 до 9, либо массив символов «0»…«9». Ученые остановились на