2015-06-26
1272
Использование нескольких систем счисления делает актуальной задачу получения по записи числа в одной системе счисления его запись в другой системе счисления – задачу перевода числа из одной системы счисления в другую (по xp получить xq). Метод решения задачи зависит от того, в какой системе счисления оперирует тот, кто должен будет осуществлять этот перевод – исполнитель. При этом исполнитель может работать в системе счисления с основанием r и a) r=p; b) r=q; c) r≠p и r≠q. В этом случае говорят, что исполнитель “знает” r-ичную арифметику. Случай (с) сводится к переводам (x)p=>(х)r=>(x)q.
5.1. Перевод числа в систему счисления исполнителя
Дано: xp=(αn…α3α2α1α0.α -1…α-m)p; p – основание системы счисления; C={c1, c2, c3, …, cp} – алфавит системы счисления; база системы счисления неотрицательная;
получить xq. Для исполнителя xp - строка символов. По этой строке он должен получить число в своей системе счисления. По исходным данным исполнитель может построить полином
βn*pn+ βn-1*pn-1+…+ β2*p2 +β1 *p1+ β0*p0+ β-1*p-1+…+ β-m*p-m.
|
|
|
Здесь βi– элемент базы, соответствующий цифре αi. Если в полиноме все числа записать в системе счисления исполнителя и исполнитель в своей арифметике выполнит действия по вычислению значения полинома, то в результате будет получено нужное число.
Например, C2E,4A16=> (?)10.
C2E,4A16=12*162+2*161+14*160+4*16-1+10*16-2=
(12*16+2)*16+14+((10/16+4)/16=2118 
=2118,2890625.
Запись полинома
βn*pn+ βn-1*pn-1+…+ β2*p2+ β1*p1+ β0*p0+ β-1*p-1+…+ β-m*p-m
в виде
((…((βn*p+ βn-1)*p +βn-2)*p+…+ β2)*p+ β1)*p+ β0+((…((β-m)/p +β-m+1)/p +…)/p+ β-1)/p
называют представлением полинома по схеме Горнера. Это представление позволяет оптимизировать процесс вычисления значения полинома за счет уменьшения количества операций умножения и деления.
Задачи
a) Выполнить переводы: 110110111,01112=>(?)10; FD08,0C16=>(?)10.
b) Разработать алгоритм перевода, описать его в виде блок-схемы.
c) Можно ли по этому же правилу производить перевод из десятичной системы счисления в двоичную или шестнадцатеричную систему счисления? Если да, то при каких условиях. Если нет, то почему. По 135910=>(?)16.
5.2. Перевод числа из системы счисления исполнителя
Дано: xp=число в системе счисления исполнителя; q – основание системы счисления, в которую выполняется перевод; C={c1, c2, c3, …, cq} – алфавит системы счисления; база системы счисления неотрицательная;
получить xq. =(αn…α3α2α1α0.α -1…α-m)q
Исполнитель по xp должен получить строку символов
αn…α3α2α1α0.α -1…α-m - q- ичную запись числа, которая соответствует полиному βn*qn+ βn-1*qn-1+…+ β2*q2+ β1*q1+ β0*q0+ β-1*q-1+…+ β-m*q-m. Полином определён, если известны его коэффициенты. Таким образом, задача сводится к поиску коэффициентов полинома с тем, чтобы затем при записи числа заменить их соответствующими цифрами системы счисления. Для получения правила перевода необходимо помнить о том, что исполнитель владеет средствами p-ичной арифметики.
|
|
|
5.2.1. Перевод целых чисел.
По xp получить (αn…α3α2α1α0)q, то есть найти коэффициенты полинома βn*qn+ βn-1*qn-1+…+ β2*q2+ β1*q1+β0*q0. Если xp обозначить через R0 и полином записать по другому: q*(βn*qn-1+ βn-1*qn-2+…+ β2*q1+ β1)*q+ β0, то видно, что выражение в скобках соответствует числу R1=(αn…α3α2α1)q, a R0 =q* R1+ β0. Здесь β0 - элемент базы, поэтому β0<q. Значит, β0 – остаток от деления R0 на q, а R1 - целая часть частного R0/q.
R1 =βn*qn-1+ βn-1*qn-2+…+ β2*q1+ β1 =(αn…α3α2α1)q. По числу R1 находим коэффициент β1 - остаток от деления R1 на q, соответствующий цифре α1, и число R2 - целую часть частного R1/q. Процесс продолжается до тех пор, пока очередная целая часть частного не окажется равной нулю. Записывая число в новой системе счисления, следует остатки заменять соответствующими цифрами.
Например, 379610=>(?)16.3796 | 16 R0=3796, β0=4, α0=4, R1=237;
4 237 | 16 R1=237, β1=13,α1=D, R2=14;,
13 14 | 16 R2=14, β2=14, α2=E; R3=0.
14 0
379610=4+16*(13+16*(14))=((14)*16+13)*16+4=(ED4)16.
Задачи
a) Перевести десятичные числа в двоичную систему счисления: 141, 128, 87, 685.
b) Перевести десятичные числа в шестнадцатеричную систему счисления: 549, 685, 3007, 9875.
5.2.2. Перевод правильных дробей.
По 0<xp <1 получить (0. α-1…α-m)q, то есть найти коэффициенты β-1 , …, β-m полинома β-1*q-1+…+ β-m*q-m.
Если xp обозначить через Z1, a полином умножить на q, то
Z1*q =β-1*q0+(β-2*q-1+…+ β-m*q-m+1), чему соответствует число (α -1.α -2…α-m)q. Z1*q = β-1+Z2. Отсюда β-1 – целая часть произведения Z1*q, Z2 - дробная часть Z1*q.
По Z2 =(β -2*q-1+…+ β-m*q-m+1)=(0. α –2…α-m)q аналогично отыскиваются β –2 и Z3.
Процесс продолжают до тех пор, пока очередное Z-m-1 окажется равным нулю или будет получено нужное количество β –i (1≤ i≤ m. Выбирают m таким образом, чтобы p-k≈q-m. Здесь k – количество цифр в дробной части xp).
Примеры.
0.062510=>(?)16.
0 | 0625 *16 Z1 =0.0625
1 | 0 β-1=1, Z2 =0; 0.062510=>(0.1)16.
0.3010=>(?)16
0 | 30 *16 Z1 =0.30;
4 | 80 β-1=4, Z2 =0.80;
12 | 80 β-2=12, Z3 =0.80; 0.3010=(0.2ССССС…)16; 0.3010≈ (0.2D)16
Задачи
a) 0.150010=>(?)2; 0.3710=>(?)2; (
)10=>(?)2.
b) 0.150010=>(?)16; 0.3710=>(?)16; ()10=>(?)16.
c) 3705.13010=>(?)16; 28079.810010=>(?)16.
d) FEC.4A16=>(?)2; FEC.4A16=>(?)7;
