14 Вопрос

Алгоритм сложения

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

Естественно, смысл сложения сохраняется и для много­значных чисел, но практическое выполнение сложения проис­ходит по особым правилам. Сумму многозначных чисел обычно находят, выполняя сложение столбиком.

Видим, что в основе алгоритма сложения многозначных чисел лежат следующие теоретические факты:

- способ записи чисел в десятичной системе счисления;

- свойства коммутативности и ассоциативности сложения;

- дистрибутивность умножения относительно сложения; -таблица сложен и я однозначных чисел.

Выведем алгоритм сложения многозначных чисел в общем виде. Пусть даны числа: х = а_n*10ⁿ + а_n-1*10 ^n-1 + ... + а₀ и у = b_п*10 ⁿ+ b_n-1*10^n-1 + ... +b₀, т.е. рассмотрим случай, ко­гда количество цифр в записи чисел х и у одинаково, х + у -= (a_n*10ⁿ+a_n-1*10^n-1+ ... + а₀) + (b_n*10ⁿ+b_n-1 + ... + b₀) = (a_n+b_n)*10n+(a_n-1+b_n-1)*10^n-1+ ... + (а_в + b₀) - преобразо­вания выполнены на основе свойств ассоциативности и коммута­тивности сложения, а также дистрибутивности умножения от­носительно сложения. Сумму (а, +b_n)10ⁿ + (а_n-1 + b_n-1)*10^n-1 + ... + (а₀ + b₀), вообще говоря, нельзя рассматривать как деся­тичную запись числа х + у, так как коэффициенты перед сте­пенями 10 могут быть больше 9. Лишь в случае, когда все суммы а_к + b_k не превосходят 9, операцию сложения можно считать законченной. В противном случае выбираем наимень­шее к, для которого а_к + b_к ≥10. Если а_к + b_к ≥ 10, то из того, что 0 ≤ а_к ≤ 9 и 0 ≤ b_к ≤ 9, следует неравенство 0 ≤ а_к + b_к≤18 и по­этому а_k + b_к можно представить в виде а_к + b_к = 10 + с_к, где 0 ≤с_к ≤ 9. Но тогда (а_к + b_к)*10^к = (10 + с_k)*10^k=10^k+1+ c_k* 10 . В силу свойств сложения и умножения в (а_п+b_n)*10ⁿ +...+(a₀+b₀) слагаемые (а_k+1 + b_k+1)*10^k+1 + (а_k + b_k)*10 могут быть заме­нены на (a_k+1 + b_k+1+ 1)*10^k+1 + с_k*10^k . После этого рассмат­риваем коэффициенты а_n+ b_n, а_n-1, + b_{п-1, ...,} a_k+2 + b_k+1, a_k+1+ b_к+1 + 1, выбираем наименьшее s, при котором коэффи­циент больше 9, и повторяем описанную процедуру. Через п шагов придем к выражению вида: х + у = (с_n + 10)*10ⁿ + ... + с₀, где с_n ≠ 0, или х + у = 10ⁿ⁺¹+ с_n*10ⁿ + ... + с₀, и где для всех п выполняется равенство 0 ≤ с_n < 10. Тем самым получена деся­тичная запись числа х + у.

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

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

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

2. Складывают единицы первого разряда. Если сумма меньше десяти записывают ее в разряд единиц ответа и пере­ходят к следующему разряду (десятков).

3. Если сумма единиц больше или равна десяти, то пред­ставляют ее в виде а₀+ b₀ = 1 • 10 + с_в, где с₀ - однозначное число; записывают с₀ в разряд единиц ответа и прибавляют 1 к десяткам первого слагаемого, после чего переходят к раз­ряду десятков.

4. Повторяют те же действия с десятками, потом с сотнями и т.д. Процесс заканчивается, когда оказываются сложенными цифры старших разрядов. При этом, если их сумма больше или равна десяти, то приписываем впереди обоих слагаемых нули, увеличиваем нуль перед первым слагаемым на 1 и вы­полняем сложение 1+0=1.

Заметим, что в этом алгоритме (как и в некоторых других). для краткости употребляется термин «цифра» вместо «одно­значное число, изображаемое цифрой».