Главная Случайная страница



Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника







Вычислительные алгоритмы позиционной системы





 

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

Дополнительный разряд      
1-е слагаемое +
2-е слагаемое  
Сумма
Сложение единиц     9 + 6 = 1 5
Сложение десятков   9 + 7 + 1 = 1 7
Сложение сотен 9 + 8 + 1 = 1 8
Сложение десятков тысяч 9 + 0 + 1 = 1 0
                   

 

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

 
 
 

 



 


При вычитании двух чисел, записанных в десятичной позиционной системе счисления, вычитание начинается с единиц. Если уменьшаемое содержит больше (или столько же) единиц, чем вычитаемое, то вычитание выполняется. В противном случае один десяток уменьшаемого распаковывается, и его единицы переносятся в разряд единиц. Может, однако, оказаться, что уменьшаемое не имеет ни одного десятка, тогда распаковывается сотня, тысяча, десяток тысяч и т. д. Десяток доходит до единиц, а в остальные разряды попадают девятки, поскольку 10n – 1 = 99….9, где число девяток равно n.

 
 

          Распаковка десятков тысяч
  Распаковка         1   Распаковка десятков
  Уменьшаемое                
  Вычитаемое                    
  Разность                    
                                     
  Вычитание единиц   3 – 5 вычитание невозможно, следует распаковать десятку. Уменьшаемое принимает вид 1 0 0 1 13.
  Повторное вычитание единиц 13 – 5 = 8 Вместо двух десятков остался один
  Вычитание десятков 1 – 7 вычитание невозможно, следует распаковать один из высших разрядов – десяток тысяч. Уменьшаемое принимает вид 0 9 9 11 13.
  Повторное вычитание десятков 11 – 7 = 4 Вычитание сотен и тысяч 9 – 9 = 0    
        9 – 0 = 9    
                                     

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

а = аn·10n + аn – 1·10n – 1 + … + а2·102 + а1·101 + а0·100 и

b = bm·10m + bm – 1·10m – 1 + … + b2·102 + b1·101 + b0·100.

Используя законы коммутативности и дистрибутивности получим

a·b = a·(bm·10m + bm – 1·10m – 1 + … + b2·102 + b1·101 + b0·100) =

a·bm·10m +…+ a·bk ·10k + … + a·b2·102 + a·b1·101 + a·b0·100.

В итоге оказывается, что для получения результата нужно вычислить несколько произведений вида a·bk ·10k и сложить их. Поскольку операцией сложения мы уже владеем, достаточно разобраться в том, как вычисляются числа вида a·bk ·10k, где k = 0, 1, …, m, а число bk записывается одной цифрой.



Используя запись числа а в десятичной позиционной системе счисления получим

a·bk ·10k = (аn·10n + аn – 1·10n – 1 + … + а2·102 + а1·101 + а0·100)· bk ·10k =

n·10n+ kn – 1·10n+ k – 1 + …+ а2·10 k+2 + а1·10k+1 + а0·10 k+ 0·10 k– 1+…+ 0·100.)·bk.

Очевидно, что позиционная запись числа в скобках получается из записи числа а добавлением k нулей в младшие разряды.

Займёмся разбором вопроса об умножении произвольного натурального числа на число, которое записывается одной цифрой. Умножение начинается с младших разрядов. Для перемножения чисел-цифр (аi и bk) используется таблица умножения. Получаемые при этом старшие разряды добавляются к следующему произведению чисел-цифр (аi+1 и bk).

       
 
Таблица умножения
 

 

 
Умножение на число-цифру  
                       
=
            Дополнительно получено  
Умножение единиц 6 7 = 42 4 десятка  
Десятки 7 7 + 4= 49 + 4= 53 5 сотен  
Сотни 8 7 + 5= 56 + 5= 61 6 тысяч  
Тысячи 9 7 + 6= 63 + 6= 69 6 дес.тысяч  
                           

 

 

 


