Занятие 3

Схема Горнера. Действия над числами в различных системах счисления

Повторение

Дайте определения позиционной и непозиционной систем счисления. Приведите примеры.
Какая запись числа называется развернутой? Приведите примеры.
Дайте определение алфавита, основания, базиса системы счисления. Приведите примеры.
Как перевести число в десятичную систему счисления?
Как перевести целое число из десятичной системы счисления?
Как перевести правильную дробь и смешанное число из десятичной системы счисления?
Какое минимальное основание должна иметь система счисления, если в ней могут быть записаны числа:

10, 21, 201, 1201;
403, 561, 666, 125;
22, 984, 1010, А219?

В каких системах счисления 10 – число нечетное?

Перевод чисел в десятичную систему счисления по схеме Горнера

Рассмотрим развернутую запись числа в троичной системе счисления: 12012₃=1*3⁴+2*3³+0*3²+1*3¹+2*3⁰. В первых четырех слагаемых имеется общий множитель 3, который можно вынести за скобки. Получим:
1*3⁴+2*3³+0*3²+1*3¹+2*3⁰=(1*3³+2*3²+0*3²+1)*3+2. Теперь этот же множитель можно вынести из первых трех слагаемых:
1*3⁴+2*3³+0*3²+1*3¹+2*3⁰=(1*3³+2*3²+0*3¹+1)*3+2=((1*3²+2*3¹+0)*3+1)*3+2. И, наконец:
1*3⁴+2*3³+0*3²+1*3¹+2*3⁰=(1*3³+2*3²+0*3¹+1)*3+2=((1*3²+2*3¹+0)*3+1)*3+2=(((1*3+2)*3+0)*3+1)*3+2.
На основе этой схемы можно вывести следующий алгоритм для перевода целых чисел в десятичную систему счисления:
Старшую цифру умножаем на основание, добавляем вторую цифру, результат умножаем на основание, добавляем третью цифру и так до тех пор, пока не прибавим последнюю цифру.
Результатом будет десятичная запись числа. Ясно, что полученное равенство будет справедливо для любых целых P-ичных чисел, а формулу можно записать в общем виде:
a_na_n-1a_n-2...a₁a_{0_p}=(...(a_n*p+a_n-1)*p+a_n-2)*p+...)+a₁)*p+a₀.
Эта формула и является иллюстрацией схемы Горнера для пероевода целых чисел в десятичную систему счисления.
Механизм вычислений можно представить так ( на рассмотренном выше примере):
1   2   0     1     2 (выписываем цифры числа в заданной системе счисления).
   1  5  15  46  140 (результат, полученный при умножении на основание и добавлении очередной цифры, записываем под соответствующей цифрой). Последнее число и будет ответом.
Действия над числами в различных системах счисления

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

1+0=1 1*0=0

1+1=10 1*1=1

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

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

1+1=2 1*1=1

1+2=10 2+2=11 1*2=2 2*2=11

Более привычный для нас вид имеют таблицы сложения и умножения в восьмеричной системе счисления:

Таблица сложения

1+1=2

1+2=3 2+2=4

1+3=4 2+3=5 3+3=6

1+4=5 2+4=6 3+4=7 4+4=10

1+5=6 2+5=7 3+5=10 4+5=11 5+5=12

1+6=7 2+6=10 3+6=11 4+6=12 5+6=13 6+6=14

1+7=10 2+7=11 3+7=12 4+7=13 5+7=14 6+7=15 7+7=16

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

1*1=2

1*2=2 2*2=4

1*3=3 2*3=6 3*3=11

1*4=4 2*4=10 3*4=14 4*4=20

1*5=5 2*5=12 3*5=17 4*5=24 5*5=31

1*6=6 2*6=14 3*6=22 4*6=30 5*6=36 6*6=44

1*7=7 2*7=16 3*7=25 4*7=34 5*7=43 6*7=52 7*7=61

А теперь представьте, что в первом классе вам нужно было бы выучить наизусть таблицы сложения и умножения в шестнадцатеричной системе счисления! Сколько бы времени вы на это затратили?

Таблица сложения

1+1=2

1+2=3 2+2=4

1+3=4 2+3=5 3+3=6

1+4=5 2+4=6 3+4=7 4+4=8

1+5=6 2+5=7 3+5=8 4+5=9 5+5=A

1+6=7 2+6=8 3+6=9 4+6=A 5+6=B 6+6=C

1+7=8 2+7=9 3+7=A 4+7=B 5+7=C 6+7=D 7+7=E

1+8=9 2+8=A 3+8=B 4+8=C 5+8=D 6+8=E 7+8=F 8+8=10

1+9=A 2+9=B 3+9=C 4+9=D 5+9=E 6+9=F 7+9=10 8+9=11 9+9=12

1+A=B 2+A=C 3+A=D 4+A=E 5+A=F 6+A=10 7+A=11 8+A=12 9+A=13 A+A=14

1+B=C 2+B=D 3+B=E 4+B=F 5+B=10 6+B=11 7+B=12 8+B=13 9+B=14 A+B=15 B+B=16

1+C=D 2+C=E 3+C=F 4+C=10 5+C=11 6+C=12 7+C=13 8+C=14 9+C=15 A+C=16 B+C=17 C+C=18

1+D=E 2+D=F 3+D=10 4+D=11 5+D=12 6+D=13 7+D=14 8+D=15 9+D=16 A+D=17 B+D=18 C+D=19 D+D=1A

1+E=F 2+E=10 3+E=11 4+E=12 5+E=13 6+E=14 7+E=15 8+E=16 9+E=17 A+E=18 B+E=19 C+E=1A D+E=1B E+E=1C

1+F=10 2+F=11 3+F=12 4+F=13 5+F=14 6+F=15 7+F=16 8+F=17 9+F=18 A+F=19 B+F=1A C+F=1B D+F=1C E+F=1D F+F=1E

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

1*1=1

1*2=2 2*2=4

1*3=3 2*3=6 3*3=9

1*4=4 2*4=8 3*4=C 4*4=10

1*5=5 2*5=A 3*5=F 4*5=14 5*5=19

1*6=6 2*6=C 3*6=12 4*6=18 5*6=1E 6*6=24

1*7=7 2*7=E 3*7=15 4*7=1C 5*7=23 6*7=2A 7*7=31

1*8=8 2*8=10 3*8=18 4*8=20 5*8=28 6*8=30 7*8=38 8*8=40

1*9=9 2*9=12 3*9=1B 4*9=24 5*9=2D 6*9=36 7*9=3F 8*9=48 9*9=51

1*A=A 2*A=14 3*A=1E 4*A=28 5*A=32 6*A=3C 7*A=46 8*A=50 9*A=5A A*A=64

1*B=B 2*B=16 3*B=21 4*B=2C 5*B=37 6*B=42 7*B=4D 8*B=58 9*B=63 A*B=6E B*B=79

1*C=C 2*C=18 3*C=24 4*C=30 5*C=3C 6*C=48 7*C=54 8*C=60 9*C=6C A*C=78 B*C=84 C*C=90

1*D=D 2*D=1A 3*D=27 4*D=34 5*D=41 6*D=4E 7*D=5B 8*D=68 9*D=75 A*D=82 B*D=8F C*D=9C D*D=A9

1*E=E 2*E=1C 3*E=2A 4*E=38 5*E=46 6*E=54 7*E=62 8*E=70 9*E=7E A*E=8C B*E=9A C*E=A8 D*E=B6 E*E=C4

1*F=F 2*F=1E 3*F=2D 4*F=3C 5*F=4B 6*F=5A 7*F=69 8*F=78 9*F=87 A*F=96 B*F=A5 C*F=B4 D*F=C3 E*F=D2 F*F=E1

Пользуясь таблицами, выполним: 31₈+52₈ и 31₈*52₈ . Применим обычное сложение и умножение "столбиком": . Произведем проверку, переведя слагаемые (множители) и результаты в десятичную систему счисления по схеме Горнера:
   3   1       5   2        1   0   3          2   0     3       2
   3   25      5   42      1   8   67      2   16   131   1050
Сложив в десятичной системе счисления числа 25 и 42, получим 67, а перемножив эти же числа, получим 1050, значит, действия выполнены правильно.
Задачи
К оглавлению