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

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

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

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

Сначала рассмотрим умножение многозначного числа на однозначное. Умножим, например, 428 на 3. Согласно правилу записи чисел в десятичной системе счисления 428 можно представить в виде

4·10² + 2·10 + 8 и тогда 428·3 = (4·10² + 2·10 + 8)·3.

На основании дистрибутивности умножения относительно сложения раскроем скобки: (4·10²)·3 + (2·10)·3 + 8·3. Произведения в скобках могут быть найдены по таблице умножения однозначных чисел: 12·10² + 6·10 + 24.

Видим, что умножение многозначного числа на однозначное свелось к умножению однозначных чисел. Но чтобы получить окончательный результат, надо преобразовать выражение 12·10² + 6·10 + 24 –  коэффициенты перед степенями 10 должны быть меньше 10. Для этого представим число 12 в виде 1·10+2, а число 24 в виде 2·10+4.

Затем в выражении (1·10 + 2)·10² + 6·10 + (2·10 + 4) раскроем скобки: 1·10³ + 2·10² + 6·10 + 2·10 + 4.

На основании ассоциативности сложения и дистрибутивности умножения относительно сложения сгруппируем слагаемые 6·10 и 2·10 и вынесем 10 за скобки: 1·10³ + 2·10² + (6 + 2)·10 + 4.

Сумма 6 + 2 есть сумма однозначных чисел и может быть найдена по таблице сложения: 1·10³ + 2·10² + 8·10 + 4. Полученное выражение есть десятичная запись числа 1284, т.е. 428·3 = 1284.

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

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

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

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

Выведем правило умножения многозначного числа на однозначное в общем виде. Пусть требуется умножить х = а_n · 10ⁿ+ а_n–1 · 10^n–1 + ...+ а₀ на однозначное число у: х·у = (а_n·10ⁿ+ а_n–1·10^n–1+ ...+а₀)·у = (а_n·у)·10ⁿ + (а_n–1·у)· 10^n–1 + ... + а₀ · у, причем преобразования выполнены на основании свойств умножения. После этого, используя таблицу умножения, заменяем все произведения а_k · у, где 0  k  n, соответствующими значениями а_k · у = b_k · 10 + с и получаем: х · у=(b_n·10 + с_n)·10ⁿ + (b_n–1·10 + с _n–1)·10^n–1 + ... + (b₁·10 + с₁)·10 + (b₀·10 +с₀) = b_n·10ⁿ⁺¹ + (с_n + b_n–1)·10ⁿ + ... + (с₁ + b₀)·10 + с₀.

По таблице сложения заменяем суммы с_k + b_k–1 где 0  k  n и k = 0, 1, 2, ..., n, их значениями. Если, например, с₀ однозначно, то последняя цифра произведения равна m, а к скобке (с₁ + b₀) надо прибавить 1. Продолжая этот процесс, получим десятичную запись числа х · у.

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

1. Записываем второе число под первым.

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

3. Если произведение цифр единиц числа х на число убольше или равно 10, то представляем его в виде 10q₁ + с₀, где с₀ –  однозначное число; записываем с₀ в разряд единиц ответа и запоминаем q₁ –  перенос в следующий разряд.

4. Умножаем цифры разряда десятков на число у, прибавляем к полученному произведению число q₁ и повторяем процесс, описанный в пп. 2 и 3.

5. Процесс умножения заканчивается, когда окажется умноженной цифра старшего разряда.

Как известно, умножение числа х на число вида 10^k сводится к приписыванию к десятичной записи данного числа k нулей. Покажем это. Умножим число х = а_n · 10ⁿ+ а_n–1 · 10^n–1 + ...+ а₀ на 10^k :

(а_n·10ⁿ+ а_n–1·10^n–1 + ...+ а₀)·10^k = а_n·10^{n+ k} + а_n–1·10^{n+ k –1} + ...+ а₀·10^k.

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

k нулей

а_n·10^{n+ k} + а_n–1·10^{n+ k –1} + ...+ а₀·10^k + 0·10 ^k–1 +0·10 ^k–2 +...+ 0·10 + 0.

Например, 347·10³ = (3·10² + 4·10 + 7)·10³ = 3·10⁵ + 4·10⁴ + 7·10³ = 3 · 10⁵ + 4 · 10⁴ 7 · 10³ + 0 · 10² + 0 · 10 + 0 = 347000.

Заметим еще, что умножение на число у·10^k, где у  –  однозначное число, сводится к умножению на однозначное число уи на число 10^k.

Например, 52 · 300 = 52 ·(3 · 10²) = (52 · 3) · 10² = 156 · 10² = 15600.

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

Умножим, например, столбиком 428 на 263.

