高精度运算：
struct bign
{
int len,s[N];
bign() { memset(s,0,sizeof(s)); len=1; }
bign(int num) { *this=num; }
bign(char *num) { *this=num; }
bign operator =(int num)
{
char c[N];
sprintf(c,"%d",num);
*this=c;
return *this;
}
bign operator =(const char *num)
{
len=strlen(num);
REP(i,len) s[i]=num[len-1-i]-'0';
return *this;
}
string str()
{
string res="";
REP(i,len) res=(char)(s[i]+'0')+res;
return res;
}
void clean()
{
while (len>1&&!s[len-1]) len--;
}
bign operator +(const bign &b)
{
bign c;
c.len=0;
for (int i=0,g=0;g||i<len||i<b.len;i++)
{
int x=g;
if (i<len) x+=s[i];
if (i<b.len) x+=b.s[i];
c.s[c.len++]=x%10;
g=x/10;
}
return c;
}
bign operator -(const bign &b)
{
bign c;
c.len=0;
int x;
for (int i=0,g=0;i<len;i++)
{
x=s[i]-g;
if (i<b.len) x-=b.s[i];
if (x>=0) g=0;
else{
x+=10;
g=1;
};
c.s[c.len++]=x;
}
c.clean();
return c;
}
bign operator *(const bign &b)
{
bign c;
c.len=len+b.len;
REP(i,len) REP(j,b.len) c.s[i+j]+=s[i]*b.s[j];
REP(i,c.len-1) { c.s[i+1]+=c.s[i]/10; c.s[i]%=10; }
c.clean();
return c;
}
bool operator <(const bign &b)
{
if (len!=b.len) return len<b.len;
for (int i=len-1;i>=0;i--)
if (s[i]!=b.s[i]) return s[i]<b.s[i];
return false;
}
bign operator +=(const bign &b)
{
*this=*this+b;
return *this;
}
bign operator -=(const bign &b)
{
*this=*this-b;
return *this;
}
};
//istream& operator >>(istream &in,bign &x)
//{
// string s;
// in>>s;
// x=s.c_str();
// return in;
//}
ostream& operator <<(ostream &out,bign &x)
{
out<<x.str();
return out;
}
bign p[81],f[81][81],ans(0);
int n,m,a[81][81];
void init()
{
//ifstream cin("game.in"); //freopen("game.in","r",stdin);
cin>>n>>m; //scanf("%d%d",&n,&m);
REP(i,n) REP(j,m) cin>>a[i][j]; //scanf("%d",&a[i][j]);
p[0]=1; REP(i,m) p[i+1]=p[i]*2;
}
#define N 35 //const int N(35);
#define REP(i,n) for (int i=0;i<(n);i++)
struct bign
{
int len,s[N];
bign() { memset(s,0,sizeof(s)); len=1; }
bign(int num) { *this=num; }
bign(char *num) { *this=num; }
bign operator =(int num)
{
char c[N];
sprintf(c,"%d",num);
*this=c;
return *this;
}
bign operator =(const char *num)
{
len=strlen(num);
REP(i,len) s[i]=num[len-1-i]-'0';
return *this;
}
string str()
{
string res="";
REP(i,len) res=(char)(s[i]+'0')+res;
return res;
}
void clean()
{
while (len>1&&!s[len-1]) len--;
}
bign operator +(const bign &b)
{
bign c;
c.len=0;
for (int i=0,g=0;g||i<len||i<b.len;i++)
{
int x=g;
if (i<len) x+=s[i];
if (i<b.len) x+=b.s[i];
c.s[c.len++]=x%10;
g=x/10;
}
return c;
}
bign operator -(const bign &b)
{
bign c;
c.len=0;
int x;
for (int i=0,g=0;i<len;i++)
{
x=s[i]-g;
if (i<b.len) x-=b.s[i];
if (x>=0) g=0;
else{
x+=10;
g=1;
};
c.s[c.len++]=x;
}
c.clean();
return c;
}
bign operator *(const bign &b)
{
bign c;
c.len=len+b.len;
REP(i,len) REP(j,b.len) c.s[i+j]+=s[i]*b.s[j];
REP(i,c.len-1) { c.s[i+1]+=c.s[i]/10; c.s[i]%=10; }
c.clean();
return c;
}
bool operator <(const bign &b)
{
if (len!=b.len) return len<b.len;
for (int i=len-1;i>=0;i--)
if (s[i]!=b.s[i]) return s[i]<b.s[i];
return false;
}
bign operator +=(const bign &b)
{
*this=*this+b;
return *this;
}
bign operator -=(const bign &b)
{
*this=*this-b;
return *this;
}
};
//istream& operator >>(istream &in,bign &x)
//{
// string s;
// in>>s;
// x=s.c_str();
// return in;
//}
ostream& operator <<(ostream &out,bign &x)
{
out<<x.str();
return out;
}
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int a[10001]={0},b[10001]={0},c[10002]={0},d[10002]={0};
void zhuan(string s,int *d) //转换成数字数组
{
d[0]=s.size();
for (int i=d[0];i>0;i--)
d[i]=s[d[0]-i]-'0';
}
void add(int *a,int *b,int *c) //加法
{
c[0]=max(a[0],b[0]);
int jw=0;
for (int i=1;i<=c[0];i++)
{
c[i]=a[i]+b[i]+jw;
jw=c[i]/10;
c[i]%=10;
}
if (jw>0) { ++c[0]; c[c[0]]=1; }
}
bool bigger(int *a,int *b) //比较大小
{
if (a[0]!=b[0]) return a[0]>b[0]; //比较位数
for (int i=a[0];i>0;i--)
if (a[i]!=b[i]) return a[i]>b[i];
return true;
}
void sub(int *a,int *b,int *c) //减法
{
if (!bigger(a,b)) swap(a,b);
c[0]=a[0];
for (int i=1;i<=a[0];i++)
{
c[i]+=a[i]-b[i];
if (c[i]<0) c[i]+=10,c[i+1]--;
}
while (c[c[0]]==0&&c[0]>1) c[0]--;
}
void output(int *d) //输出数字数组d
{
for (int i=d[0];i>0;i--) cout<<d[i];
cout<<endl;
}
int main()
{
string s1,s2;
while (cin>>s1>>s2)
{
fill(a,a+10001,0);fill(b,b+10001,0);fill(c,c+10002,0);
zhuan(s1,a);
zhuan(s2,b); add(a,b,c); output(c);
sub(a,b,d);
if (!bigger(a,b)) cout<<"-";
output(d);
}
return 0;
}
高精度乘除法：
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int a[10001]={0},b[10001]={0},c[10002]={0},d[10002]={0};
void zhuan(string s,int *d) //转换成数字数组
{
d[0]=s.size();
for (int i=d[0];i>0;i--)
d[i]=s[d[0]-i]-'0';
}
bool bigger(int a[],int b[]) //比较大小
{
if (a[0]!=b[0]) return a[0]>b[0]; //比较位数
for (int i=a[0];i>0;i--)
if (a[i]!=b[i]) return a[i]>b[i];
return true;
}
void sub(int *a,int *b) //减法
{
for (int i=1;i<=a[0];i++)
{
a[i]-=b[i];
if (a[i]<0) a[i]+=10,a[i+1]--;
}
while (a[a[0]]==0&&a[0]>1) a[0]--;
}
void chen10(int *a)
{
if (a[0]==1&&a[1]==0) return ;
for (int i=a[0];i>=1;i--)
a[i+1]=a[i];
a[1]=0;
a[0]++;
}
void div(int *a,int *b,int *c)
{
d[0]=1;
for (int i=a[0];i>=1;i--)
{
chen10(d);
d[1]+=a[i];
while (bigger(d,b))
{
sub(d,b);
c[i]++;
}
}
c[0]=a[0];
while (c[c[0]]==0&&c[0]>1) c[0]--;
}
void output(int *d) //输出数字数组d
{
for (int i=d[0];i>0;i--) cout<<d[i];
cout<<endl;
}
int main()
{
string s1,s2;
while (cin>>s1>>s2)
{
fill(a,a+10001,0);fill(b,b+10001,0);fill(c,c+10002,0);fill(d,d+10002,0);
zhuan(s1,a);
zhuan(s2,b);
//mul(a,b,c); output(c);
div(a,b,c);
output(c); output(d);
}
//system("pause");
return 0;
}
posted on 2013-02-04 11:31
龙在江湖 阅读(243)
评论(0) 编辑 收藏 引用 所属分类:
算法