Задача на одномерные массивы

При следующем делении  частного на основание q будут получены новое целое частное и новый остаток: А_p = А_q = (А_q)₂×q + b₁, где b₁ – вторая младшая цифра числа. Продолжая деление целых частных до нулевого значения, находят все цифры числа в  новой системе.

Правило перевода целого числа из одной системы  счисления в другую.

1. Пусть дано число А в системе счисления p. Для перевода его в систему счисления q необходимо последовательно делить данное число и получаемые целые частные на основание новой системы счисления (q), выраженные цифрами исходной системы (p), до тех пор, пока частное не станет равным нулю.
2. Полученные остатки, являющиеся цифрами числа в новой системе счисления, следует выразить цифрами алфавита этой системы.
3. Составить число в новой системе, начиная с последнего остатка.

 

 

Примеры

1. Перевести число А₍₁₀₎= 53 в А₍₂₎ .

 

53	2
52	26	2
1	26	13	2
	0	12	6	2
		1	6	3	2
			0	2	1	2
				1	0	0
					1

 

2. Перевести число А₍₁₀₎= 53 в А₍₈₎, а затем в А₍₂₎.

53	8
48	6	8
5	0	0
	6

Перевод восьмеричного  числа в двоичное проще выполнить, учитывая, что основание 8 является кубической степенью основания 2. Поэтому  достаточно каждый разряд восьмеричного числа представить тремя разрядами двоичного числа: 65₍₈₎=110101₍₂₎.

 

3. Перевести число А₍₁₀₎= 53 в А₍₁₆₎, а затем в А₍₂₎.

53	16
48	3	16
5	0	0
	3

Перевод шестнадцатеричного числа в двоичное проще выполнить, учитывая, что основание 16 является четвертой степенью основания 2. Поэтому достаточно каждый разряд восьмеричного числа представить четырьмя разрядами двоичного числа: 35₍₁₆₎=00110101₍₂₎.

 

4. Перевести число А₍₃₎= 22 в А₍₂₎.

22	2
22	11	2
0	11	2	2
	0	2	1	2
		0	0	0
			1

 

5. Перевести число А₍₄₎= 33 в А₍₈₎.

Основание 8 в системе  счисления с основанием 4 будет  представлено числом 20₍₄₎.

33	20
20	1	20
13(4)	0	0
	1

 

6. Перевести число А₍₂₎= 11010 в А₍₁₀₎.

Воспользуемся основной формулой позиционной системы чисел.

11010 ₍₂₎ = 1´2⁴ + 1´2³ + 0´2² +1´2¹ + 0´2⁰ = 1´16 + 1´8 + 0´4 + 1´2 + 0´1 = 26₍₁₀₎

 

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

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

Правило перевода дробных чисел из системы счисления  с основанием p в систему счисления с основанием  q:

1. Последовательно умножать данное число и получаемые дробные части произведений на основание новой системы, выраженное цифрами исходной системы, до тех пор, пока дробная часть  произведения не станет равной нулю.
2. Полученные целые части произведений, являющиеся цифрами числа в новой системе, выразить цифрами алфавита этой системы.
3. Составить дробную часть числа в новой системе, начиная с целой части первого произведения.

Пример. Перевести число А₍₁₀₎= 0,65625 в А₍₂₎ различными способами, используя перевод непосредственно в двоичную систему, а также через восьмеричную и шестнадцатеричную системы.

 

а) А₍₁₀₎ ® А₍₂₎                  б) А₍₁₀₎ ® А₍₈₎ ® А₍₂₎               в) А₍₁₀₎ ® А₍₁₆₎ ® А₍₂₎

 

 

 

 

 

 

 

 

 

 

 

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

Например, число А₍₁₀₎ = 0,3 в двоичной системе представляется бесконечной периодической дробью 0.01001100110011….= 0,0(1001)₍₂₎.

 

Перевод чисел из любой системы счисления p в десятеричную систему чисел. Перевод чисел в десятичную систему может выполняться либо по правилам перевода, либо по формулам степенного ряда, либо по формулам разложения по схеме Горнера. Рассмотрим последовательно применение этих алгоритмов на примерах.

1. Перевести число А₍₂₎= 10101101 в А₍₁₀₎.

• Выполним перевод по правилу перевода целого числа. Для этого представим новое основание системы 10 в двоичной системе: 10₍₁₀₎= 1010₍₂₎, и будем делить двоичное число на новое основание следующим образом:

 

	10101101			1010
	1010			10001			1010
	1101			1010			1	1010
	1010			111			0	0
	0011						1

 

 

 

 

По формуле степенного ряда перевод А₍₂₎= 10101101 в А₍₁₀₎ производится следующим образом:

10101101₍₂₎= 1´2⁷+ 0´2⁶ + 1´2⁵+0´2⁴ + 1´2³ + 1´2² +0´2¹ + 1´2⁰ =

= 1´128 + 0´64 + 1´32+ 0´16+ 1´8 +1´4+ 0´2+ 1´1 = 173₍₁₀₎

• Перевод А₍₂₎= 10101101 в А₍₁₀₎ по формуле Горнера:

((((((1×2+0)×2+1)×2+0)×2+1)×2+1)×2+0)×2+1=173₍₁₀₎

2. Перевести дробные числа А₍₂₎= 0,10101;  B₍₈₎= 0,52;  C₍₁₆₎ = 0,A8 в десятичную систему различными способами.

• Перевод по формуле степенного ряда:

       А₍₂₎= 0,10101=1´2 ^-1+ 0´2 ^-2 + 1´2 ^-3+0´2 ^-4 + 1´2 ^-5 = 0,5+0,125+0,03125 = =0,65625;

        В₍₈₎=0,52=5´8^-1+ 2´8^–2=0,625+0,03125= 0,65625;

        С₍₁₆₎=0,А8=10´16^–1 + 8´16^–2=0,625+0,03125= 0,65625;

• Перевод по схеме Горнера:

            A = ((((1×2^-1+0)×2^-1+1)×2^-1+0)×2^-1+1)×2^-1=0,65625₍₁₀₎;

            B = (5×8^-1+2)×8^-1=0,65625₍₁₀₎;

             C = (10×16^-1+8)×16^-1=0,65625₍₁₀₎;

• Выполним перевод по правилу перевода дробного числа. Для этого представим новое основание системы 10 в двоичной системе: 10₍₁₀₎=1010₍₂₎, в восьмеричной системе: 10₍₁₀₎=12₍₈₎, в шестнадцатеричной системе: 10₍₁₀₎=А₍₁₆₎. Умножение и сложение производится в соответствующей системе.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Арифметические операции в системе чисел

Посмотрим, как  проводятся расчеты в другой системе чисел. Пусть основанием системы чисел является цифра 6. Вначале рассмотрим операции с «однозначными» числами. (Однозначными в данном случае будут числа 0, 1, 2, 3, 4, 5.) Этим основным операция нужно учиться, как таблице умножения.

Сложение. Если одним членом некоторой суммы является 0, то сумма равна второму члену. Поэтому суммирование с нулем не рассматривается в силу очевидности.

Построим таблицу сложения однозначных чисел. В первом столбце  и первой строке записаны цифры, составляющие алфавит шестеричной системы, кроме 0; на пересечении i-ой строки и j-го столбца находится сумма a_i  и a_j , представленная в шестеричной системе.

Получается следующая  таблица:

+	1	2	3	4	5
1	2	3	4	5	10
2	3	4	5	10	11
3	4	5	10	11	12
4	5	10	11	12	13
5	10	11	12	13	14

 

Например, сумма 3 и 5 находится  на пересечении строки с цифрой 3 и столбца с цифрой 5: 3₍₆₎ + 5₍₆₎ =  12₍₆₎.

 

 

А теперь посмотрим, как  осуществляется суммирование многозначных чисел в той же системе счисления с основанием 6.

Определим сумму 315 + 543. Пусть эти числа записываются в виде:

315 = 3´100 + 1´10 + 5    и    543 = 5´100 + 4´10 + 3.

(Здесь числа 10 и  100 обозначают числа  в шестеричной  системе чисел.)

Учитывая коммутативность  и ассоциативность операции сложения, и используя дистрибутивное свойство, получим форму:

315 + 543 = (3 + 5) ´100 + (1 + 4) ´10 + (5 + 3).

Найдем значение последнего сложения из таблицы: 5 + 3 = 12 = 1´10 + 2. Откуда:

315 + 543 = (3 + 5) ´100 + (1 + 4 + 1) ´10 + 2.

Рассмотрим опять последний  член, содержащий операцию сложения. Эта сумма составляется на основе таблицы: (1 + 4) + 1 = 5 + 1 = 10, поэтому:

315 + 543 = (3 + 5 + 1) ´100 + 0´10 + 2.

Если еще раз посмотреть последний член, содержащий операцию сложения: 

3 + 5 + 1  =  3 + 10 = 13 = 1´10 + 3, то получится выражение:

315 + 543 = 1´1000 + 3´100 + 0´10 + 2 = 1203 .

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

  315

+543

1302

Процесс сложения идет таким  образом: 5 + 3 = 12 (из таблицы):  записывается 2, а 1 в старшем разряде суммируется  с предыдущим столбцом; 1+4+1=10: записывается 0, 1 суммируется со столбцом, стоящем  слева; 1+3+5=13: записывается 3, и, поскольку нет больше столбцов,  слева записывается 1.

Легко видеть, что и  сложение большего количества членов, и операция  вычитания осуществляются подобно тому, как это делается в десятичной системе чисел.

Умножение. В таблице умножения в системе счисления с основанием 6 представлены произведения однозначных чисел. Умножение на 0 и здесь не следует отдельно записывать, так как в случае, когда один из сомножителей 0, то и результат всего произведения будет 0. Аналогично не нужно приводить произведения, одним из сомножителей  которых является 1, так как в этих случаях результат произведения  всегда равняется другому сомножителю.

Таблица умножения в системе счисления с основанием 6 имеет следующий вид:

´	2	3	4	5
2	4	10	12	14
3	10	13	20	23
4	12	20	24	32
5	14	23	32	41