Автор: Пользователь скрыл имя, 24 Декабря 2010 в 10:28, курсовая работа
Цель моей курсовой работы заключается в реализации структур и алгоритмов для работы с «длинными» числами для последующего использования их в вычислениях. Скорость работы алгоритмов сильно зависит от выбора основания системы счисления (BASE).
Введение 3
1. Структуры, алгоритмы классических «длинных» чисел 5
1.1 Структура класса «BigInt» 6
1.2 Операции над большими числами 7
2. Структуры и алгоритмы факториальной длинной арифметики 10
2.1 Структура факториальной длинной арифметики 10
2.2 Функции и операции над числами факториальной арифметики 11
3. Сравнение систем счисления 15
3.1 Набор необходимых для сравнения инструментов 15
3.2 Сравнение систем счисления 16
Заключение 20
Список использованной литературы 21
Приложение: Class BigInt, функции для работы с классом 22
if (!carry) C.Size = Size;
while (carry) {
temp = carry % (i+2); //BASE
carry = carry / (i+2);
c[i] = temp; //BASE
i++;
}
C.update();
return C;
}
void BigInt::FacToDec(){
BigInt res;
int i=0;
for(int i = Size-1; i >= 0; i--){
Mul_Int_Dec(res, (i + 2), res);
Add_Int_Dec(res,
}
*this = res;
}
BigInt FacToDec(BigInt A){
BigInt res;
int i=0;
for(int i = A.Size-1; i >= 0; i--){
Mul_Int_Dec(res, (i + 2), res);
Add_Int_Dec(res,A.
}
return res;
}
void Div_fac(const BigInt &A, const int B, BigInt &Q, int &R) {
int r=0, *q=Q.Coef;
const int *a=A.Coef;
long i, temp;
for ( i=A.Size-1; i>=0; i--) {
temp = r*(i+2) + a[i];
q[i] = temp / B;
r = temp - q[i]*B; //r – промежуточный остаток на предыдущей итерации
}
R = r;
i = A.Size-1;
while ( (i>0) && (q[i]==0) ) i--; //подсчитываем длину частного
Q.Size = i+1;
}
int operator%(const BigInt &A, const int B){
BigInt Q;
int r=0, *q=Q.Coef;
const int *a=A.Coef;
long i, temp;
for ( i=A.Size-1; i>=0; i--) {
temp = r*(i+2) + a[i];
q[i] = temp / B;
r = temp - q[i]*B; //r – промежуточный остаток на предыдущей итерации
}
return r;
}
BigInt Div_int(const BigInt &A, const int B) {
BigInt Q;
int r=0, *q=Q.Coef;
const int *a=A.Coef;
int i, temp;
for ( i=A.Size-1; i>=0; i--) {
temp = r*BASE + a[i];
q[i] = temp / B;
r = temp - q[i]*B;
}
i = A.Size-1;
while ( (i>0) && (q[i]==0) ) i--;
Q.update();
return Q;
}
int Div_int_rm(const BigInt &A, const int B) {
BigInt Q;
int r=0, *q=Q.Coef;
const int *a=A.Coef;
int i, temp;
for ( i=A.Size-1; i>=0; i--) {
temp = r*BASE + a[i];
q[i] = temp / B;
r = temp - q[i]*B;
}
return r;
}
BigInt Div_Int_Fac(BigInt &A, const int B) {
BigInt C;
const int *a=A.Coef;
int res = a[A.Size-1];
for(int i=A.Size-1;i>=0;i--){
C.Coef[i] = res / B;
if (i) res = (res % B) * (i+1) + a[i-1];
}
C.update();
return C;
}
int Div_Int_Fac_rm(BigInt &A, const int B) {
const int *a=A.Coef;
int temp, rm, res = a[A.Size-1];
for(int i=A.Size-1;i>=0;i--){
temp = res / B;
if (i) res = (res % B) * (i+1) + a[i-1];
else rm = res % B;
}
return rm;
}
void Div_fac(BigInt& A, BigInt& B, BigInt& Q, BigInt& R){
BigInt fact, temp;
R = A;
int i;
for(i = A.Size - 1;i >= 0;i--)
{
int
from = 0, till = i + 1;
fact.Size = i + 1;
while (from < till)
{
int x = (from + till + 1) / 2;
fact.Coef[i] = x;
temp = B * fact;
if ( temp <= R)
from = x;
else till = x - 1;
}
fact.Coef[i] = from;
temp = B * fact;
R = R - temp;
Q.Coef[i] = from;
fact.Coef[i] = 0;
}
}
BigInt BigInt::operator /(BigInt& B){
BigInt Q,R;
if( Size < B.Size ){
return 0; //Вернем нуль, т.е. делимое меньше делителя
}
else Div_fac(*this,B,Q,R);
Q.update();
return Q;
}
BigInt BigInt::operator %(BigInt& B){
BigInt Q,R;
if(Size < B.Size) return B;
else Div_fac(*this,B,Q,R);
return R;
}
BigInt BigInt::operator ++ (int){
int i=0, temp = 1;
while(temp){
temp = temp + this -> Coef[i] ++;
this -> Coef[i] = temp % (i + 2);
temp = temp / (i + 2);
i++;
}
if(temp) {
Coef[i] = temp % (i + 2);
temp = temp / (i + 2);
}
if(Coef[Size]) Size++;
return *this;
}
Содержимое файла программы main.cpp:
#include "cursovaya.h"
#include "conio.h"
#include "iostream"
#include "fstream"
#include "time.h"
#include "stdio.h"
void analyze(){
ofstream out("analyze.txt");
BigInt A;
A.Coef[0]=1;
BigInt B;
for(long i = 1; i<101;i++){
A = A * (int)i;
out<<i<<"\t"<<A.
B=FacToDec(A);
out<<"\t"<<B.Size<
cout << i << endl;//}
}
out.close();
}
int main(){
BigInt A,B;
int n,m,s;
cout<<"Enter n,m:"; cin>>n>>m;
A.random(n); B.random(m);