Арифметика в других системах счисления
Пойдём дальше. Зададимся вопросом- как можно складывать, умножать и т.п. числа например в пятеричной системе. Тут есть два пути.
Первый путь очевиден: перевести число в десятичную систему, спокойно его там сложить, а потом перевести обратно в прежнюю систему.
Метод прост, хорош- но проблема в том что работает он только с узким диапазоном чисел- до 2 млрд. Потому что там считаются логарифмы и десятичное число это не массив, а просто int. А тип int вмещает максимум 2^31 - 1 = 2147483647, это 4 байт памяти компьютера. Вторая половина уходит под отрицательные числа.
Второй же путь- не переводить в десятичную систему, а производить поразрядное сложение- тут мы уже неограничены. Но проблема что такой алгоритм более трудный.
Тем не менее он уже не так труден, потому что мы написали аналогичные алгоритмы для десятичной системы ранее, поэтому останется лишь обобщить.
...
На самом деле эти функции сложения, вычитания и умножения очень мало меняются: просто изменить один параметр- там где использовалось 10, сделать основание. А сами функции будут перегружены и обобщены.
int *Kosh_Sum (int a[], int b[], int osn= 10) {
int n;
a[0]>b[0] ? n=a[0] : n=b[0];
int *A= new int [n+1];
int *B= new int [n+1];
A[0]= n; B[0]= n;
int d;
if(a[0]>b[0]) {
d= a[0]-b[0];
for(int i=1; i<=d; i++) B[i]= 0;
for(int i=d+1; i<=n; i++) B[i]= b[i-d];
|
|
|
for(int i=1; i<=n; i++) A[i]= a[i];
}
if(a[0]<b[0]) {
d= b[0]-a[0];
for(int i=1; i<=d; i++) A[i]= 0;
for(int i=d+1; i<=n; i++) A[i]= a[i-d];
for(int i=1; i<=n; i++) B[i]= b[i];
}
if(a[0]==b[0]) {
for(int i=1; i<=n; i++) A[i]= a[i];
for(int i=1; i<=n; i++) B[i]= b[i];
}
int size= n;
int *_A= Kosh_Copy(A);
_A[0]= 0;
for(int i=n; i>=1; i--) if(_A[i] + B[i]>=osn) _A[i-1]++;
if(_A[0]) size= n+1;
int *C= new int [size+1];
C[0]= size;
bool inc= false;
if(size==n) {
for(int i=n; i>=1; i--) {
C[i]= A[i] + B[i];
if(inc) {
C[i]++;
inc= false;
}
if(C[i]>=osn) {
C[i]-=osn;
inc= true;
|
|
|
}
}
}
if(size==(n+1)) {
C[1]= 1;
for(int i=n; i>=1; i--) {
C[i+1]= A[i] + B[i];
if(inc) {
C[i+1]++;
inc= false;
}
if(C[i+1]>=osn) {
C[i+1]-=osn;
inc= true;
}
}
}
return C;
}
int *Kosh_Subst (int a[], int b[], int osn= 10) {
int max= a[0], min= b[0], d= max-min;
int *B= new int [max+1];
B[0]= max;
for(int i=1; i<=d; i++) B[i]= 0;
for(int i=(d+1); i<=max; i++) B[i]= b[i-d];
int *A= Kosh_Copy(a);
//
int *C= new int [max+1];
C[0]= max;
bool razr= false;
for(int i=max; i>=1; i--) {
|
|
|
if(razr) {
A[i]--;
razr= false;
}
C[i]= A[i]-B[i];
if(C[i]<0) {
C[i]+= osn;
razr= true;
}
}
int nulls= 0;
for(int i=1; i<max; i++) {
if(!C[i]) nulls++;
else break;
}
int n= max-nulls;
int *c= new int [n+1];
c[0]= n;
for(int i=1; i<=n; i++) c[i]= C[i+nulls];
return c;
}
int *Kosh_Prod (int a[], int b[], int osn= 10) {
int adeg= a[0]-1, bdeg= b[0]-1;
int *A= new int [a[0]];
int *B= new int [b[0]];
for(int i=0; i<=adeg; i++) A[i]= a[i+1];
for(int i=0; i<=bdeg; i++) B[i]= b[i+1];
int *C= PolynomProd(A,adeg,B,bdeg);
int n= adeg+bdeg+1;
int *c= new int [n+1];
c[0]= n;
for(int i=1; i<=n; i++) c[i]= C[i-1];
int fazla= 0;
for(int i=n; i>=1; i--) {
c[i]+= fazla;
if(c[i]>=osn) {
fazla= c[i]/osn;
|
|
|
c[i]= c[i]%osn;
}
}
if(fazla) {
int *c1= new int[n+2];
c1[0]= n+1;
c1[1]= fazla;
for (int i=2; i<(n+2); i++) c1[i]= c[i-1];
return c1;
}
return c;
}
Римские числа
Здесь мы научимся программировать римские числа. Это сделать достаточно просто, т.к. римские числа ограничены 3999- это самое большое возможное римское число. Поэтому мы вводим римское число как строку, переводим в число int обычное и работаем с ним. Потом результат обратно выводим как римское число. Т.е. по сути вся арифметика будет скрытая в виде int. Нужно записать лишь ввод и вывод- это основная задача и довольно непростая.
Сначала напишем простую систему:
I - 1
V - 5
X - 10
L - 50
C - 100
D - 500
М - 1000
Пример: 281 = ССLXXXI
Проще всего сначала сделать именно вывод римского числа. Будем разбирать через остатки.
void RomePrint (int x) {
if(x/1000) {
for(int i=1; i<=(x/1000); i++) cout << "M";
x%=1000;
}
if(x/500) {
cout << "D";
x%=500;
}
if(x/100) {
for(int i=1; i<=(x/100); i++) cout << "C";
x%=100;
}
if(x/50) {
cout << "L";
x%=50;
}
if(x/10) {
for(int i=1; i<=(x/10); i++) cout << "X";
x%=10;
}
if(x/5) {
cout << "V";
x%=5;
}
for(int i=1; i<=x; i++) cout << "I";
}
Это упрощённая запись римских чисел. Проблема в том, что реальные римские цифры имеют ещё один нюанс: например 4 записывается как IV, 9 как IX, 40 как XL и т.д. Это нужно тоже проверять. Вот расширенная функция:
void RomePrint (int x) {
if(x/1000) {
for(int i=1; i<=(x/1000); i++) cout << "M";
x%=1000;
}
if(x/100==9) {
cout << "CM";
x%= 100;
}
else {
if(x/500) {
cout << "D";
x%=500;
}
if(x/100) {
if(x/100==4) cout << "CD";
else for(int i=1; i<=(x/100); i++) cout << "C";
x%=100;
}
}
if(x/10==9) {
cout << "XC";
x%= 10;
}
else {
if(x/50) {
cout << "L";
x%=50;
}
if(x/10) {
if(x/10==4) cout << "XL";
else for(int i=1; i<=(x/10); i++) cout << "X";
x%=10;
}
}
if(x==9) cout << "IX";
else {
if(x/5) {
cout << "V";
x%=5;
}
if(x) {
if(x==4) cout << "IV";
else for(int i=1; i<=x; i++) cout << "I";
}
}
}
С функцией ввода сложнее. Потому что нужно как-то обрабатывать эти числа для 4, 9 и т.д. Но если потрудиться, и это как-то возможно реализовать. Будем делать перебором с тысячи и до единицы.
int RomeInput() {
string s; cin>>s;
int i= 0;
int res= 0;
if(s[i]=='M') {
res+= 1000;
i++;
if(s[i]=='M') {
res+= 1000;
i++;
if(s[i]=='M') {
res+= 1000;
i++;
}
}
}
if(s[i]=='D') {
res+= 500;
i++;
}
if(s[i]=='C') {
if(s[i+1]=='M') {
res+= 900;
i+=2;
}
else if(s[i+1]=='D') {
res+= 400;
i+=2;
}
else {
res+= 100;
i++;
}
if(s[i]=='C') {
res+= 100;
i++;
if(s[i]=='C') {
res+= 100;
i++;
}
}
}
if(s[i]=='L') {
res+= 50;
i++;
}
if(s[i]=='X') {
if(s[i+1]=='C') {
res+= 90;
i+=2;
}
else if(s[i+1]=='L') {
res+= 40;
i+=2;
}
else {
res+= 10;
i++;
}
if(s[i]=='X') {
res+= 10;
i++;
if(s[i]=='X') {
res+= 10;
i++;
}
}
}
if(s[i]=='V') {
res+= 5;
i++;
}
if(s[i]=='I') {
if(s[i+1]=='X') {
res+= 9;
i+=2;
}
else if(s[i+1]=='V') {
res+= 4;
i+=2;
}
else {
res+= 1;
i++;
}
if(s[i]=='I') {
res+= 1;
i++;
if(s[i]=='I') {
res+= 1;
i++;
}
}
}
return res;
}
Дата добавления: 2018-09-22; просмотров: 194; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!