Называется определенный способ записи чисел. Из Базового курса информатики вы знакомы с историей систем счисления, знаете, что системы счисления бывают позицио icon

Называется определенный способ записи чисел. Из Базового курса информатики вы знакомы с историей систем счисления, знаете, что системы счисления бывают позицио


3 чел. помогло.
Смотрите также:
Это способ записи чисел и соответствующие ему правила действий над числами...
Конкурс «Компьютерный урок» Учитель информатики: Тема урока: «Системы счисления»...
Урок информатики по теме "Системы счисления. Позиционные и непозиционные системы счисления...
Урок информатики по теме "Системы счисления. Позиционные и непозиционные системы счисления...
№1: Системы счисления. Перевод чисел из системы в систему...
Экзаменационные вопросы по курсу “Методы программирования” Iкурс, 2004 г...
Основанием. Основание позиционной системы счисления это количество различных знаков или символов...
Основанием. Основание позиционной системы счисления это количество различных знаков или символов...
Решение задач по теме «Системы счисления»...
Доклад №1. «Происхождение систем счисления»...
Урок по информатике "Двоичная система счисления"...
Курса



Загрузка...
страницы:   1   2   3   4
скачать
1.3. Представление чисел


1.3.1. Системы счисления


Системой счисления или нумерацией называется определенный способ записи чисел. Из Базового курса информатики вы знакомы с историей систем счисления, знаете, что системы счисления бывают позиционными и непозиционными. Вам также известно, что привычная для нас система счисления называется десятичной позиционной системой, что в компьютере для представления чисел и выполнения вычислений используется двоичная система счисления.

Числа заключают в себе количественную информацию. Запись чисел по правилам определенной системы счисления есть способ кодирования чисел. От способа кодирования зависит размер кода, т.е. количество цифр в записи числа, а также правила выполнения вычислений. Одной из главных проблем, которую нужно было решить изобретателям ЭВМ, это проблема представления чисел в памяти компьютера и алгоритма их обработки (вычислений) процессором. Для понимания того, как были решены эти проблемы нужно знать принципы организации систем счисления.

^ Основные понятия позиционных систем счисления

Цифрами называют символы, используемые для записи чисел. Алфавитом системы счисления называется совокупность всех цифр. Количество цифр, составляющих алфавит, называется его размерностью.

В записи многозначного числа цифры, стоящие в разных позициях, имеют разный вес. Так в целом десятичном числе 325 тройка означает три сотни, двойка – два десятка, пятерка - пять единиц: 325=3·100 + 2·10 +5·1. Такая запись называется развернутой формой записи числа: число записывается в виде суммы, в которой каждое слагаемое – это цифра, умноженная на свой вес. Вот еще пример развернутой записи смешанного десятичного числа:

6248,547 = 6·1000 + 2·100 + 4·10 + 8·1 + 5·0,1 + 4·0,01 + 7·0,001= 6·103 + 2·102 + 4·101 + 8·100 + 5·10-1 + 4·10-2 + 7·1-3

В десятичной системе счисления веса равны степеням десятки (положительным и отрицательным). Каждая позиция в записи числа называется разрядом числа. Разряды нумеруются в целой части числа положительными целыми числами, начиная от нуля, в дробной части – отрицательными числами, начиная от минус единицы:

разряды: 3 2 1 0 -1-2-3

число: 6248,547

Здесь номера разрядов указаны маленькими цифрами сверху. Отсюда видно, что веса соответствующих цифр равны десяти в степени, равной номеру разряда, в котором стоит эта цифра.

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


… 109, 108, 107, 106, 105, 104, 103, 102, 101, 100, 10-1, 10-2, 10-3, …

Запись числа в развернутой форме еще называют разложением числа по базису.

Система счисления именуется традиционной, если ее базис образует геометрическую прогрессию. Знаменатель этой прогрессии называется основанием системы счисления. У традиционных систем счисления знаменатель базиса совпадает с размерностью ее алфавита.