428

263

1284

2568

856

112564

Видим, что для получения ответа нам пришлось умножить 428 на 3, 6 и 2, т.е. умножить многозначное число на однозначное; но, умножив на 6, результат записали по – особому, поместив единицы числа 2568 под десятками числа 1284, так как умножали на 60 и получили число 25680, но нуль в конце записи опустили. Слагаемое 856 – это результат умножения на 2 сотни, т.е. число 85600. Кроме того, нам пришлось найти сумму многозначных чисел.

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

– умножать многозначное число на однозначное и на степень десяти;

– складывать многозначные числа.

Представим число 263 в виде суммы 2 · 10² + 6 · 10 + 3 и запишем произведение 428 · (2 · 10² +6 · 10+3). Оно, согласно дистрибутивности умножения относительно сложения, равно 428 · (2 · 10²) + 428 · (6 · 10) + 428 · 3. Отсюда, применив ассоциативное свойство умножения, получим: (428 · 2) · 10² + (428 · 6) · 10 + 428 · 3. Видим, что умножение многозначного числа 428 на многозначное число 263 свелось к умножению многозначного числа 428 на однозначные числа 2, 6 и 3, а также на степени 10.

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

х = а_n · 10ⁿ+ а_n–1 · 10^n–1 + ...+ а₀; у = b_m · 10^m + b_m–1 · 10^m–1 +...+ b₀.

В силу дистрибутивности умножения относительно сложения, а также ассоциативности умножения можно записать:  х · у = х · (b_m · 10^m + b_m–1 · 10^m–1 +...+ b₀) = (х · b_m) · 10^m + (х · b_m–1) · 10^m–1 +...+ х · b₀. Последовательно умножая число х на однозначные числа b_m, b_m–1,..., b₀, а затем на 10^m , 10^m–1, ..., 1, получаем слагаемые, сумма которых равна х · у.

Приходим к алгоритму умножения числа х = на число у =  .

1. Записываем множитель х и под ним второй множитель у.

2. Умножаем число х на младший разряд b₀ числа у и записываем произведение х · b₀ под числом у.

3. Умножаем число х на следующий разряд b₁, числа у и записываем произведение х  · b₁, но со сдвигом на один разряд влево, что соответствует умножению х · b₁ на 10.

4. Продолжаем вычисление произведений до вычисления х · b _k.

5. Полученные k + 1 произведения складываем.

Изучение алгоритма умножения многозначных чисел в начальном курсе математики, как правило, проходит в соответствии с выделенными этапами. Различия имеются только в записи. Например, при обосновании случая умножения многозначного числа на однозначное пишут: 428 · 3 = (400 + 20 + 8) · 3 = 400 · 3 + 20 · 3 + 8 · 3 = 1200 + 60 + 24 = 1284. Основой выполненных преобразований являются:

 –  представление первого множителя в виде суммы разрядных слагаемых (т.е. запись числа в десятичной системе счисления);

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

 –  умножение «круглых» (т.е. оканчивающихся нулями) чисел на однозначное число, что сводится к умножению однозначных чисел.

Алгоритм деления

Когда речь идет о технике деления чисел, то этот процесс рассматривают как действие деления с остатком: разделить целое неотрицательное число а на натуральное число b  –  это значит найти такие целые неотрицательные числа q и r , что а = b · q + r, причем 0  r < b.

В ыясним сначала, как осуществляется деление на однозначное число. Если на однозначное число делят однозначное или двузначное (не превышающее 89), то используется таблица умножения однозначных чисел. Например, частным чисел 54 и 9 будет число 6, так как 9 · 6= 54. Если же надо разделить 51 на 9, то находят ближайшее к нему меньшее число, которое делится на 9  –  это число 45, и, следовательно, неполным частным при делении 51 на 9 будет число 5. Чтобы найти остаток, надо из 51 вычесть 45: 51 – 45 = 6. Таким образом, 51 = 9 · 5 + 6, т.е. при делении 51 на 9 получается неполное частное 5 и остаток, равный 6. Записать это можно иначе, при помощи деления уголком:

51 9

45 5

6

Будем теперь делить трехзначное число на однозначное, например, 378 на 4. Разделить 378 на 4 –  это значит найти такое неполное частное q и остаток r, что 378 = 4 q + r, причем остаток r должен удовлетворять условию 0  r < b, а неполное частное q  –  условию 4 q  378 < 4(q + 1).

Определим, сколько цифр будет содержаться в записи числа q. Однозначным число q быть не может, так как тогда произведение 4q может быть максимально равно 36 и, значит, не будут выполняться условия, сформулированные выше для r и q. Если число q двузначное, т.е. если 10 < q < 100, то тогда 40 < 4 q < 400 и, следовательно, 40 < 378 < 400, что верно. Значит, частное чисел 378 и 4  –  число двузначное.

