Системы счисления и основы двоичных кодировок (стр. 2 из 7)
Как же вавилоняне записывали числа? Они писали палочками, вдавливая их в глину, поэтому основными графическими элементами были у них клинья. Первый обозначал единицы, второй - десятки.
Эти знаки очень наглядны, количество клинышков бросается в глаза, так что пересчитывать их не приходится. Но клинописное письмо очень неудобно для оценки величины промежутков между числами, а необходимость переписывать все от руки приводила к частым опискам. Знак разделения был необходим, и он появился. Начиная с некоторого времени, на вавилонских кирпичиках появляется значок ^ , соответствующий нашему нулю
Однако, введя "позиционную пробку" в середине чисел, вавилоняне так и не додумались ставить ее на конце. И до самого падения вавилонской культуры числа 1, 60, 3000 записывались одинаково.
Только индусы, заимствовавшие у них позиционную нумерацию, научились правильно использовать знак нуля, и, введя вместо 60 основание 10, дали счислению его современную форму.
Три тысячи лет назад индусы уже пользовались современной нумерацией, хотя в памятниках того времени и не упоминаются числа, большие 100000. В более поздних источниках встречаются значительно большие числа - до ста квадриллионов (1017). В одной из сравнительно молодых легенд о Будде говорится, что он знал названия чисел до 1054. Впрочем, индусы, по - видимому, не представляли себе бесконечности натурального ряда, они полагали, что существует какое -то наибольшее число, известное только богам.
Доказательство бесконечности числового ряда — заслуга древнегреческих ученых.
1.2 Непозиционные и позиционные системы счисления
Система счисления (Нумерация) - это способ представления числа символами некоторого алфавита, которые называются цифрами.
Путем длительного развития человечество пришло к двум видам систем счисления: позиционной и не позиционной.
1.2.1 Непозиционная система счисления
В самой древней нумерации употреблялся лишь знак "|" для единицы, и каждое натуральное число записывалось повторением символа единицы столько раз, сколько единиц содержится в этом числе. Сложение в такой нумерации сводилось к приписыванию единиц, а вычитание - к их вычеркиванию. Для изображения сколько – нибуть больших чисел этот способ нумерации непригоден из - за своей громоздкости.
При начальном обучении в школе, когда счет ведется в пределах одного - двух десятков, этот способ нумерации успешно применяется (счет на палочках).
В непозиционных системах счисления смысл каждого знака сохраняется и не зависит от его места в записи числа.
К более современным непозиционным системам относят египетскую иероглифическую систему нумерации, в которой имелись определенные знаки для чисел: единица - I, десять - n, сто - ρ и так далее; эти числа называются узловыми. Все остальные натуральные числа, называемые алгоритмическими числами, записываются единообразно при помощи единственной арифметической операции - сложения. Например ,число 243 запишется в виде ρρ nnnnIII, 301 - в виде ρρρ I.
К непозиционным системам относят римскую нумерацию. За узловые числа в этой системе принимают числа: единица - I, пять - V, десять - X, пятьдесят - L, сто - С, пятьсот - D, тысяча - М. Все алгоритмические числа получаются при помощи двух арифметических операций: сложения и вычитания. Вычитание производится тогда, когда знак, соответствующий меньшему узловому числу, стоит перед знаком большего узлового числа, например, VI - шесть (5+1= 6), ХС – девяносто(100-10=90), 1704 - МОССIV, 193 -СХСШ, 687 - DCLXXXII.
В римской нумерации заметны следы пятеричной системы счисления, так как в ней имеются специальные знаки для чисел 5, 50 и 500.
При записи чисел использовался не только принцип сложения, но и принцип умножения.
Например, в старо — китайской системе счисления числа 20 и 30 изображались схематически, как 2,10 и 3,10. числа 10, 100, 1000 имели определенные специальные обозначения. Число 528 записывалось так: 5,100,2,10,8.
Наиболее удобными среди непозиционных систем счисления являются алфавитные системы нумерации. Примерами таких систем могут служить ионийская система (Древняя Греция), славянская, еврейская, грузинская и армянская.
Во всех алфавитных системах существенным является обозначение специальными символами - буквами в алфавитном порядке всех чисел от 1 до 9, всех десятков от 10 до 90 и всех сотен от 100 до 900. Чтобы отличать запись чисел от слов над буквами, обозначающими цифры, в греческой и славянской нумерации ставилась черта.
В греческой системе счисления число 543 записывалось: φμγ (φ - 500, μ- 40, γ- 3). В римской системе счисления это число записывается в виде DXLIII, в египетской иероглифической - в виде ρρρρρ nnnIII.
Из этого примера видно преимущество алфавитной нумерации, в которой используется цифровой принцип обозначения единиц, десятков, сотен.
В записи больших чисел в алфавитной системе уже виден переход к позиционной системе записи. Например, 32543 записывалось так
 |
