Четверг, 07 Апреля 2011 г. 19:53
+ в цитатник
Тема: Больная реализация длинной арифметики на с++
#include
#include
#include
#include
#include
using namespace std;
struct long_num{
char *body;
int length;
bool isPositive;
};
void input_long_num(long_num* long_num_a)
{
char buf[1000];
char *str = buf;
scanf("%s",str);
char maybeSign = str[0];
long_num_a->isPositive = (maybeSign != '-');
if (maybeSign == '+' || maybeSign == '-')
{
str++;
}
long_num_a->length=strlen(str);
long_num_a->body=new char[long_num_a->length];
for (int i = long_num_a->length - 1, j = 0; i >= 0 ; i--, j++)
{
long_num_a -> body[j] = (int)str[i] - 48;
}
}
void output_long_num(long_num* long_num_a){
if (long_num_a->isPositive==false) printf("%c",'-');
for(short i=long_num_a->length-1; i>=0 ; i--)
printf("%d",(int)long_num_a->body[i]);
}
bool operator ==(long_num num_a,long_num num_b)
{
if (num_a.isPositive!=num_b.isPositive) return false;
int t=num_a.length-num_b.length;
if (t) return false;
for(int i=0; (i(long_num num_a, long_num num_b)
{
if (num_a.isPositive && !num_b.isPositive) return true;
if (!num_a.isPositive && num_b.isPositive) return false;
char sign=1;
if (!num_a.isPositive && !num_b.isPositive) sign=-1;
int t=num_a.length-num_b.length;
if (!t)
{
for(int i=num_a.length-1; i>=0 && !t; i--)
t=num_a.body[i]-num_b.body[i];
}
t*=sign;
if (t>0) return true;
return false;
}
bool operator <(long_num num_a,long_num num_b)
{
return !( num_a>num_b || num_a==num_b);
}
bool operator <=(long_num num_a,long_num num_b)
{
return !(num_a > num_b);
}
bool operator >=(long_num num_a,long_num num_b)
{
return !(num_a < num_b);
}
long_num abs(long_num num_a)
{
num_a.isPositive=1;
return num_a;
}
void sum(long_num* num_a, long_num* num_b, long_num* num_c){
char sum_sign=num_a->isPositive+num_b->isPositive;
if ((sum_sign)%2){
return ;
}
if (sum_sign) num_c->isPositive=1;
else num_c->isPositive=0;
char i=0;
char* num_arr;
num_arr=new char[max(num_a->length,num_b->length)];
int mod=0;
num_c->length=0;
for(int index_num_a=0,index_num_b=0; index_num_a < num_a->length || index_num_b < num_b->length || mod ;)
{
if ( index_num_a < num_a->length )
{
mod += num_a -> body[index_num_a++];
}
if ( index_num_b < num_b->length )
{
mod += num_b -> body[index_num_b++];
}
num_arr[num_c->length++]=mod%10;
mod/=10;
}
num_c->body=new char[num_c->length];
for(int i=0;ilength;i++)
num_c->body[i]=num_arr[i];
}
long_num operator -(long_num num1, long_num num2);
long_num operator +(long_num num_a, long_num num_b)
{
if (num_a.isPositive!=num_b.isPositive) return num_a-num_b;
long_num num_c;
num_c.isPositive=num_a.isPositive;
char i=0;
char* num_arr;
num_arr=new char[max(num_a.length,num_b.length)+1];
int mod=0;
num_c.length=0;
for(int index_num_a=0,index_num_b=0; index_num_a < num_a.length || index_num_b < num_b.length || mod ;)
{
if ( index_num_a < num_a.length )
{
mod += num_a.body[index_num_a++];
}
if ( index_num_b < num_b.length )
{
mod += num_b.body[index_num_b++];
}
num_arr[num_c.length++]=mod%10;
mod/=10;
}
num_c.body=new char[num_c.length];
for(int i=0;iisPositive;
for(int i=0; ilength; i++)
{
num_a->body[i]-=num_b->body[i];
}
for(int i=0; ilength; i++)
{
if (num_a->body[i]<0)
{
num_a->body[i]+=10;
num_a->body[i+1]--;
}
}
for(num_c.length=num_a->length; !num_a->body[num_c.length-1] ; num_c.length--);
num_c.body=new char[num_c.length];
for(int i=0; ibody[i];
}
return num_c;
}
long_num operator *(long_num num_a, long_num num_b)
{
long_num num_c;
num_c.isPositive=1;
if (num_a.isPositive!=num_b.isPositive) num_c.isPositive=0;
unsigned short* num_arr;
num_arr=new unsigned short[num_a.length+num_b.length];
for (int i=0; i9)
{
num_arr[i+1]+=num_arr[i]/10;
num_arr[i]%=10;
}
}
for(num_c.length=num_a.length+num_b.length; !num_arr[num_c.length-1] ; num_c.length--);
num_c.body=new char[num_c.length];
for(int i=0; i(long_num num1, long_num num2)
{
long_num num_c;
num_c.isPositive=1;
if (num1.isPositive!=num2.isPositive) num_c.isPositive=0;
long_num *num_a;
long_num *num_b;
num_a=&num1;
num_b=&num2;
char *buf,*result,*div;
buf=new char[num_a->length];
result=new char[num_a->length];
div=new char[num_b->length];
for(int i=0; ilength; i++)
{
buf[i]=num_a->body[num_a->length-i-1];
}
for(int i=0; ilength; i++)
{
div[i]=num_b->body[num_b->length-i-1];
}
unsigned short left=0,right=num_b->length-1,buf_length=num_b->length,index=0,maxindex=num_a->length-num_b->length;
int l,j,t=0;
while(index<=maxindex)
{
t=0;
result[index]=0;
if (index) t=buf[index-1];
for(j=0,l=index; (jlength) && (!t); j++, l++ )
t=buf[l]-div[j];
while(t>=0)
{
result[index]++;
for(j=0,l=index; jlength; j++, l++)
buf[l]-=div[j];
for(l=index+num_b->length-1; l>=index; l--)
{
if (buf[l]<0)
{
buf[l]+=10;
buf[l-1]--;
}
}
t=0;
if (index) t=buf[index-1];
for(j=0,l=index; (jlength) && (!t); j++, l++ )
t=buf[l]-div[j];
}
index++;
}
for(num_c.length=maxindex+1,l=0; !result[l] ; l++, num_c.length--);
num_c.body=new char[num_c.length];
for(j=0,l=maxindex; j
Метки:
с++
программирование
алгоритмы
длинная арифметика
длинные числа
длинная алгебра
алгоритмы длинной алгебры
-
Запись понравилась
-
0
Процитировали
-
0
Сохранили
-