Система счисления
жүктеу/скачать 184,15 Kb.
|
Лекция 11. Система счисления
| Теорема.Пусть х и у - натуральные числа, записи которых даны в десятичной системе счисления:
х = а ∙10 +а ∙10 +…+ а ∙10+а , у = b ∙10 +b ∙10 +…+b ∙10+b . Тогда число х меньше числа у, если возможно одно из условий: а) n Доказательство. а) Если п • Очевидно, что х<10п+1 и 10m у. Тогда х <10п+1 10m у, т.е. х< у. б) Если п=m, но ап • Умножая обе части этого неравенства на 10п, получим, (ап+1)·10п bп ·10п. • Очевидно, что х <(ап+1)·10пи bп ·10п у, тогда х <(ап+1)·10п< bп ·10п у, т.е. х<у. в) Если п=m,ап=bп,…,ак=bк, но ак-1 • Умножая обе части этого неравенства на 10п,получим: (ак-1 +1)·10п bк-1 ·10п. • Очевидно, что х <(ак-1 +1)·10п и bк-1 ·10п у , тогда х <(ак-1 +1)·10п<<bк-1 ·10п у, т.е. х<у. Например, а) Если х=572 и у=2437, то х<у , так как 572=5·102+7·101+2·100 и у=2·103+4·102+3·101+7 100. п=2, m=3, 2<3, n б) Если х=2372 и у=3487, то х<у, так как 2372=2·103+3·102+7·101+2·100 и 3487=3·103+4·102+8·101+ 5·100. п=3, m=3, ап=2, bn=3, 2<3. в) Если х=2372 и у=2385, то х<у, так как х=2·103+3·102+7·101+2·100 и у=2·103+3·102+8·101+5·100, п=3, m=3, ап=2, bn=2 ак=3, bк=3, ак-1=7, bк-1=8, 7<8. ак-1<bк-1. Арифметические действия с числами, записанными в десятичной системе счисления, выполняют, используя особую таблицу и особые правила, называемые алгоритмами действий. Например, сложение однозначных чисел выполняют с помощью специально составленной таблицы сложения. Вычитание однозначного числа из однозначного или двузначного числа, не превышающего 18, сводится к нахождению третьего числа с учетом таблицы сложения однозначных чисел. Умножение однозначных чисел можно выполнить, основываясь на определение этого действия, как нахождение суммы одинаковых слагаемых или же выполняют с помощью специально составленной таблицы умножения. Деление с остатком однозначного или двузначного числа, не превышающее 89, на однозначное число, сводится к нахождению неполного частного и остатка с учетом таблицы умножения однозначных чисел. Алгоритмы каждого из действий основываются на определенные теоретические положения. Теоретической основой алгоритма сложения многозначных чисел является способ записи чисел в десятичной системе счисления. Кроме того коммутативный и ассоциативный законы умножения, дистрибутивный закон умножения относительно сложения, таблица сложения однозначных чисел. Пусть х = а ∙10 + а ∙10 +…+а ∙10+а и у = bп∙10п+ bп-1∙10п-1 +…+ + b ∙10+b . Как видно из суммы, количество цифр в записях чисел х и у одинаково. Наибольший показатель 10 в обоих случаях равно п. Следует иметь в виду, если десятичные записи слагаемых имеют разное количество цифр, то можно их уравнять в обоих слагаемых, приписав к числу, имеющему меньшее количество цифр несколько нулей впереди. Тогда х+у= =а ∙10 +а ∙10 +…+а ∙10+а+bп∙10п+bп-1∙10п-1+b ∙10+b . Преобразуя сумму на основе коммутативности и ассоциативности сложения, а также дистрибутивности умножения относительно сложения получим: х+у= =(а + bп )∙10 +(а + bп-1)∙10 +…+ (а1+ b )∙10+(а0+ b ). Если каждая из сумм аi+bi 9, где i=0;1;…;п, то операцию сложения можно считать законченной, в чем и заключается суть алгоритма сложения многозначных чисел без перехода через разряд. Например, 327+541= =(3·102+2·10+7)+(5·102+4·10+1)=(3·102+5·102)+(2·10+4·10)+(7+1)=(3+5)·102+ +(2+4)·10+(7+1)=8·102+6·10+8=868. Если сумма аi+bi 10, тоследует представить аi+bi в виде аi+bi=10+сi, где 0<сi 9. Но тогда (аi+bi)·10i=(10+сi)·10i=10i+1+сi·10i. Следовательно, слагаемые (аi+1+bi+1)·10 i+1+ (аi+bi)·10i суммы х+у могут быть заменены на (аi+1+bi+1+1)·10i+ сi·10i. После этого рассматриваем коэффициенты а + bп ,а + bп-1,…, аi+2+ +bi+2, аi+1+bi+1+1, снова выбираем наименьшее s, при котором коэффициент больше 9, и повторяем описанную процедуру. Через п шагов получим, что х+у=(cn+10)·10n+…+c0, где cn 0 или х+у= 10п+1+сп·10п+…+с0, где 0 сп<10, в чем и заключается суть алгоритма сложения многозначных чисел с переходом через разряд. Например, 497+586=(4·102+9·10+7)+ +(5·102+8·10+6) = (4·102+5·102)+(9·10+8·10)+(7+6) = (4+5)·102+(10+7)·10+ +(10+3)=(4+5)·102+102+(7·10+10)+3=(4+5+1)·102+(7+1)·10+3=10·102+8·10+3= =103 +80+3=1000+80+3=1083. Описанный выше процесс сложения позволяет сформулировать алгоритм сложения натуральных чисел, записанных в десятичной системе счисления, следующим образом. * Записывают слагаемые «столбиком», т.е. второе слагаемое под первым так, чтобы соответствующие разряды находились друг под другом. * Складывают цифры (для краткости здесь и далее употребляется термин «цифра» вместо словосочетания «однозначное число, изображаемое цифрой») разряда единиц. Если сумма меньше десяти, тогда ее записывают в разряд единиц ответа и переходят к следующему разряду (десятков). * Если сумма цифр единиц больше или равно десяти, то ее представляют в виде а + b =10+ с0, где с0 однозначное число и его записывают в разряд единиц ответа и прибавляют 1 к цифре десятков первого слагаемого, после чего переходят к разряду десятков. * Повторяют те же действия с десятками, потом сотнями и т. д. Процесс заканчивается, когда окажутся сложенными цифры старших разрядов. При этом, если последняя сумма оказывается больше или равно десяти, то приписывают впереди обоих слагаемых нули, увеличивают нуль перед первым слагаемым на 1 и выполняют сложение 1+ 0. * Читают ответ. Теоретической основой алгоритма вычитания многозначных чисел является принцип записи чисел в десятичной системе счисления. Кроме того свойства вычитания и умножения, таблица сложения однозначных чисел. Пусть х=а ∙10 +а ∙10 +…+ а ∙10+а и у= bп∙10п+bп-1∙10п-1+…+b ∙10+b . Тогда х-у= =а ∙10 +а ∙10 +…+ а ∙10+а0 - (bп∙10п+bп-1∙10п-1+b ∙10+b ). Преобразуя разность на основе дистрибутивности умножения относительно вычитания, а также коммутативности и ассоциативности сложения (рассматривая разность как алгебраическую сумму) получим: х-у=(а - bп )∙10 +(а - bп-1)∙10 +…+(а1 - b )∙10+(а0 - b ). Если для всех i выполняется условие аi bi, где i=0;1;…;п, то операцию вычитания можно считать законченной, в чем и заключается суть алгоритма вычитания многозначных чисел без перехода через разряд. Например, 947-842= =(9·102+4·10+7)-(8·102+4·10+2)=(9·102-8·102)+(4·10-4·10)+(7-2)=(9-8)·102+ +(4-4)·10+(7-2)=1·102 +0·10+5=105. Если же аi bi не выполняется для всех i, то берем наименьшее i , для которого аi <bi. Пусть s – наименьший индекс, такой, что s>i и аs 0, а as-1=…=ai+1=0, имеет место равенство as·10s=(as-1)·10s+9·10s-1+…+9·10i+1+ +…+10·10i. Поэтому выражение (аs-bs) ·10s +…+ (ai-bi) ·10i можно заменить на (аs-bs-1) ·10s +(9-bs-1) ·10s-1+…+(9-bi+1) ·10i+1+ …+ (ai +10 -bi) ·10i. Изаi< bi 0<10+ai -bi<10и0 bt 9 0 9-bt<10, гдеi+1 t Применяя далее те же преобразования к коэффициентам а - bп,…,аs-bs -1, через п шагов придем к записи разности х-у в виде х-у=сп·10п+сп-1·10п-1+…+с0, где для всех i выполняется неравенство 0 =(3·103+0·102+0·10+1) - (1·103+7·102+9·10+8) = (3-1)·103 + (0·102-7·102) + +(0·10-9·10)+ (1-8)= (2-1) ·103+(9 ·102 +0·102-7·102) + (9·10 + 0·10 -9·10) + +(10+1-8)= 1·103 +(9+0-7)·102 +(9+0-9) ·10+(11-8)= 1·103+2·102+0·10+3=1203. Описанный выше процесс позволяет сформулировать алгоритм вычитания многозначных чисел, записанных в десятичной системе счисления, следующим образом. * Записывают уменьшаемое и вычитаемое «столбиком», т.е. вычитаемое под уменьшаемым так, чтобы соответствующие разряды находились друг под другом. * Если цифра в разряде единиц вычитаемого не превосходит соответствующей цифры уменьшаемого, то вычитают ее из цифры уменьшаемого и записывают разность в разряде единиц ответа, после чего переходят к следующему разряду. * Если же цифра в разряде единиц вычитаемого больше чем цифра единиц уменьшаемого, т.е. b > а , а цифра десятков уменьшаемого отлична от нуля, то уменьшают цифру десятков на 1, одновременно увеличив цифру единиц уменьшаемого на 10. После чего вычитают из числа 10 + а число b и записывают разность в разряде единиц ответа, далее переходят к следующему разряду. * Если цифра единиц вычитаемого больше чем цифра единиц уменьшаемого, и цифры, стоящие в разряде десятков, сотен и т. д. уменьшаемого, равны нулю, то берут первую отличную от нуля цифру в уменьшаемом (после разряда единиц). Уменьшают ее на 1, все цифры в младших разрядах до разряда десятков включительно, увеличивают на 9, а цифру в разряде единиц – на 10. Вычитают из числа 10+ а число b , записывают разность в разряде единиц ответа и переходят к следующему разряду. * В следующем разряде повторяют описанный процесс. * Процесс вычитания заканчивается, когда производят вычитание из старшего разряда уменьшаемого. * Читают ответ. Алгоритм умножения зависит от особенностей множителей. Поэтому алгоритм умножения обоснуют в различных случаях, а именно: умножение многозначного числа на однозначное число; умножение многозначного числа на число вида 10к; умножение многозначного числа на число вида у·10к, где у - однозначное число; умножение многозначного числа на многозначное число. а) Алгоритм умножения многозначного числа на однозначное число опирается на способ записи чисел в десятичной системе счисления. А также на таблицу умножения однозначных чисел, законы сложения и умножения, таблицу сложения однозначных чисел. Пусть х= а ∙10 + +а ∙10 +…+а ∙10+а . Надо умножить его на однозначное число у, т.е. х∙ у=( а ∙10 + +а ∙10 + +…+ а ∙10+а )∙у. Преобразуем произведение на основе дистрибутивности умножения относительно сложения, а также коммутативности и ассоциативности умножения: х∙у=а ∙10 ∙у+а ∙10 ∙у+…+а ∙10∙у+а ∙у= =(а ∙у)∙10 +(а ∙у)∙10 +…+(а ∙у)∙10+а ∙у. Заменяя по таблице сложения все произведения аi∙y (где0 i Например, 396·4=(3·102+9·10+6)·4=(3·4)·102+(9·4)·10+6·4=12·102++36·10+24= =(1·10+2)·102+(3·10+6)·10+(2·10+4)=1·103+(2+3)·102+(6+2)·10+4=1000+80+4= =1584. б) Алгоритм умножения многозначного числа на число 10к основан на принцип записи чисел в десятичной системе счисления, на правило умножения степеней и законы умножения. Пусть х= а ∙10 + +а ∙10 +…+ а ∙10+а . Надо умножить его на число у=10к.х∙у=(а ∙10 +а ∙10 +…+а ∙10+а )∙10к. Преобразуем произведение: х∙10к=а ∙10 ∙10к+а ∙10 ∙10к+…+а ∙10∙10к+а ∙10к=а ∙10 +к+а ∙10 +к-1+ +…+а ∙10к+0∙10к-1+0∙10к-2+…+ 0∙10+0, т.е. умножение многозначного числа х на число 10ксводится приписыванию к десятичной записи данного числа к нулей. Например, 237·103=(2·102+3·10+7)·103=2·102·103+3·10·103+7·103=2·105+ +3·104+7·103=200000+30000+7000=237000. в) Алгоритм умножения многозначного числа на число у·10к, где у – однозначное число, опирается на алгоритм умножения на однозначное число и на число 10к. Пусть х= а ∙10 + +а ∙10 +…+ а ∙10+а . Надо умножить его на число у·10к. жүктеу/скачать 184,15 Kb. Достарыңызбен бөлісу:
|