Наиболее удобными системами счисления оказались позиционные или поместные системы.
1.2.2 Позиционные системы счисления
Позиционная система счисления - это совокупность определений и правил, позволяющих записывать любое натуральное число с помощью некоторых значков или символов, каждый из которых имеет определенный смысл в зависимости от его места в записи числа (от его позиции). Чаще всего применяют позиционную систему счисления с фиксированным основанием. Основанием системы может быть любое натуральное число ρ, ρ>1
Систематической записью натурального числа N по основанию ρназывают представление этого числа в виде суммы:
N = аnρn+...+а1ρ, + а0
где аn, ..., а1, а0 - числа принимающие значения 0, 1, ..., ρ - 1, причем, аn≠0.
Позиционная система счисления с основанием ρ называется ρ — ичной (двоичной, троичной и так далее). На практике чаще всего применяется десятичная ρ= 10).
Для обозначения чисел 0, 1, ..., ρ - 1 в ρ - ичной системе счисления используют особые знаки, называемые цифрами. Древнеиндийские математики открыли нуль - особый знак, который должен был показать отсутствие единиц определенного разряда.
Для ρ - ичной системы счисления нужно ρ цифр. Если ρ < 10, то применяются те же обозначения цифр, что и в десятичной системе счисления (только берутся цифры, меньше основания системы).
В системах с основанием ρ > 10 для чисел, больших или равных 10, не вводят специальных символов, а используют десятичную запись этих чисел, заключая эту запись в скобки. Например, в четырнадцатеричной системе имеется четырнадцать цифр: 0, 1, 2, 3 ... 9, (10), (11), (12), (13).
В системе счисления с основанием ρ, так же как и в десятичной системе счисления, место, занимаемое цифрой, считая, справа налево, называется разрядом.
Число N= аnρn+ . . . +a1ρ +а0 содержит а0 единиц первого разряда, а1 единиц второго разряда, а2 единиц третьего разряда и так далее. Единица следующего разряда в ρ раз больше единицы предыдущего разряда.
Позиционные системы счисления удовлетворяют требованию возможности и однозначности записи любого натурального числа.
Теорема. Любое натуральное число N может быть записано в системе с основание ρ и притом единственным образом.
Доказательство:
1. Докажем существование представления любого натурального числа в виде
N=anρn+an-1ρn-1 + ... +аρ+а0 (1)
Доказательство проведем методом полной математической индукции.
Представление числа N в виде (1) возможно для первых р-1 натуральных чисел 1, 2,..., ρ-1, так как n=1 и число совпадает с данным числом. Представление числа в виде (1) для чисел 1, 2, . . . ,ρ-1, очевидно, возможны только единственным способом: 1=1, 2=2,. . . ,ρ-1=ρ-1.
Предположим, что все натуральные числа N≤k (к≥1) представимы в виде (1). Докажем что число к+1 так же представимо в виде (1). Для этого разделим с остатком число к+1 на ρ:
K+l=sρ+r, 0<г<ρ-1 (2)
где s - неполное частное и г - остаток.
Так как число s≤k, то оно по предположению индукции представимо в виде (1):
s = аnρn+ . . . +a1ρ +а0 (3)
где 1≤аn≤ρ -1, 0≤ ai≤ρ -l, (i=0,1,..,n-1)
Подставим выражения (2) и (3), получим:
k+l= (anρ+ ... +аiρ +а0) ρ + г = аnρ +... + aiρ +a0ρ +г (4)
где 1 ≤an≤ρ -1, 0≤aj≤ ρ -1, 0 ≤ г ≤ ρ -1 0=0,1,. . ,n-1)
Это выражение (4) дает представление числа к+1 в виде (1):
К+1=bn+1ρ n+1 + bnρ n + ... + b1ρ +b0
где b0 =r, bi+1- ai (i=0,l,.. ,n-l)
2. Докажем единственность представления любого натурального числа в виде (1).
Доказательство проведем методом математической индукции.
Для чисел 1, 2,... , ρ -1 представление в виде (1) единственно.
Предположим что для всех натуральных N≤k (к≥1) представление в виде (1) единственно. Докажем, что число к+1 может быть представлено в виде (1) только одним способом. Для этого разделим с остатком число к+1 на ρ:
K+l=sρ+r, 0<г< ρ -1 (5)
Предположим, что к+1 имеет два различных способа представления:
к+1=а nρ n + аn-1ρ n-1+ ....+ а1ρ +а() (6)
к+1 =bmρ m + bm-1ρ m-1 + ... + b1ρ +b0 (7)
Представим: равенства (6) и (7) в виде:
k+1= (а nρ n-1 + an-1 ρ n-2+ ... + а1)ρ+а0 (6*)
k+1 = (bmρ m-1 + bm-1ρ m-2+ ... + b)ρ+b0 (7*)