Чтобы найти цифру десятков частного, умножим последовательно делитель 4 на 20, 30, 40 и т.д. Поскольку 4 · 90 = 360, а 4 · 100 = 400, и 360 < 378 < 400, то неполное частное заключено между числами 90 и 100, т.е. q = 90 + q₀.Но тогда должны выполняться неравенства:

4 ·(90 + q₀)  378 < 4 ·(90 q + q₀ + 1),

откуда 360 + 4 q₀  378 < 360 + 4(q₀ +1)

и 4q₀  18 < 4(q₀ + 1).

Число q₀ (цифра единиц частного), удовлетворяющее последнему неравенству, можно найти подбором, воспользовавшись таблицей умножения. Получаем, что q₀ = 4 и, следовательно, неполное частное q = 90 + 4 = 94. Остаток находится вычитанием: 378 – 4 · 94 = 2.

Итак, при делении числа 378 на 4 получается неполное частное 94 и остаток 2: 378 – 4 · 94+2. Описанный процесс является основой деления уголком:

378 4

36 94

18

16

2

Аналогично выполняется деление многозначного числа на многозначное. Разделим, например, 4316 на 52. Выполнить это деление  –  значит найти такие целые неотрицательные числа q и r, что 4316 = 52 q + r, 0  r < 52, а неполное частное должно удовлетворять неравенству 52q  4316 < 52(q + 1).

Определим число цифр в частном q. Очевидно, частное заключено между числами 10 и 100 (т.е. q  –  двузначное число), так как 520 < 4316 < 5200. Чтобы найти цифру десятков частного, умножим последовательно делитель 52 на 20, 30, 40, 50 и т.д. Поскольку 52 · 80 = 4160, а 52 · 90 = 4680 и 4160 < 4316 < 4680, то неполное частное заключено между числами 80 и 90, т.е. q = 80 + q₀. Но тогда должны выполняться неравенства:

52 · (80 + q₀)  4316 < 52 · (80 + q₀ + 1),

4160 + 52 q₀  4316 < 4160 + 52 · (q₀ + 1),

52 q₀  156 < 52 · (q₀+ 1).

Ч исло q₀ (цифру единиц частного), удовлетворяющее последнему неравенству, можно найти подбором: 156 = 52 · 3, т.е. имеем случай, когда остаток равен 0. Следовательно, при делении 4316 на 52 получается частное 83. Приведенные рассуждения лежат в основе деления уголком:

4316 52

416 83

156

156

0

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

1. Если а = b, то частное q = 1, остаток r = 0.

2. Если а > b и число разрядов в числах а и b одинаково, то частное q находим перебором, последовательно умножая b на 1, 2, 3, 4, 5, 6, 7, 8, 9, так как а < 10 b. Этот перебор можно ускорить, выполнив деление с остатком цифр старших разрядов чисел а и b.

3. Если а > b и число разрядов в числе а больше, чем в числе b, то записываем делимое а и справа от него делитель b, который отделяем от а уголком и ведем поиск частного и остатка в такой последовательности:

а) Выделяем в числе а столько старших разрядов, сколько разрядов в числе b или, если необходимо, на один разряд больше, но так, чтобы они образовывали число d₁, больше или равное b. Перебором находим частное q₁ чисел d₁ и b,последовательно умножая b на 1, 2, 3, 4, 5, 6, 7, 8, 9. Записываем q₁ под уголком (ниже b).

б) Умножаем b на q₁, и записываем произведение под числом а так, чтобы младший разряд числа bq₁ был написан под младшим разрядом выделенного числа d₁.

в) Проводим черту под bq₁ и находим разность r₁ = d₁ –  b q₁..

г) Записываем разность r₁ под числом bq₁ приписываем справа к r₁ старший разряд из неиспользованных разрядов делимого а и сравниваем полученное число d₂ с числом b.

д) Если полученное число d₂ больше или равно b, то относительно него поступаем согласно п. 1 или п. 2. Частное q₂записываем после q₁.

е) Если полученное число d₂ меньше b, то приписываем еще столько следующих разрядов, сколько необходимо, чтобы получить первое число d₃, большее или равное b. В этом случае записываем после q₁ такое же число нулей. Затем относительно d₃ поступаем согласно пп. 1, 2. Частное q₂ записываем после нулей. Если при использовании младшего разряда числа а окажется, что d₃ < b, то тогда частное чисел d₃ и b равно нулю, и этот нуль записывается последним разрядом к частному, а остаток r = d_3.