Умножение чисел в десятичной позиционной системе счисления
                                           
Перемножаемые числа записываются одно под другим. Далее поочерёдно вычисляются произведения первого сомножителя на слагаемые второго, имеющие вид bk ·10k. Все произведения выписываются одно под другим и суммируются.            
             
           
      +   0
        0 0
       
                     
    В записи умножения столбиком нули младших разрядов опускаются, но позиционные сдвиги соблюдаются.
     
                       
1-е слагаемое             =  
2-е слагаемое       =    
3-е слагаемое   =    
                                             

Деление двух чисел, записанных в десятичной позиционной системе счисления, основывается на следующих соображениях. Важнейшим обстоятельством является то, что при делении с остатком любого натурального числа на 10k, где k+1 равно числу разрядов этого числа, частное равно старшей цифре этого числа: рk·10k + pk – 1·10k – 1 + … + p0·100 : 10k = рk·10k + r, где r < 10k.

Пусть заданы два числа, записанных в позиционной системе счисления числа а = аn·10n + аn – 1·10n – 1 + … + а0·100 и b = bm·10m + bm – 1·10m–1 + … + b0·100.

Считая, известным их частное a : b, а также число разрядов k+1 в его записи, мы можем найти цифру старшего разряда, разделив с остатком a : b на 10k. Тот же самый результат будет получен, если разделить с остатком a на b∙10k.

Пусть q = qk·10k + qk – 1·10k–1 + … + q2·102 + q1·101 + q0·100 – запись частного в позиционной системе счисления. Тогда верно выражение а = (b∙10k)·qk + rk, (где rk < b∙10k). Его смысл как раз и состоит в том, что при делении с остатком числа а на число b∙10k (при некотором, изначально неизвестном, значении k) может быть получена цифра старшего разряда частного a : b.

Остаток rk равен а – (b∙10k)·qk = qk – 1·10k – 1 + … + q2·102 + q1·101 + q0·100. Точно так же рассуждения, применённые к числу rk, позволяют с помощью деления с остатком на b∙10k–1 найти следующую цифру qk–1в записи частного. При этом будет получен остаток rk–1 = qk–2·10k–2 + … + q2·102 + q1·101 + q0·100. С его помощью можно найти очередную цифру qk – 2. Продолжая этот процесс, можно найти все цифры частного. Последний остаток определяется тем, что он меньше делителя b.

Итак, деление одного натурального числа на другое распадается на несколько однотипных шагов. Характер каждого шага таков: делимое нужно домножить на некоторую степень десяти, чтобы при делении делимого на полученное число частное было меньше 10. Умножение числа на степень десяти производится дописыванием нулей справа к десятичной записи числа. Нужно дописывать нули до тех пор, пока из делителя получается число меньшее, чем делимое. Затем подбирается частное, выражаемое одной цифрой, и вычисляется остаток.

Приведём пример выполнения данного шага. При делении 9876 на 19 дописыванием нулей получаем из делителя возрастающую последовательность чисел 190, 1900, 19000, … Из неё нужно выбрать самое большое число, не превосходящее делимого. Им является 1900. Умножим это число на числа, выражаемые цифрами: 1900·1 = 1900, 1900·2 = 3800, 1900·3 = 5700, 1900·4 = 7600, 1900·5 = 9500, 1900·6 = 11400. Последнее число больше делимого, поэтому частное равно 5. В итоге 9876 = 1900·5 + 376.

 

Деление чисел в десятичной позиционной системе счисления
                                           
                             
– частное Умножение ведётся от младших разрядов, деление – от старших
             
                                   
          1-й шаг   9876 = 1900·5 + 376
          2-й шаг   376 = 190·1 + 186
      – остаток   3-й шаг   186 = 19·9 + 15







Date: 2015-05-04; view: 604; Нарушение авторских прав



mydocx.ru - 2015-2021 year. (0.011 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию