Відомо, що операції з числовими значеннями в комп’ютері відбувається з обмеженою кількістю розрядів. Але трапляються випадки, коли приходиться обчислювати числа де кількість знаків становить 20, 100, 1000. Такі числа використовуються в астрономії, мікрофізиці, комбінаториці.
Для реалізації операцій з довгими числами необхідно розмістити довге число в пам’яті комп’ютера. Розмістимо довге число в цілочисельний масив. В кожну комірку пам’яті помістимо по декілька цифр (для початку 1 цифру) В нульовій комірці пам’яті будемо зберігати кількість цифр довгого числа. Розвернемо масив для зручності уявлення розміщення цифр.
Запишемо число: 475739541
Масив M:
|
Номер елементів масиву
|
9
|
8
|
7
|
6
|
5
|
4
|
3
|
2
|
1
|
0
|
|
Елементи масиву
|
4
|
7
|
5
|
7
|
3
|
9
|
5
|
4
|
1
|
9
|
Для реалізації довгої арифметики створимо такі функції:
- занесення довгого числа в масив;
- виведення довгого числа;
- додавання двох довгих чисел;
- порівняння довгих чисел;
- множення довгого числа на коротке;
- множення двох довгих чисел;
- ділення довгого числа на коротке;
- ділення довгого на довге число.
Довге число зручно вводити у вигляді рядка, при цьому у нульовій комірці розміщується цифра самого високого розряду, а останньою розміщена цифра першого розряду. Розвернемо (реверсуємо) рядок і запишемо кожну цифру в окрему комірку цілочисельного масиву. Для цього напишемо функцію:
void strtomasiv(char *str,int *T)// Переведення з рядка в масив int
{int i;
T[0]=strlen(str); //Знаходження кількості знаків у числі
strrev(str); // розвертає (реверсує) символьний масив
for(i=1;i
for(i=1;i<=T[0];i++)
T[i]=str[i-1]-'0';// переведення з символів у цифри
// і занесення їх у числовий масив
}
Функція отримує довге число у вигляді символьного масиву *str, і повертає також через параметри масив *T типу int.
Для прискорення операцій з довгими цифрами у кожну комірку заносять не одну цифру, а декілька. Число типу int (long) у мові С++ може пам’ятати 10 знаків. Враховуючи діапазон данного типу (перша цифра максимального числа не перевищує 2) ми можемо записати у кожну комірку пам’яті массиву по 9 цифр при додаванні та 4 цифри при множенні. множенні.
void strtomasiv(char *str,int *T)// Переведення з рядка в масив int
{int i,j,n,p,k; // із занесенням по K знаків у кожну комірку
char temp[10];
n=strlen(str);
n-=K;
for (i=1;i
for(i=1;n>0;n-=K,i++)
{strncpy(temp,str+n,K);//копіювання К символів з довгого числа
p=0;
for(j=0;j
p=p*10+temp[j]-'0'; //складання числа
T[i]=p;
}
strncpy(temp,str,n+K); //формування самого числа самих старших розрядів
p=0;
for(j=0;j
p=p*10+temp[j]-'0';
T[i]=p;
T[0]=i;
}
Для виведення довгих чисел також рекомендується написати окрему функцію.
Під час виведення масиву довгого числа, де в кожній комірці знаходиться лише по одній цифрі не виникає ніяких проблем, необхідно вивести масив у зворотному порядку.
void out(int *T)// Виведення масиву
{
int i;
for(i=T[0];i>0;i--)
{
cout<
}
}
Якщо виводите масив, де в кожній комірці знаходиться по декілька цифр можливі проблеми з виведенням ведучиз нулів. Якщо нам потрібно вивести число 12030002, і в кожній комірці знаходтться по 4 цифри, то ми отримуємо масив з двох комірок, в T[1]=2, а в T[2]=1203. Під час виведення, наведеному вище ми отримаємо 12032. Ми втрачаємо три розряди значення яких дорівнюють 0. В такому випадку необхідно застосувати застосувати форматоваий вивід. Для цього застосуємо два флаги форматованого виведення:
void out(int *T)// Виведення масиву
{
int i;
for(i=T[0];i>0;i--)
{
cout<
cout.width (K); //задається ширина поля виведення К знаків з
// вирівнюванням по правому краю
cout.fill ('0');//заповнення пустих позицый символом '0'.
}
}
Додавання цілих довгих чисел. Процес додавання довгих чисел – це реалізація додавання чисел в стовпчик. Перше число –масив T1, друге число – масив T2 – результат – T3.
Наприклад:
T1 67897
T2 328
-----
T3 68225
void add(int *T1,int *T2,int *T3) //додавання довгих чисел T3=T1+T2;
{
int n=(T1[0]>T2[0])?T1[0]:T2[0];//знаходиться кількість цифр більшого числа
int p=0,i;
for(i=1;i<=n;i++)
{
int temp=T1[i]+T2[i]+p;
T3[i]=temp%R; // виділення результуючої групи цифр
p=temp/R; // виділення цифри, що виходить за
// розрядність групи
}
if(p>0) {n++; T3[n]=p; }
T3[0]=n;
}
Порівняння довгих чисел.
Функція порівняння довгих чисел повертає «0» – коли числа рівні, «1»- коли перше число більше за друге і «-1» коли друге число більше першого. Під час реалізації спочатку порівнюється кількість цифр. Якщо кількість цифр різна, то у більшого числа більше кількість цифр. Якщо ж кількість цифр однакова, то порівнюють всі цифри по порядку, починаючи з старшого розряду. Даний алгоритм буде працювати правильно і у випадку коли в одній комірці пам’яті масиву будемо зберігати декілька цифр.
int compare(int *T1,int *T2)//Порівняння довгих чисел 0-рівні,
// 1 - T1 > T1, -1 - T1
{int i;
if(T1[0]>T2[0]) return 1; //якщо в І числа кількість цифр > ніж в ІІ
else
if(T1[0]< ніж в ІІ
else
{for(i=1;i
if(T1[0]>T2[0]) return 1;
else
if(T1[0]
return 0;
}
}
Множення довгого числа на коротке.
void mult(int *T1,int k)// Множення довгого числа на коротке T1=T1*k
{
int i,p=0;
for(i=1;i
{
int temp=T1[i]*k+p;
T1[i]=temp%R;
p=temp/R;
}
while(p>0)
{
T1[0]++;
T1[T1[0]]=p%R;
p/=R;
}
}
Множення двох довгих чисел
void multDD(int *T1,int *T2,int *T3)// Множення довгого числа на довге T3=T1*T2
{
int i,j,p=0;
for(i=1;i<=T2[0];i++)
{
for(j=1;j<=T1[0];j++)
{
int temp=T2[i]*T1[j]+p+T3[j+i-1];
T3[i+j-1]=temp%R;
p=temp/R;
}
T3[i+j-1]=p;p=0;
}
int n=T2[0]+T1[0]-1;
while(p>0)
{
T3[n]=p%R;
p/=R;
n++;
}
if(T3[n+1]>0) T3[0]=n+1; else T3[0]=n;
}
