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

х-у=сn10n+сn-110n-1+…+с110+с0 0« сi = 9 , i=0,n

Если первые коэф-ты этой формулы равны 0, то их отбросим десятич-ая форма записи числа х-у.

Если степени не равны (число цифр в записи числа у не совпадает с числом цифр записи числа х), то добавим к записи числа у с нулевым коэф-том, чтобы уровнять число цифр и рассужд-я повторить.

Словесное описание алгоритма вычитания:

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

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

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

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

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

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

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

1) десятич-ая запись числа; 2) табл. умнож. однозн. чисел; 3) законы слож. и умнож(ЗСУ).; 4) табл. слож-я однозн. числе.

Умнож-е многозн-х чисел свод-ся к умнож-ю многозн-го числа на однозн-ое, умнож-ю числа на 10k и слож-ю многозн-х чисел.

Алгоритм умножения в общем виде: Пусть 0« аi « 9 , , аn≠0 , i=аn.

х= аn•10n+аn-1•10n-1+…+а1•10+ а0 ; у-однозн-ое число

ху=( аn •10n+аn-1•10n-1+…+а1•10+а0)•у=д/з=( аn •10n)у+(аn-1•10n-1)у+…+(а1•10)у+ а0у=а/з, к/з= (аn•у) 10n+( аn-1•у) 10n-1+…+( а1•у)10+ а0у====

Заменим аkу их значениями, используя табл-цу умнож-я. Затем представим аkу=вk10+сk

вk,сk – однозн-ые. Подставим:

==(вn10+сn)10n+(вn-110+сn-1)10n-1+…+(в110+с1)10+(в010+с0)=ТС, ТУ=вn10n+1+(сn+вn-1)10n+…+ +(с1+в0)10+с0 Находим знач-е сумм по ТаблСлож сk+вm-1 k, m=0,n

Если сумма окаж-ся больше либо равна 10, то представить её в виде t•10+t0 .Далее пользуемся ЗСУ, преобразовать данное выраж-е до тех пор пока не получ-ся десятич-ая запись числа ху.

Составим алгоритм умнож-я числа на 10k, т. е. справа к числу приписать k нулей:

Пусть 0« аi « 9 , , аn≠0 , i=аn. х= аn•10n+аn-1•10n-1+…+а1•10+ а0

х•10k=(аn•10n+аn-1•10n-1+…+а1•10+а0)10k=д/з=(аn•10n)10k+(аn-1•10n-1)10k+…+(а1•10)10k+ а010k=а/з, св-во степени= аn•10n+k+ аn-1•10n+k-1+…+ а1•10k+1+ а010k= аn•10n+k+ аn-1•10n+k-1+…+ а1•10k+1+ а010k+0•10k-1+…+0•10+0= аn• аn-1•…• а1 а00…0

Заметим, что умнож-е на число у•10k , где у-однозн. число, сводится к умнож-ю на однозн-ое число у и на число 10k (используя а/з умнож-я).

Составим алгоритм умнож-я многозн. на многозн. число:

у= вn•10n+ вn-1•10n-1+…+ в1•10+ в0 , 0< вj« 9, х — многозн. число

ху=х•(вn•10n+вn-1•10n-1+…+в1•10+в0)=д/з=х(вn•10n)+х(вn-1•10n-1)+…+х(в1•10)+хв0=а/зу= =(хвn)•10n+(хвn-1)10n-1+…+(хв1)10+хв0=1) алгоритм умнож-я однозн.х0 на однозн. вk, k=0,n; 2) умнож-е числа на 10k; 3) слож-е многозн. чисел.

Деление многозн. чисел основано на Т. о делении с остатком.

а, в Є N (Eq, rЄZ) а=вq+r, 0 « r <в

Теор-ие основы деления многозн. чисел:

1) Т. о делении с остатком; 2) слож-е, умнож-е, вычит-е многозн-х чисел.

14. Отношение делимости на мн-ве целых неотрицательных чисел, его свойства. Делимость суммы, разности, произведения. Признаки делимости.

! будем говорить aєZ, делится на bєN, если (сущ-ет qєZ) a=bq, a:b (а делится на b или а кратно b). а : b<=> когда сущ-ет qЄZ /a = b*q

a—кратное числа b, b—делитель числа a

Пр-р: 6:3, (сущ-ет 2єN) 6=3*2

!Свойства:

1) любое натур-ое число дел-ся само на себя (рефлексивность) (для любого аєN) а:а (сущ-ет 1єN) (для любого аєN) а*1=а => a:a

Следствие: любое целое неотрицательное число дел-ся на 1

2)Если a:b => a≥b (делитель числа не превосходит самого числа)

a:b=> (сущ-ет qєZ) такое что a=bq, и значит а-b=bq—b=b(q-1). Так как а≠0, то q≥1, b(q-1) ≥0 => a≥b

следствие: мн-во натуральных делителей аєN конечно

3)0 дел-ся на любое натуральное число 0:b ( для любого bєN)

по опред умн-я (для любого аєZ) а*0=0=>0*b => a=0 q=0 b— делитель=> 0:b

4) Отношение делимости антисимметрично

(для любых а,bєN) a:b, b:a => a=b

a:b =>(сущ—ет q1 є N) a= bg1 | => a≥b èa=b

b:a =>(сущ—ет q2 є N) b= ag2 | => b≥a

5)Отношение делимости транзитивно, т. с. (для любого а€Z, b,c € N) (a:b, b:c=>а:с )

а:b=>сущ—ет k€ Z, | a=b*k | è a=b*k= (c*m)*k=c*(m*k) € Z=>a:c

b:c=> сущ—ет m €Z, | b=c*m |

Рассмотренные свойства показывают, что отношение делимости является отношением нестрогого порядка.

Делимости суммы, разности и произведения.

6) Если а:с и b:с=>(а+(-)b):с (если каждое из чисел делится на с, то и сумма(разность) делится на с.

а:с=>сущ-ет k€ Z, | a=k*с | è

b:c=> сущ-ет m €Z, | b=m*c |

è а+(-)b= k*с+(-)m*c =(k+(-)m)*c €Z=>(а+(-)b):с

Это свойство обобщается на любое конечное число слагаемых:

а1:b, a2:b, ….. am:b=>(а1+ a2 +…+ am):b

7) Если все слагаемые суммы, кроме одного, делятся на данное число, то сумма на это число не делится.(вытекает из 5,6 свойства)

8) Если один из множителей а и b дел-ся на сєN, то и все произведение дел-ся на с

а, b єZ, сєN a:c и b:c => ab:c (аналогично 4)

9)Если a:m, mєN, b:n, nєN, то произведение ab делится на произведение mn.

a:m => (сущ-ет g1 єZ ) а= mg1 |

b:n=> (сущ-ет g2 єZ ) а= mg2 |=> ab = (mg1) (ng2)=(mn)( g1g2 )=>ab:mn

! Под признаком делимости понимают необходимое и достаточное условие делимости какого-либо числа на данное число. При этом позволяется не выполняя деление(по виду числа) судить о его делении на данное. Признак делимоти на любое натуральное число м. б. получен из след. теоремы «Признак делимости Паскаля»