Переводы между системами счисления
В этой главе рассмотрим переводы между разными системами счисления. Помимо привычной десятичной существуют и другие- например, пятеричная. Там всего 5 цифр: 0, 1, 2, 3, 4. А далее 10, 11 и т.д.
Задача в том, чтобы вот я ввожу например обычное десятичное число и надо перевести его в двоичное. Вход: 9, выход: 1001.
В идеале написать не просто перевод в именно двоичную систему, но вообще в любую до десяти. Давайте сначала напишем перевод именно в двоичную.
Как вообще происходит перевод? Мы будем использовать число как массив цифр- это расширяет спектр возможностей и упрощает алгоритмы. Функции для ввода, вывода и т.п. мы уже написали. Хотя смысла особо нет, т.к. нам всё равно нужно абсолютное значение- нам нужно брать логарифм.
Сначала нужно понять, сколько цифр будет в двоичном числе:
0-1 -> 1
2-3 -> 2
4-7 -> 3
В итоге мы берём двоичный логарифм, убираем дробную часть и прибавляем 1.
Хранить двоичное число как массив цифр будем хранить как приняли- в первом элементе кол-во цифр, а далее сами цифры. На вход в качестве десятичного будем подавать обычный int.
int log2 (int x) { return int(log(x)/log(2));} // целая часть двоичного логарифма
int *DecToBin (int x) {
int size= log2(x) + 1; // кол-во цифр двоичного числа
int *res= new int [size+1]; // само двоичное число- массив для его хранения
res[0]= size; // в 1-м элементе храним размер
// далее реализовано то что на картинке выше
for(int i= log2(x); i>=0; i--) {
|
|
|
if(x - pow(2,i) <0) {
res[size-i]= 0;
continue;
}
else {
res[size-i]= 1;
x-= pow(2,i);
}
}
return res;
}
Тестировать можно так:
int x; cin>>x;
Kosh_Print(DecToBin(x));
Есть один недостаток- с нулём не работает, т.к. логарифм из него не берётся. Поэтому пропишем это условие отдельно, дополним функцию:
...
Теперь попробуем переводить в другую систему счисления- сделать более универсально. Посмотрим на примере троичной как это происходит:
Теперь можно написать алгоритм- не только для троичной, но и для любой системы счисления с кол-вом цифр от 2 до 9.
int Log (int x, int n) { return int(log(x)/log(n)); }
// osn= {2,3,4,5,6,7,8,9}
int *Dec_To_Min (int x, int osn= 3) {
if(!x) {
int *res= new int [2];
res[0]= 1; res[1]= 0;
return res;
}
else {
int size= Log(x,osn) + 1;
int *res= new int [size+1];
res[0]= size;
|
|
|
for(int i= Log(x,osn); i>=0; i--) {
res[size-i]= x/pow(osn,i);
x%= (int)pow(osn,i);
}
return res;
}
}
Теперь решим обратную задачу: перевод из системы с основанием 2-9 в десятичную обратно. Тут всё даже проще: чисто делается сумма будто вычисляется значение полинома.
Теперь сама функция перевода:
int Min_To_Dec (int x[], int osn= 3) {
int size= x[0];
int res= 0;
for(int i= size-1; i>=0; i--) res+= x[size-i]*pow(osn,i);
return res;
}
Можно хранить число в более расширенном виде: в 1-м элементе хранить например количество цифр, а во 2-м элементе уже основание системы счисления. Это расширит возможности- т.е. функции сами автоматически будут определять, в какой системе счисления число- но при этом алгоритмы станут сложнее.
Сначала лучше запишем функцию, которая переводит например из троичной системы в пятеричную. Это уже легко будет сделать, т.к. мы будем использовать десятичную систему как буферную, промежуточную. Т.е. мы троичное число переводим сначала в десятичное, а потом это десятичное уже в пятеричное.
|
|
|
int *Perevod_System_Min (int x[], int osn_from, int osn_to) {
return Dec_To_Min(Min_To_Dec(x,osn_from),osn_to);
}
...
Мы рассмотрели только системы счисления, которые меньше 10- т.е. они содержат привычные нам цифры. Поэтому в названиях функций выше и была приписка Min. Но есть системы с количеством чисел больше 10, например 16-ричная. Тут проблема в том, что в качестве цифр дальше уже используются буквы: A, B, C, D, E, F для 16-ричной например. Поэтому число с основанием системы счисления больше 10 уже придётся хранить в массиве символов, при этом написать переводные функции из этих символов в цифры.
Хотя есть и другой выход- в памяти компьютера эти цифры будут храниться как обычные числа типа 10, 11, 12 и т.д. Тогда можно переводные функции даже не менять. А при выводе на консоль мы будем переводить эти цифры в буквы. Ну и при вводе буквы в цифры соответственно. Т.е. изменить придётся только функции ввода и вывода.
В таблице ASCII заглавные английские буквы идут подряд- это можно использовать. Так как цифры 10, 11 и т.д. тоже идут соответственно им подряд.
Эта команда выведет таблицу:
for(int i=0; i<=255; i++) cout << i << " --> " << (char)i << endl;
65 --> A
66 --> B
67 --> C
68 --> D
69 --> E
70 --> F
48 --> 0
49 --> 1
50 --> 2
Этого отрывка нам будет достаточно для понимания как запрограммировать перевод символьной цифры в числовую.
|
|
|
char IntDigit_To_Char (int x) {
if( (x>=0)&&(x<=9) ) return (char)(48+x);
if(x>=10) return (char)(55+x);
}
void Kosh_Print_Max (int a[]) {
int r= a[0];
for (int i=1; i<=r; i++) cout << IntDigit_To_Char(a[i]);
}
Тестирование:
int x; cin>>x; int *t= Dec_To_Min(x,16);
Kosh_Print_Max(t);
Выводим 16-ричное число.
...
Теперь алгоритм ввода.
int *Kosh_Input_Max() {
string s; cin>>s;
int size= StringSize(s);
int *number= new int [size+1];
number[0]= size;
for(int i=1; i<=size; i++) number[i]= CharToInt(s[i-1]);
return number;
}
По сути он абсолютно такой же, вообще ничего не поменялось. Функция перевода из символа в цифру была модифицирована и всё:
int CharToInt (char c) {
if (((int)c>=48)&&((int)c<=57)) return (int)c - 48;
if ((int)c>=65) return (int)c - 55;
}
Пример тестирования на 14-ричной системе счисления:
int *t= Kosh_Input_Max();
int x= Min_To_Dec(t,14);
cout << x << endl;
Kosh_Print_Max(t);
...
Что касается задачи перевода из 16-ричную в троичную например- эта задача уже решена, применимы всё те же функции. Просто единственное для таких систем типа 16-ричных мы модифицировали функции ввода и вывода. Можно теперь все эти функции переименовать и получим чёткую систему, на которой тут и закончим:
int CharToInt (char c) {
if (((int)c>=48)&&((int)c<=57)) return (int)c - 48;
if ((int)c>=65) return (int)c - 55;
}
char IntDigit_To_Char (int x) {
if( (x>=0)&&(x<=9) ) return (char)(48+x);
if(x>=10) return (char)(55+x);
}
int StringSize (string s) {
char c= s[0]; int i=0; int stringsize=0;
while ((int)c != 0) { i++; c=s[i]; stringsize++; }
return stringsize;
}
void Kosh_Print (int a[]) {
int r= a[0];
for (int i=1; i<=r; i++) cout << IntDigit_To_Char(a[i]);
}
int *Kosh_Input() {
string s; cin>>s;
int size= StringSize(s);
int *number= new int [size+1];
number[0]= size;
for(int i=1; i<=size; i++) number[i]= CharToInt(s[i-1]);
return number;
}
////////////////////////////////////
int Log (int x, int n) { return int(log(x)/log(n)); }
int *Dec_To_Another (int x, int osn= 3) {
if(!x) {
int *res= new int [2];
res[0]= 1;
res[1]= 0;
return res;
}
else {
int size= Log(x,osn) + 1;
int *res= new int [size+1];
res[0]= size;
for(int i= Log(x,osn); i>=0; i--) {
res[size-i]= x/pow(osn,i);
x%= (int)pow(osn,i);
}
return res;
}
}
int Another_To_Dec (int x[], int osn= 3) {
int size= x[0];
int res= 0;
for(int i= size-1; i>=0; i--) res+= x[size-i]*pow(osn,i);
return res;
}
int *Perevod_System (int x[], int osn_from, int osn_to) {
return Dec_To_Another(Another_To_Dec(x,osn_from),osn_to);
}
Дата добавления: 2018-09-22; просмотров: 234; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!