Системы счисления. Алгоритмы сложения и вычитания. Алгоритм сложения

• Название: Алгоритм сложения
• Анкор: Системы счисления
• Дата: 11.08.2022
• Размер: 73.5 Kb.
• Имя файла: Алгоритмы сложения и вычитания.doc
• Тип: Документы; #644222

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

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

Например, 1 + 1 = 2, 7 + 9 = 16 и т.д.

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

Представим слагаемые 341 и 7238 в виде суммы степеней десяти с коэффициентами:

341 + 7238 = (3·10² + 4·10 + 1) + (7·10³ + 2·10² + 3·10 + 8).

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

3·10² + 4·10 + 1 + 7·10³ + 2·10² + 3·10 + 8.

На основании свойства коммутативности поменяем местами слагаемые:

7·10³ + 3·10² + 2·10² + 4·10 + 3·10 + 1 + 8.

Согласно свойству ассоциативности произведем группировку:

7·10³ + (3·10² + 2·10²) + (4·10 + 3·10) + (1 + 8).

Вынесем за скобки в первой группе число 10², а во второй – 10. Это можно сделать в соответствии со свойством дистрибутивности умножения относительно сложения:

7·10³ + (3 + 2)·10² + (4+3)· 10 + (1 + 8).

Итак, сложение данных чисел 341 и 7238 свелось к сложению однозначных чисел, изображенных цифрами соответствующих разрядов. Эти суммы находим по таблице сложения: 7·10³ + 5·10² +7·10 + 9. Полученное выражение есть десятичная запись числа 7579.

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

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

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

– дистрибутивность умножения относительно сложения;

– таблица сложения однозначных чисел.

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

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

х = а_n·10ⁿ+а_n-1·10^n-1+...+а₁·10 + а₀ и у = b_n·10ⁿ+b_n-1·10^n-1+ ... + b₁·10 + b₀,

т.е. рассмотрим случай, когда количество цифр в записи чисел х и у одинаково,

х+у = (а_n·10ⁿ+а_n-1·10^n-1+...+ а₁·10 + а₀) + (b_n·10ⁿ+b_n-1·10^n-1+...+ b₁·10 + b₀) =

(а_n + b_n)·10ⁿ + (а_n-1 + b_n-1)·10^n-1 +... + (а₁+ b₁)·10 + (а₀ + b₀) – преобразования выполнены на основе свойств ассоциативности и коммутативности сложения, а также дистрибутивности умножения относительно сложения.

Сумму (а_n+ b_n )·10ⁿ + (а_n-1 + b_n-1)·10^n-1 +... + (а₁+ b₁)·10 + (а₀ + b₀) вообще говоря, нельзя рассматривать как десятичную запись числа х + у, так как коэффициенты перед степенями 10 могут быть больше 9. Лишь в случае, когда все суммы а_k + b_k не превосходят 9, операцию сложения можно считать законченной. В противном случае выбираем наименьшее k, для которого а_k+b_k10. Если а_k + b_k 10, то из того, что 0  а_k  9 и 0  b_k  9, следует неравенство 0  а_k + b_k  18 и поэтому а_k + b_k можно представить в виде

а_k + b_k = 10+ с_k, где 0  с_k  9. Но тогда (а_k + b_k) ·10^k =(10 + с_k) ·10^k = = 10^k+1 + с_k·10^k. В силу свойств сложения и умножения в

(а_n + b_n )·10ⁿ +... + (а₁+ b₁)·10 + (а₀ + b₀) слагаемые

(а_k+1 + b_k+1) ·10^k+1 + (а_k + b_k) ·10^k могут быть заменены на

(а_k+1 + b_k+1 + 1) ·10^k+1 + c_k·10^k. После этого рассматриваем коэффициенты

а_п + b_n, а_п-1 + b_n-1, а_k+2+ b_k+2, а_k+1 + b_k+1 + 1, выбираем наименьшее s, при котором коэффициент больше 9, и повторяем описанную процедуру. Через n шагов придем к выражению вида: х + у = (c_n + 10) ·10ⁿ +...+ c₀, где c_n  0, или х + у = 10ⁿ⁺¹ + c_n ·10ⁿ +...+ c₀ и где для всех nвыполняется равенство 0  с_n < 10. Тем самым получена десятичная запись числа х + у.

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

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

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

3. Если сумма единиц больше или равна десяти, то представляют ее в виде а₀ + b₀ = 1·10 + c₀, где c_{0 –} однозначное число; записывают c₀ в разряд единиц ответа и прибавляют 1 к десяткам первого слагаемого, после чего переходят к разряду десятков.

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

Алгоритм вычитания

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

Если же числа а и b многозначные и b < а, то смысл действия вычитания остается тем же, что и для вычитания в пределах 20, но техника нахождения разности становится иной: разность многозначных чисел чаще всего находят, производя вычисления столбиком, по определенному алгоритму. Выясним, каким образом возникает этот алгоритм, какие теоретические факты лежат в его основе.

Рассмотрим разность чисел 485 и 231. Воспользуемся правилом записи чисел в десятичной системе счисления и представим данную разность в тàêîì виде: 485 – 231 = (4·10² + 8·10 + 5) – (2·10² + 3·10 + 1). Чтобы вычесть из числа 4·10² + 8·10 + 5 сумму 2·10² + 3·10 + 1, достаточно вычесть из него каждое слагаемое этой суммы одно за другим, и тогда:

(4·10² + 8·10 + 5)–(2·10² + 3·10 + 1)=(4·10² + 8·10 + 5) – 2·10² – 3·10 – 1.

Чтобы вычесть число из суммы, достаточно вычесть его из какого-либо одного слагаемого (большего или равного этому числу). Поэтому число 2·10² вычтем из слагаемого 4·10², число 3·10 из слагаемого 8·10, а число 1 – из слагаемого 5, тогда:

(4·10² + 8·10 + 5)–2·10² – 3·10 – 1=(4·10² – 2·10²)+(8·10 – 3·10)+(5 – 1).

Воспользуемся дистрибутивностью умножения относительно вычитания и вынесем за скобки 10² и 10. Тогда выражение будет иметь вид: (4 – 2)·10² + (8 – 3)·10 + (5 – 1). Видим, что вычитание трехзначного числа 231 из трехзначного числа 485 свелось к вычитанию однозначных чисел, изображенных цифрами соответствующих разрядов в записи заданных трехзначных чисел. Разности 4 – 2, 8 – 3 и 5 – 1 находим по таблице сложения и получаем выражение: 2·10² + 5·10 + 4, которое является записью числа 254 в десятичной системе счисления. Таким образом, 485 – 231= 254. Выражение (4 – 2) ·10² + (8 – 3)·10 + (5 – 1) задает правило вычитания, которое обычно выполняется столбиком:

В
идим, что вычитание многозначного числа из многозначного основывается на:

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

– правилах вычитания числа из суммы и суммы из числа;

– свойстве дистрибутивности умножения относительно вычитания;

– таблице сложения однозначных чисел.

Нетрудно убедиться в том, что если в каком-нибудь разряде уменьшаемого стоит однозначное число, меньше числа в том же разряде вычитаемого, то в основе вычитания лежат те же теоретические факты и таблица сложения однозначных чисел. Найдем, например, разность чисел 760 – 326. Воспользуемся правилом записи чисел в десятичной системе счисления и представим эту разность в таком виде:

760 – 326 = (7·10² + 6·10 + 0) – (3·10² + 2·10 + 6).

Поскольку из числа 0 нельзя вычесть 6, то выполнить вычитание аналогичное тому, как было сделано в первом случае, невозможно. Поэтому возьмем из числа 760 один десяток и представим его в виде 10 единиц – десятичная система счисления позволяет это сделать – тогда будем иметь выражение: (7·10² + 5·10 + 10) – (3·10² + 2·10 + 6). Если теперь воспользоваться правилами вычитания суммы из числа и числа из суммы, а также дистрибутивностью умножения относительно вычитания, то получим выражение

(7 – 3)·10² + (5 – 2)·10 + (10 – 6) или 4·10² + 3·10 + 4. Последняя сумма есть запись числа 434 в десятичной системе счисления. Значит, 760 – 326 = 434.

Рассмотрим процесс вычитания многозначного числа из многозначного в общем виде.

Пусть даны два числа х = а_n10ⁿ + а_n-1·10^n-1 + ... + а₁·10 + а₀ и

у = b_n·10ⁿ + b_n-1·10^n-1 + ... + b₁·10 + b₀. Известно также, что у < х. Используя правила вычитания числа из суммы и суммы из числа, дистрибутивность умножения относительно вычитания, можно записать, что

(а_n – b_n )·10ⁿ + (а_n-1 – b_n-1)·10^n-1 +... + (а₁ – b₁)·10 + (а₀ – b₀) (1)

Эта формула задает алгоритм вычитания, но при условии, что для всех m выполняется условие а_k  b_k. Если же это условие не выполняется, то берем наименьшее k, для которого а_k < b_k.Пусть m– наименьший индекс, такой, что m >k. и а_m  0, а а_m-1 = ... = а_k+1 = 0. Имеет место равенство а_m·10^m = (а_m – 1)·10^m +9·10^m–1 + ... + 9·10^k+1 + 10·10^k (например, если m = 4, k= 1, а_m =6, то 6·10⁴ = 5·10⁴ + 9·10³ + 9·10² + 10·10). Поэтому в равенстве (1) выражение (а_m – b_m)·10^m + ...+ (а_k – b_k )·10^k можно заменить на

(а_m – b_m – 1)·10^m+(9 – b_m–1 )·10^m–1+...+(9 – b_k+1)·10^k+1 + (а_k + 10 – b_k)·10^k. Из того, что а_k < b_k < 10, вытекает неравенство 0 < 10 + а_k – b_k < 10, а из того, что 0 b_s 9, вытекает неравенство 09–b_s<10, где k+1sm – 1. Поэтому в записи х – у=(а_n – b_n)·10ⁿ +...+ (а_m – b_m – 1)·10^m + (9 – b_m–1)·10^m–1 + ... + (9 – b_k+1)·10^k+1 + (а_k + 10 – b_k)·10^k + ...+ (а₀ – b₀) все коэффициенты с индексом, меньшим m, неотрицательны и не превосходят 9. Применяя далее те же преобразования к коэффициентам а_n – b_n, ..., а_m – b_m – 1, через n шагов придем к записи разности х – у в виде

х – у = c_n·10ⁿ + cа_n-1·10^n-1 +... + c₀, где для всех k выполняется неравенство 0 < c_k < 10. Если при этом окажется, что с_n = 0, то надо отбросить первые слагаемые, вплоть до первого коэффициента, отличного от нуля.

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

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

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

3. Если же цифра единиц вычитаемого больше единиц уменьшаемого, т.е. b₀ > а₀, а цифра десятков уменьшаемого отлична от нуля, то уменьшаем цифру десятков уменьшаемого на 1, одновременно увеличив цифру единиц уменьшаемого на 10, после чего вычитаем из числа 10 + а₀ число b₀ и записываем разность в разряде единиц искомого числа, далее переходим к следующему разряду.

4. Если цифра единиц вычитаемого больше цифры единиц уменьшаемого, а цифры, стоящие в разряде десятков, сотен и ò.ä. уменьшаемого, равны нулю, то берем первую отличную от нуля цифру в уменьшаемом (после разряда единиц), уменьшаем ее на 1, все цифры в младших разрядах до разряда десятков включительно увеличиваем на 9, а цифру в разряде единиц на 10: вычитаем b₀ из 10 + а₀, записываем разность в разряде единиц искомого числа и переходим к следующему разряду.

5. В следующем разряде повторяем описанный процесс.

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