^ Основание десятичной системы счисления равно десяти т.к. размерность ее алфавита и знаменатель базиса равны десяти.


По такому же принципу организованы все другие традиционные системы счисления. Наименьшим основанием для позиционной системы является 2 – двоичная система. Система с основание 1 не может быть позиционной, поскольку для нее невозможно построить базис - единица в любой степени равна единице. Базис двоичной системы счисления выглядит так:


… 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 2-1, 2-2, 2-3, …

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


Размерность алфавита равна основанию системы счисления. Вот несколько примеров позиционных систем и их алфавитов:


Основание

Название

Алфавит

2

Двоичная

0 1

3

Троичная

0 1 2

8

Восьмеричная

0 1 2 3 4 5 6 7

16

Шестнадцатеричная

0 1 2 3 4 5 6 7 8 9 A B C D E F


Если n – основание системы не большее десяти, то в алфавите используются n первых арабских цифр. Если основание превышает 10, то в качестве дополнительных цифр выступают буквы латинского алфавита по порядку.

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


в любой позиционной системе счисления ее основание записывается как 10.


Например: 102=2, 103=3, 108=8, 1016=16 и т.д.


Задача 1. Число в троичной системе счисления: 2011,13 нужно перевести в десятичную систему, т.е. определить равное ему число в десятичной системе.


Разложим данное число по базису троичной системы счисления, т.е. запишем его в развернутой форме и вычислим полученное выражение по правилам десятичной арифметики:

2011,13= 2·33+0·32+1·31+1·30+1·3-1=54+3+1+1/3=


Задача 2. Шестнадцатеричное число 2AF,8C16 перевести в десятичную систему.


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


2AF,8C16=2·162+10·16+15·160+8·16-1+12·16-2=512+160+15+1/2+3/64= 687,546875


Задача 3. Двоичное число 1010101111,1000112 перевести в десятичную систему.


1010101111,1000112=1·29+1·27+1·25+1·23+1·22+1·2+1+1·2-1+1·2-5+1·2-6= 512 + 128 + 32 + 8 + 4 +2 + 1 +1/2 + 1/32 +1/64 =687,546875.


Обратите внимание, что результат тот же, что и в задаче 2. Значит двоичное число из данной задачи равно шестнадцатеричному числу из задачи 2. К этому обстоятельству мы еще вернемся.

Схема Горнера и перевод чисел

Недесятичное число можно быстро перевести в десятичную систему и с помощью простого калькулятора. Такой перевод связан с применением так называемой схемы Горнера для вычисления алгебраических многочленов. Сначала рассмотрим перевод целого числа на примере восьмеричного числа 2317458. Запишем его в развернутой форме и преобразуем полученную сумму к эквивалентной скобочной форме:


2317458 = 2·85+3·84+1·83+7·82+4·8+5=((((2·8+3)·8+1)·8+7)·8+4)·8+5=78821

Раскройте мысленно скобки в записанном выражении, и вы увидите, что получится то же разложение по базису восьмеричной системы счисления. Но зато скобочное выражение очень просто вычислять. На калькуляторе нужно последовательно слева направо выполнять умножения и сложения. Порядок нажатия клавиш на калькуляторе будет таким:


2

×

8

+

3

×

8

+

1

×

8

+

7

×

8

+

4

×

8

+

5

=


В этом примере было выполнено пять умножений и пять сложений. Такой способ вычисления называется схемой Горнера.

В общем виде алгебраический многочлен n-й степени и его преобразование к скобочной форме выглядит так:



Из этой формулы следует, что алгебраический многочлен n-й степени можно вычислит за n операций умножения и n операций сложения. Это самый оптимальный способ вычисления.

Схему Горнера можно применить и для перевода дробных чисел. Покажем на примере двоичного числа 0,1101012. Запишем число в развернутой форме и выполним тождественные преобразования, приводящие выражение к скобочной форме:


0,1101012 = 1·2-1+1·2-2+0·2-3+1·2-4+0·2-5+1·2-6 = 1·2-6+0·2-5+1·2-4+0·2-3+1·2-2+1·2-1 =

=(((((1/2+0)/2+1)/2+0)/2+1)/2+1)/2= 0, 828125


Полученное выражение также поддается последовательному вычислению на калькуляторе: шесть операций деления и пять – сложения. Клавиши нажимаются в таком порядке:

1

/

2

+

0

/

2

+

1

/

2

+

0

/

2

+

1

/

2

+

1

/

2

=


Прибавление нулей можно не делать, тогда число операций сократиться.


^ Пример нетрадиционной системы счисления

В качестве примера нетрадиционной системы счисления рассмотрим так называемую фиббоначиевую систему. Базисом этой системы является следующий числовой ряд: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … Он называется рядом Фибоначчи или числами Фибоначчи. Ряд Фибоначчи строится следующим образом: первые два числа задаются как начальные значения: F1=1, F2=2. Каждое следующее число равно сумме двух предыдущих чисел: F3=F2+F1, F4=F3+F2, F5=F4+F3 и т.д.

^ Базис фибоначчиевой системы не является геометрической прогрессией, как у традиционных систем счисления. Алфавит фибоначчиевой системы состоит из двух цифр: 0 и 1, как у двоичной системы счисления. Можно доказать, что в фибоначчиевой системе представимо любое целое число. В следующей таблице для сравнения приводятся первые 10 целых чисел в десятичной, двоичной и фибоначчиевой системах счисления:

Таблица 1.3

Десятичная с.с.

0

1

2

3

4

5

6

7

8

9

Двоичная с.с.

0

1

10

11

100

101

110

111

1000

1001

Фиббонач. с.с.

0

1

10

100

101

1000

1001

1010

10000

10001


Отметим важную особенность фибоначчиевой системы: неоднозначность представления некоторых целых чисел в этой системе. Например, число 3 можно записать двумя способами: 3=11fib=100fib. А число 8 можно записать тремя способами: 8=10000fib=1100fib=1011fib. Такое свойство системы называется избыточностью. Традиционные системы счисления не имеют избыточности. Для автоматической обработки данных избыточность оказывается полезным свойством. Благодаря избыточности можно обнаруживать потерю данных, возникающую из-за технических сбоев. Отсюда интерес к фибоначчиевой системе счисления со стороны конструкторов вычислительной техники.


Система основных понятий


^ Позиционные системы счисления

Традиционные системы: базис – геометрическая прогрессия; основание p – знаменатель базиса; размерность алфавита = основанию системы

Развернутая форма записи числа:



αi – цифра i-го разряда числа; p – основание системы счисления (p≥2)

^ Схема Горнера – быстрый алгоритм перевода p-ичного числа в десятичное

Целое число

Дробное число





^ Нетрадиционная система (пример): фибоначчиева система счисления

Базис

F1=1, F2=2, F3 = F2+F1, F4 = F3+F2,…, Fi = Fi-1+Fi-2,… →

1, 2, 3, 5, 8, 13, 21, 34, …– числа Фибоначчи

Алфавит:

0, 1

^ Фибоначчиева система счисления – избыточна; традиционные системы – не избыточны


Вопросы и задания

1. Определите основные понятия систем счисления: традиционные системы, нетрадиционные системы; цифра, алфавит системы, основание системы.

2. Почему развернутую форму записи числа называют разложением по базису?

3. Чему будет равно: 1/3 при переводе в троичную систему, 1/5 - в пятеричную систему, 1/8 - в восьмеричную систему, 1/16 - в шестнадцатеричную систему?

4. Что общего между результатами вычисления следующих выражений: 1112+12, 2223+13, 7778+18, FFF16+116 ?

5. Назовите предыдущие значения в натуральном ряде чисел для следующих значений: 1005, 1007, 1009 .

6. В таблице 1.3 для всех чисел в диапазоне от 0 до 9 приведено лишь по одному способу представления в фибоначчиевой системе счисления. Для тех чисел, представление которых неоднозначно, запишите все варианты.

7. Составьте программу вычисления n-го элемента из ряда чисел Фибоначчи (n>2) согласно определению ряда: F1=1, F2=2, Fi=Fi-1+Fi-2, i=3,4,… Массив в программе не использовать.

8*. Составьте программу перевода целого числа из фибоначчиевой системы счисления в десятичную систему.

9**. Составьте программу перевода целого десятичного числа в фибоначчиеву систему счисления.


^ 1.3.2. Перевод десятичных чисел в другие системы счисления


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

Сначала получим правила перевода целого числа. Обозначим целое число через Х. Основание системы счисления, в которую будем переводить, обозначим p. В результате перевода получится (n+1)- разрядное число. Запишем это следующим образом:





Здесь α0 обозначает цифру нулевого разряда числа, α1 – цифру первого разряда и т.д. Значения этих цифр лежат в диапазоне от 0 до р-1. Запишем значение числа в системе p в развернутом виде и преобразуем к скобочной форме.


=



Отсюда нетрудно понять, что α0 равно остатку от целочисленного деления Х на р, а Х1 – частное от целочисленного деления Х на р. Применяя символику языка Паскаль, запишем: α0=X mod p, X1=X div p. Здесь div – знак операции целого деления, а mod – остатка от деления. Таким образом, найдена α0 - цифра нулевого разряда числа в p-ичной системе.

Теперь запишем число Х1 в скобочной форме:




По аналогии с предыдущим следует, что α1=X1 mod pостаток от деления Х1 на р; X2=X1 div p. Найден α1 - первый разряд искомого числа.

Продолжая далее целочисленные деления на р с выделением остатка, последовательно будем получать искомые цифры р-ичного числа. Процесс закончится, когда в результате деления нацело (div) получится ноль. Последний остаток будет равен αn – старшей цифре числа.

Задача 1. Перевести число 58 в троичную систему счисления.

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

58 : 3 = 19 (1)

19 : 3 = 6 (1)

6 : 3 = 2 (0)

2 : 3 = 0 (2)


Окончательный результат такой: 58=20113. Это равенство мы уже получали в предыдущем параграфе.


Теперь рассмотрим перевод десятичной дроби в систему счисления с основанием р. Пусть Y – дробное десятичное число: Y<1. Очевидно, что в системе с основание р оно также будет дробным числом, поскольку 1 в любой системе счисления обозначает одну и ту же величину. Число, равное Y в системе р, запишем в развернутой форме.



Умножим это равенство на р:



Отсюда видно, что α-1 – это целая часть произведения Y·p, а Y1 – дробная часть этого произведения. Далее выпишем Y1 и умножим его на р:





Теперь α-2 стало целой частью произведения Yp. Очевидно, что дальше нужно умножать на р значение Y2. Выделив его целую часть, получим третью цифру дробного числа - α-3. И так далее.

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


Задача 2. Перевести десятичную дробь 0,625 в двоичную систему счисления.


Будем последовательно умножать это число на 2, выделяя целую часть произведения:

0,625·2 = 1,25

0,25·2 = 0,5

0,5·2 = 1,0

1 – первая цифра

0 – вторая цифра

1 – третья цифра

Дальше нули

В итоге получили: 0,625 = 0,1012


Вторая ситуация – получение периодической дробной части. В таком случае последовательные умножения надо продолжать до выделения периода.


Задача 3. Перевести число 0,123 в пятеричную систему счисления.


0,123·5=0,615

0,615·5=3,075

0,075·5=0,375

0,375·5=1,875

0,875·5=4,375

0

3

0

1

4




оставить комментарий
страница1/4
Дата02.10.2011
Размер0,55 Mb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2   3   4
средне
  2
отлично
  2
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх