Системы счисления. Лекция 3

Содержание

Слайд 2

Значение и обозначение числа Число Значение (содержание) Обозначение (форма) Значение конкретного

Значение и обозначение числа

Число

Значение (содержание)

Обозначение (форма)

Значение конкретного числа – это числовая

величина, «чистая», отвлеченная от каких-либо измеряемых объектов и единиц измерения, количественная мера, выраженная в стандартных единицах.

Обозначение (форма, внешнее представление) числа – это его название или знак в некотором языке или системе обозначений, позволяющих отличать данное число от других.

9, IX, девять, nine, 1001(2)

Значение числа инвариантно (не зависит от обозначения).

Слайд 3

это система правил, позволяющих конструировать названия чисел (знаковые обозначения) некоторым регулярным

это система правил, позволяющих конструировать названия чисел (знаковые обозначения) некоторым регулярным

способом.
Непозиционные системы счисления возникли первыми, они основаны на простом суммировании «весов» – цифр - «разновесов», занятых в записи числа.
Например, римская с.с., где все цифры могут браться плюсом или минусом, в зависимости от позиции этой цифры относительно более «тяжелых».
IX, XI
Позиционные системы счисления : число цифр конечно, вклад каждой цифры зависит от «веса» ее позиции (разряда) в записи числа.

Система счисления (с.с.) -

Слайд 4

Представление целых чисел в позиционных системах счисления с произвольным основанием Общие

Представление целых чисел в позиционных системах счисления с произвольным основанием



Общие свойства b-ичных позиционных систем счисления (b-с.с.) определяются параметром b - основанием с.с., которое определяет количество цифр, используемых для записи числа:
от 0 до b – 1, если b ≤ 10.
Если b > 10, то используются буквы:
10 – A
11 – B
12 – C
13 – D
14 – E
15 – F

Слайд 5

0 ≤ ai i – индекс позиции (разряда), в которой расположена

0 ≤ ai < b,
i – индекс позиции (разряда), в

которой расположена цифра ai .
Запись числа называется k-значной, если индекс разряда первой значащей цифры числа равен k – 1.
Примеры
10011001(2), 248933, 7DAB(16),
123454(5) - неправильная запись

Запись целого числа

Слайд 6

Соотношение записи целого числа со значением S – запись числа. N(S)

Соотношение записи целого числа со значением

S – запись числа.
N(S) – его

значение.

S =

bi – явно указывают веса разрядов, определяющих вклад каждой цифры в значение числа,
bi называется единицей i-го разряда b-ичного числа.
ai – количество полных единиц i-го разряда, которое останется после вычета всевозможного числа единиц старших разрядов.

(2)

Слайд 7

Значение Ni равно количеству полных единиц i-го разряда в числе. Соотношение

Значение Ni равно количеству полных единиц i-го разряда в числе.

Соотношение записи

целого числа со значением

(2)

Слайд 8

N(10011(2))= 1⋅24+0⋅23+0⋅22+1⋅21+1⋅20 =19 N(10011(2))=(((1⋅2+0)⋅2+0)⋅2+1)⋅2+1=19 N(30A(16)) = 3⋅162+0⋅161+10⋅160 = 778 N(30A(16)) =(3⋅16+0)⋅16+10

N(10011(2))= 1⋅24+0⋅23+0⋅22+1⋅21+1⋅20 =19
N(10011(2))=(((1⋅2+0)⋅2+0)⋅2+1)⋅2+1=19
N(30A(16)) = 3⋅162+0⋅161+10⋅160 = 778
N(30A(16)) =(3⋅16+0)⋅16+10 = 778
N(30A(11)) =

?
N(30A(11)) = 373

Примеры

Слайд 9

Любое число однозначно представимо в виде цифр заданной b-с.с. Доказательство (от противного). Теорема 1

Любое число однозначно представимо в виде цифр заданной b-с.с.
Доказательство (от противного).

Теорема

1
Слайд 10

Вход: b > 1, k > 0 (число цифр), набор ak-1,

Вход: b > 1, k > 0 (число цифр), набор

ak-1, ak-2, … , a1, a0.
N := 0;
S := 1; (S – накапливает степень, N – значение)
цикл по i := 0 до k – 1
конец цикла;
Выход: N
2k операций *
k операций +

Алгоритм А1: (перевод b-ичного числа в 10-с.с.)

Слайд 11

Вход: b > 1, k > 0 (число цифр), набор ak-1,

Вход: b > 1, k > 0 (число цифр), набор

ak-1, ak-2, … , a1, a0
N := 0;
цикл по i от k-1 вниз до 0
N := N ⋅ b + ai ;
конец цикла;
Выход: N
k операций *
k операций +

Схема Горнера Алгоритм А2: (перевод b-ичного числа в 10-с.с)

Слайд 12

Вход: N ≥ 0, b > 1; i := 0; цикл

Вход: N ≥ 0, b > 1;
i := 0;
цикл
ai

:= N mod b; (mod – остаток от деления нацело)
N := N div b; (div – целое деление)
i := i + 1;
пока N ≠ 0;
k := i;
Выход: набор ai , k ( число значащих цифр)
минимальное число операций деления = k

Алгоритм A3: (перевод числа из 10-с.с. в b-с.с)

Слайд 13

325 Пример: перевод из 10-с.с. в 2-с.с. Целая часть | Остаток

325

Пример: перевод из 10-с.с. в 2-с.с.

Целая часть | Остаток от деления

на 2

325(10) = 101000101(2)

Слайд 14

Перевод числа из b1-с.с. в b2-с.с. 10-с.с.

Перевод числа из b1-с.с. в b2-с.с.

10-с.с.

Слайд 15

Если в дробной части числа конечное число знаков k, то нижний

Если в дробной части числа конечное число знаков k, то нижний


индекс суммы равен —к .
0.375=(3+(7+5/10)/10)/10=(3+(7+(5+0)/10)/10)/10

Представление действительных чисел

S =

Слайд 16

Связь дробной части числа со значением где i = k, … , 1;

Связь дробной части числа со значением

где i = k, … ,

1;
Слайд 17

Примеры N(«1.101(2)») = 1⋅20 +1⋅2-1 +0⋅2-2 +1⋅2-3 = 1 + 0.5

Примеры

N(«1.101(2)») = 1⋅20 +1⋅2-1 +0⋅2-2 +1⋅2-3
= 1 + 0.5

+ 0.125
= 1.625
Nf(«1.101(2)») =(1 +(0 +(1 +0)/2)/2)/2
= (1 + (0 + 0.5)/2 )/2
= (1 + 0.25) / 2 = 0.625
Nf(«0.01(3)») = 1⋅3-2 = = 0.(1)
Слайд 18

Вход: Nf ( 0 ≤ Nf 1; i := -1; цикл

Вход: Nf ( 0 ≤ Nf < 1), b >1;
i

:= -1;
цикл
([x]-взятие целой части числа)
( остается в том же диапазоне )
i := i – 1;
пока
k := i;
Выход: набор (число значащих цифр).
Алгоритм А4 может не завершиться, если данное число не представимо конечной дробью в b-с.с
Требуется k умножений (выражение Nf*b можно вычислять в цикле один раз и
хранить в промежуточной переменной).

Целая часть числа Nf*b (0 < Nf < 1) равна первой цифре дробной части числа Nf Алгоритм А4: перевод дробной части из 10-с. с. в b-с.с

Слайд 19

Пример:

Пример:

Слайд 20

Теорема Т2 Несократимая дробь p/q конечно представима в системе счисления с

Теорема Т2
Несократимая дробь p/q конечно представима в системе счисления с основанием

b в том и только в том случае, когда все числа из разложения q на простые множители входят в такое же разложение b (количество повторений не учитывается).
Пример
121/675 конечна в 15-с.с.:
675 = 33*52; 15 = 3*5;
1/675 = 5*15-3 = 0.005(15);
121*5/153 = (2*152 + 10*151 + 5)/153 = 2/151 + 10/152 + 5/153
121/675 = 0.2A5(15);
1/10 бесконечна в 2-с.с. !!!!
Слайд 21

Вход: b > 1, к > 0 (число дробных цифр), набор

Вход: b > 1, к > 0 (число дробных цифр), набор

(S накапливает степень, — значение )
цикл по i от -1 вниз до -k
;
конец цикла
Выход:
2k операций *, /
k операций +

Алгоритм А5: (перевод дробной части из b-с.с. в 10-с.с)

Слайд 22

Вход: b >1, k > 0 (число цифр), набор цикл по

Вход: b >1, k > 0 (число цифр), набор
цикл по

i от –k до -1
конец цикла;
Выход:
k операций + и /

Алгоритм А6: перевод дробной части из b-с.с. в 10-с.с. ( из формулы (7) по схеме Горнера)

Слайд 23

Число N в b-с.с. имеющее k дробных цифр, при умножении на

Число N в b-с.с. имеющее k дробных цифр, при умножении на

b становится целым (это умножение соответствует сдвигу точки на k позиций вправо)
Алгоритм А7
• найти целое N1 = N * b1k (умножением или сдвигом точки);
• выполнить для N1 один из алгоритмов А1 или А2, затем АЗ;
• разделить полученный результат на b1k в системе b2
Слайд 24

Перевести 101.101(2) в 10-с.с. 1) умножим на 23 → 101101(2) 2)

Перевести 101.101(2) в 10-с.с.
1) умножим на 23 → 101101(2)
2) переведем в

10-с.с. → 45
3) разделим: 45/8 = 5.625(10)
101.101=1*22+1*20+1*2-1+1*2-3=5+1/2+1/8=5.625

Пример

Слайд 25

Если основания двух систем счисления b1 и b2 связаны соотношением b2=

Если основания двух систем счисления b1 и b2 связаны соотношением

b2= b1m для некоторого натурального т, то такие системы счисления называются кратными.
Перевод числа из одной с. с. в другую для таких систем можно выполнить проще.
Сгруппируем цифры в b1-записи числа по m от точки влево и вправо (добавив при нехватке цифр нужное количество незначащих нулей):

Кратные системы счисления

Слайд 26

затем также сгруппируем слагаемые в формуле (5) (они содержат множитель b1

затем также сгруппируем слагаемые в формуле (5) (они содержат множитель b1

в степени, равной индексу цифры), вынесем за скобки из каждой группы i общий множитель
(b1im = (b1m)i = b2i)
и обозначим для каждой группы

Тогда значение исходного числа может быть представлено в виде:

N(S') = Ak’* b2k’ + … + Ai* b2i + ... + А0*b20 + А-1*b2-1+ … А-j b2-j,

что по определению совпадает со значением записи того же числа в b2-с.c. c цифрами Аi, если заметить, что Аi, действительно могут принимать все значения от 0 до b1m − 1 = b2 − 1.

Слайд 27

Таблицы соответствия последовательностей цифр кратных с.с.

Таблицы соответствия последовательностей цифр кратных с.с.

Слайд 28

Вход: b1 > 1, b2 = b1m, b1 - представление числа;

Вход: b1 > 1, b2 = b1m, b1 - представление числа;
•

разбить число на группы по т цифр, начиная от точки, в обе стороны (если в крайних группах цифр меньше т, добавить незначащие нули: в целой части спереди, в дробной сзади);
• заменить каждую группу b2-цифрой по формуле (8) или таблице.
Выход: b2 -представление исходного числа.

Алгоритм А8: перевод из меньшей кратной с.с. в большую

Слайд 29

Вход: b1> 1, b2= b1m; b2-представление числа; заменить каждую b2-цифру цепочкой

Вход: b1> 1, b2= b1m; b2-представление числа;
заменить каждую b2-цифру цепочкой

из т b1-цифр по формуле (8) или таблице;
отбросить незначащие нули слева и справа.
Выход: b1-представление исходного числа.

Алгоритм А9: перевод из большей кратной с.с. в меньшую

Слайд 30

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

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

и деления (в том числе, вычисления «столбиком») являются символьными, потому что оперируют входными, выходными и промежуточными данными как строками символов.
Символьные вычисления являются формальными в том смысле, что манипулируют только знаками, не обращаясь к их значениям.
Абстрагирование от смысла данных различной природы и описание алгоритма в терминах чисто символьных преобразований является одним из основных методов программирования обработки данных произвольной природы

Универсальные алгоритмы для арифметических операций

Слайд 31

Вход: две строки цифр, представляющие слагаемые; • выравнивание: расположить слагаемые одно

Вход: две строки цифр, представляющие слагаемые;
• выравнивание: расположить слагаемые одно под

другим в произвольном порядке так, чтобы разряды с одинаковым весом находились друг под другом; если какое-то число короче других слева или справа, дополнить его нулями;
• начальные установки:
обнулить цифру переноса в следующий разряд;
установить результат равным пустой строке;
• цикл по текущему разряду от младшего до старшего:
определить сумму переноса и цифр в столбце текущего разряда чисел; младшую цифру суммы записать в текущий разряд результата, старшую — в перенос;
конец цикла;
• окончание: если перенос не равен 0, то дописать перенос в начало результата
Выход: строка, представляющая результат.

Алгоритм А10: сложение двух чисел

Слайд 32

Единственное место в этом алгоритме, где присутствует обращение к значениям цифровых

Единственное место в этом алгоритме, где присутствует
обращение к значениям цифровых

символов, — это поразрядное сложение в цикле.
Действительно, из одного лишь вида знаков «2» и «3» нельзя извлечь информацию, что результатом их сложения будет знак «5».
Эти сведения можно задать, например, двумя таблицами сложения: в одной для каждой пары цифр записать младшую цифру результата, в другой — цифру переноса («0» или «1»);
исчерпав таким образом все немногочисленные случаи, можно заменить операцию сложения значений операцией выборки знака из таблицы.
Чтобы учесть сложение с переносом, можно завести две пары
таблиц или записать в каждую клетку по две цифры.
Слайд 33

Алгоритм А10 замечателен тем, что применим к произвольной позиционной с. с. при соответствующей замене таблиц сложения.

Алгоритм А10 замечателен тем, что применим к произвольной позиционной с. с.

при соответствующей замене таблиц сложения.
Слайд 34

Затраты памяти на хранение чисел и времени на выполнение операций с

Затраты памяти на хранение чисел и времени на выполнение операций с

ними зависят от длины записи числа в цифрах рабочей системы счисления.
Для заданной b-с. с. следующие величины:
kn — длина записи (натурального) числа N,
Nk — максимальное натуральное число, записываемое k цифрами,
связаны соотношениями:
kn = [logbN] + 1, где [x] — наибольшее целое, не превышающее x;
Nk = bk − 1.
Верхние оценки для размера результата арифметической операции
над парой целых чисел N1 и N2 (пусть N1 > N2):
для сложения и вычитания — kN1 +1,
для умножения — kN1 + kN2,
для деления — kN1 +1, (так как N2 > 1).
Слайд 35

В любой b-c.c. b записывается как «10(b)». Умножение на b сводится

В любой b-c.c. b записывается как «10(b)».
Умножение на b сводится к

дописыванию 0 справа к целому числу или сдвигу b-ичной точки на один разряд вправо.
Обратно: деление на b равносильно сдвигу b-ичной точки на один разряд влево, или отбрасыванию младшей цифры целого числа при делении нацело.
bk всегда представляется единицей с k нулями.
Умножение (деление) на bk сводится к сдвигу b-ичной точки на k разрядов вправо (влево).
Остатком от деления на bk является число, составленное из k младших цифр.
Примеры:
7 = 10(7)
54 = 10000(5)
1001.1101(2) ⋅ 23 = 1001.1101(2) ⋅ 1000(2) = 1001110.1(2)

Особенности умножения и деления на основание системы счисления

Слайд 36

Добавление k нулей справа и отбрасывание k младших цифр можно рассматривать

Добавление k нулей справа и отбрасывание k младших цифр можно рассматривать

как операции арифметического сдвига на k позиций.
В Си определены операции арифметического сдвига на k позиций, которые равносильны умножению или целочисленному делению на 2k.
<< — сдвиг влево
>> — сдвиг вправо
Примеры:
a = 5 << 3; /* после выполнения присваивания a будет иметь значение 40 */
b = 112 >> 4; /* b будет равно 7 */

Арифметические сдвиги

Слайд 37

Логическая аналогия Если сопоставить 0 – логическую «ложь», а 1 –

Логическая аналогия
Если сопоставить 0 – логическую «ложь», а 1 – «истину»,

то таблица сложения соответствует логической операции «исключающее или», а таблицы переноса и умножения – логической операции «и».
Минимаксная аналогия
a⋅b = min (a, b)
a + b = max (a, b) – min (a, b)
Умножение столбиком многозначных чисел в 2-с.с. реализуется с помощью сложения и сдвига:
1001001
1011
1001001
1001001
1001001
1100100011

Особенности двоичной арифметики

*

+

- Предыдущая
Активные формы здорового образа жизни
Следующая -
Работа частей и механизмов автомата

Похожие презентации

Решение квадратных уравнений
Свойства функции
Решение квадратных неравенств. 8 класс
Пересечение цилиндров
Преобразование выражений. 7 класс
задачи на нахождение процента от числа Выполнила Ученица 6 «В» средней школы №28 пос. Богородское Куницкая Екатерина Руководите
Бесконечные непериодические десятичные дроби (урок 10)
Подготовка к контрольной работе по теме: Сумма углов треугольника
Квадратные уравнения
Задача дискретного логарифмирования и криптосистемы на ее основе
Измерение углов
История математики
Число Пи
Признаки равенства прямоугольных треугольников
Обыкновенные дроби. Урок-соревнование «Крестики-нолики»
Математическая обработка экспериментальных данных
Первоначальные понятия геометрии
Применение производной и первообразной. Подготовка к ЕГЭ
Презентация по математике "Дифференциальное исчисление функции одной переменной" - скачать бесплатно
Презентация РАСТРОВАЯ И ВЕКТОРНАЯ АНИМАЦИЯ
Матрицы и действия с ними
Элементы математической статистики, комбинаторики и теории вероятностей. Формула бинома Ньютона
Правило Лопиталя
Таблица умножения и деления числа 6. Закрепление. Урок-сказка 3 класс
Организация вычислений с использованием относительных, абсолютных и смешанных ссылок
Нормальные формы формул алгебры высказываний
Задачи по математике
Решение текстовых задач
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть