Арифметика великих чиселВідомо, що операції з числовими значеннями в комп’ютері відбувається з обмеженою кількістю розрядів. Але трапляються випадки, коли приходиться обчислювати числа де кількість знаків становить 20, 100, 1000. Такі числа використовуються в астрономії, мікрофізиці, комбінаториці. Для реалізації операцій з довгими числами необхідно розмістити довге число в пам’яті комп’ютера. Розмістимо довге число в цілочисельний масив. В кожну комірку пам’яті помістимо по декілька цифр (для початку 1 цифру) В нульовій комірці пам’яті будемо зберігати кількість цифр довгого числа. Розвернемо масив для зручності уявлення розміщення цифр. Запишемо число: 475739541
Масив M:
Для реалізації довгої арифметики створимо такі функції: - занесення довгого числа в масив; - виведення довгого числа; - додавання двох довгих чисел; - порівняння довгих чисел; - множення довгого числа на коротке; - множення двох довгих чисел; - ділення довгого числа на коротке; - ділення довгого на довге число.
Довге число зручно вводити у вигляді рядка, при цьому у нульовій комірці розміщується цифра самого високого розряду, а останньою розміщена цифра першого розряду. Розвернемо (реверсуємо) рядок і запишемо кожну цифру в окрему комірку цілочисельного масиву. Для цього напишемо функцію:
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; } |
