ХКОИС
ХРРЦ
Регистрация
Забыли пароль?
Логин:
Пароль:
Поиск
Справочные сведения о системе образования Хабаровского края
Новости образования Хабаровского края
Информация и документы из министерства образования и науки Хабаровского края
Хабаровская краевая заочная физико-математическая школа
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ
Подготовка к олимпиадам по информатике
Подготовка к олимпиадам по информатикеТеоретические материалы > Системы исчисления
Системы исчисления
Язык математики формировался и развивался в течение многих столетий. Это касается как языка обозначений и формул, так и языка записи чисел. Способы записи чисел называются системами счисления.
Простейшая система счисления натуральных чисел является унитарная система, которая использует в качестве цифры единственную цифру, например, «палочку» /, обозначающую единицу. Тогда число 4, например, запишется в виде ////. В унитарной системе счисления удобно записывать и складывать небольшие числа. Сложение производится приписыванием нужного количества «палочек» справа от первого слагаемого:
////     //      //////,
4   +  2  =   6
Аналогично производится операция вычитания. Можно также легко записать операцию умножения : нужно записать a рядов по b «палочек» в каждом, а затем пересчитать полученное количество «палочек». Например,
 
, то есть .
Такой способ записи чисел эффективен только для небольших чисел. Поэтому возникла идея разбить числа на группы и каждую группу обозначить некоторым символом. Например, древние египтяне для записи единицы использовали знак /, для десятка знак , для сотни – знак C. Таким образом, число, например, 327 записывалось в виде . Подобный способ записи называется аддитивной системой счисления (отadditio – складывать). В Древнем Риме  в качестве знаков использовались следующие – I (1), V (5), X (10), C (50), D (100) и т.д. Например, число 20 записывается в виде XX, а число 40 имеет вид XL. Как видно, римская система счисления использовала не только сумму, но и разность чисел. При этом вычитаемое ставилось перед уменьшаемым. Обе системы, как аддитивная, так и римская имеет ряд недостатков: числа, записанные в такой системе, трудно складывать, вычитать и умножать, а при введении дробных чисел требуются новые символы.
Другая идея, позволяющая упростить форму записи чисел, состоит в том, чтобы значение каждой цифры в записи числа зависела от ее места (позиции), которую она занимает. Такая система счисления называется позиционной. Самая древняя позиционная система счисления известна нам по клинописным табличкам вавилонян, возраст которых боле  трех тысячелетий. Один вертикальный клинышек ▼ обозначал единицу, один горизонтальный ◄обозначал десятку. Числа от 1 до 59 записывались  следующим образом:
1
2
5
7
13
59
▼…
▼▼…
▼▼▼…
▼▼  
▼▼▼…
▼▼▼ 
   
◄▼▼▼…
 
◄◄▼▼▼
◄◄▼▼▼
    ▼▼▼
 Эти группы значков служили «цифрами» шестидесятеричной системы: каждая группа «цифр», стоящая перед предыдущей группой, означала , где k – позиция этой группы. Например, число , имело вид:
◄▼▼▼ ◄▼▼
◄▼▼     ◄
                 ◄
 
Современная нам десятичная система счисления возникла в Индии, позднее ее переняли арабы, а затем примерно с X века она начала использоваться в Европе. Удобство записи десятичных чисел и действий над ними обеспечили постепенное распространение метрической системы. И только с XVII века вошла в употребление современная алгебраическая символика.
Итак, в десятичной системе счисления n-значное натуральное число мы будем обозначать следующим образом:
 
, где  - цифры числа.
 
Эта запись означает, что число a можно представить в виде:
 
.
 
Аналогично, число, имеющее целую и дробную части, можно записать в виде:
 
d-ичные системы счисления
 
Выше мы рассмотрели десятичную систему счисления. Это – позиционная система, цифрами которой служат девять цифр , а основанием – число 10. Рассмотрим позиционные системы с произвольным основанием d.
Пусть d – произвольное натуральное число, большее единицы. Примем это число за основание d-ичной системы. Для записи любого натурального числа в такой системе требуется dцифр от 0 до d-1. Тогда n-значное натуральное число имеет следующий вид:
        
.
Например: .
 
Перевод числа из десятичной в d-ичную систему
 
1 способ. Известно, что любое натуральное число можно представить в виде:
 
         ,
 
где q – неполное частное от деления aна b,r – остаток от деления.
Пусть  -d-ичная запись числа а.  Тогда  . Отсюда видно, что последняя цифра  - остаток от деления a на d, то есть .
 При этом неполное частное q будет равно числу  , то есть числу a с отброшенной последней цифрой. Разделив q на d, получим в остатке следующую цифру  и т.д.
 
Алгоритм метода
 
Шаг 1. найти остаток от деления a на d,
Шаг 2. заменить число a неполным частным. Если это число a<d, то алгоритм закончен. В противном случае перейти на шаг 1.
Например. Найдем 7-ричную запись числа 1303.Запишем последовательные деления в виде:
       
Остатки от деления на число 7 подчеркнуты двойной чертой. Выпишем ответ: . Сделаем проверку:      .                
2 способ. Проведем предварительные рассуждения.
1.Наибольшее n-значное число, записанное в d-ичной системе, есть число . Действительно, самое большое такое число имеет все цифры, равные  (d-1): .       Например, самое большое 3-значное число, записанное в четверичной системе равно . 2.Таким образом, в записи числа a будет n цифр, если .
2.Выделим старший разряд этого числа: .
Второе слагаемое есть (n-1)-значное число, меньшее . Таким образом, чтобы найти первую цифру числа a, надо разделить a на  с остатком. Частное будет равно старшей цифре . Затем разделив остаток  на , найдем следующую цифру  и т.д.
3. Напомним, что целая часть числа x обозначается через . Разность  называется дробной частью числаx. Очевидно, что  равна неполному частному от деления a на b. Например, .
Сформулируем теперь алгоритм перевода десятичного числа в d-ичное.
 
Алгоритм перевода десятичного числа в d-ичное
 
Пусть n – наименьшее натуральное число, для которого .
Положим .
Шаг 1. Старшая цифра числа a равна .
Шаг 2. Положим   и вернемся на шаг 1.
Алгоритм выполняется за n шагов.
 
Пример. Записать число 1303 в семеричной системе.
Решение. Так как  , то n=4, d=7, a=1303.
1 итерация. Положим . Тогда первая цифра числа вычисляется по формуле  и .
2 итерация. Положим . Тогда вторая цифра числа вычисляется по формуле  и .
 
3 итерация. Положим . Тогда третья цифра числа вычисляется по формуле  и .
4 итерация. Положим . Тогда четвертая цифра числа вычисляется по формуле .
Выпишем ответ: . Отметим, что он совпал с ответом, полученным при записи числа первым способом.
 
 
 
 
 
Copyright © 2005–2017 ХабЦНИТ ТОГУ Отправить письмо
Создание сайтов в Хабаровске
пленка термоусадочная пвхwww мягкая мебель Днепропетровск