高精度算法smallfatC博客.docx
《高精度算法smallfatC博客.docx》由会员分享，可在线阅读，更多相关《高精度算法smallfatC博客.docx（16页珍藏版）》请在冰点文库上搜索。
高精度算法smallfatC博客
高精度算法-small-fat-C++博客
高精度算法#include<stdio.h>
#include<memory.h>
#include<iostream>
#include<string.h>
#include<math.h>
usingnamespacestd;
#defineMAX10000
#defineDEC10
#defineHEX16
#defineLARGE10//LARGER=10^（G-1）
#defineG2//10^（G-1）进制
classBigInt{
public:
unsignedlen;
unsignedv[MAX];
intsign;//记录数值符号
intrec;//记录除数是否为0
BigInt（）;
~BigInt（）;
/**************************
重载了三个赋值运算
调用各运算时要先由Mov（）函数将他们转化存储到数组v里面
**************************/
voidMov（BigInt&A）;
voidMov（char*A）;
voidMov（intA）;
voidCopy（BigInt&A,intbg,intn）;
BigIntAdd（BigInt&A）;
BigIntSub（BigInt&A）;
BigIntMul（BigInt&A）;
BigIntDiv（BigInt&A,BigInt&L）;
//比较函数
intCmp（BigInt&A）;
intCmp（BigInt&A,intb,intl）;//b是A.v数组中开始比较的位数，l是结束比较的位置
voidDisplay（）;
};
BigInt:
:
BigInt（）{
len=1;
for（inti=0;i<MAX;i++）{
v[i]=0;
}
}
BigInt:
:
~BigInt（）{
}
intBigInt:
:
Cmp（BigInt&A）{
if（len>A.len）return1;
if（len<A.len）return-1;
for（inti=len-1;i>=0;i--）{
if（v[i]>A.v[i]）return1;
if（v[i]<A.v[i]）return-1;
}
return0;
}
intBigInt:
:
Cmp（BigInt&A,intb,intl）{
if（len>l-b+1）return1;
if（len<l-b+1）return-1;
intj=l;
for（inti=len-1;i>=0;i--,j--）{
if（v[i]>A.v[j]）{return1;}
if（v[i]<A.v[j]）return-1;
}
return0;
}
voidBigInt:
:
Mov（intA）{
v[0]=A;
inti,k;
k=A;
i=0;
while（k>0）{
v[i]=k-k/LARGE*LARGE;
k=k/LARGE;
i++;
}
len=i;
}
voidBigInt:
:
Mov（BigInt&A）{
len=A.len;
for（inti=0;i<len;i++）{
v[i]=A.v[i];
}
while（i<MAX）{
v[i]=0;
i++;
}
}
voidBigInt:
:
Mov（char*A）{
intA_len=strlen（A）;
intk,i,j,t;
len=A_len/（G-1）;
if（A_len%（G-1））len++;
for（i=0,j=A_len-1;i<len&&j>=0;i++）{
k=1;
t=1;
while（j>=0&&k<G）{
v[i]+=（A[j]-'0'）*t;
t*=10;
j--;
k++;
}
}
}
BigIntBigInt:
:
Add（BigInt&A）{
BigIntX;
X.Mov（*this）;
intsum=0;
intcarry=0;
if（X.len<A.len）{
X.len=A.len;
}
for（inti=0;i<=X.len;i++）{
sum=A.v[i];
sum=sum+X.v[i]+carry;
X.v[i]=sum%LARGE;//10^（G-1）进制
carry=sum/LARGE;
}
if（X.v[X.len]）{
X.len++;
}
returnX;
}
BigIntBigInt:
:
Sub（BigInt&A）{
BigIntX;
BigIntT;
X.sign=0;
X.Mov（*this）;
T=X;
if（X.Cmp（A）<0）{
X.sign=1;
BigIntY;
Y.Mov（X）;
X.Mov（A）;
A.Mov（Y）;
T=X;
}
intcarry=0;
for（inti=0;i<X.len;i++）{
if（（T.v[i]>=A.v[i]+carry））{
X.v[i]=T.v[i]-carry-A.v[i];
carry=0;
}
else{
X.v[i]=LARGE+T.v[i]-A.v[i]-carry;
carry=1;
}
}
while（X.v[X.len-1]==0&&X.len>1）X.len--;
returnX;
}
BigIntBigInt:
:
Mul（BigInt&A）{
BigIntX;
intrec;
intcarry=0;
inti,j;
X.len=len+A.len;
for（i=0;i<X.len;i++）{
X.v[i]=0;
}
for（i=0;i<len;i++）{
for（j=0;j<A.len;j++）{
X.v[i+j]+=v[i]*A.v[j];
}
}
for（i=0;i<X.len;i++）{
rec=X.v[i]+carry;
X.v[i]=rec%LARGE;
carry=rec/LARGE;
}
while（X.len>1&&X.v[X.len-1]==0）{
X.len--;
}
returnX;
}
BigIntBigInt:
:
Div（BigInt&A,BigInt&X）{//X保存余数;
BigIntS;//S保存商;
BigIntY;
X.Mov（*this）;
X.rec=0;
S.Mov（0）;
if（A.Cmp（S）==0）{
X.rec=1;
returnX;
}
if（X.Cmp（A）<0）{
S.Mov（0）;
}
else{
S.len=X.len-A.len+1;
intl=A.len;
inti,j,t,k,g,c,h;
intcarry;
c=0;
//模拟除法，避免高精度乘法，用减法运算，不过用高精度乘法应该会更快一点
for（i=X.len-1,j=S.len-1;i>=A.len-1&&j>=0;i--,j--）{
t=0;h=2;
X.v[i]+=c*LARGE;
while（A.Cmp（X,i-A.len+1,i）<=0）{
if（A.Cmp（X,i-A.len+1,i）>0）break;
carry=0;
for（k=0,g=i-A.len+1;k<A.len;k++,g++）{
if（（X.v[g]>=A.v[k]+carry））{
X.v[g]=X.v[g]-carry-A.v[k];
carry=0;
}
else{
X.v[g]=LARGE+X.v[g]-A.v[k]-carry;
carry=1;
}
}
t++;
}
Y.Mov（X）;
c=X.v[i];
X.v[i]=0;
X.len--;
S.v[j]=t;
}
while（S.v[S.len-1]==0&&S.len>1）S.len--;
X.Mov（Y）;
while（X.v[X.len-1]==0&&X.len>1）X.len--;
}
returnS;
}
voidBigInt:
:
Display（）{
for（inti=len-1;i>=0;i--）{
printf（"%d",v[i]）;//printf（"%0（G-1）d",v[i]）;当G=3时为100进制，则printf（"%02d",v[i];
}
printf（"\n"）;
}
classTEST{
public:
voidadd（BigInt&A,BigIntB）{
BigIntC=A.Add（B）;
C.Display（）;
}
voidcmp（BigInt&A,BigIntB）{
inti=A.Cmp（B）;
if（i==1）printf（"A>B\n"）;
if（i==0）printf（"A==B\n"）;
if（i==-1）printf（"A<B\n"）;
}
voidsub（BigInt&A,BigIntB）{
BigIntC=A.Sub（B）;
if（C.sign）printf（"-"）;
C.Display（）;
}
voidmul（BigInt&A,BigInt&B）{
BigIntC=A.Mul（B）;
C.Display（）;
}
voiddiv（BigInt&A,BigInt&B）{
BigIntX;
BigIntC=A.Div（B,X）;
if（C.rec==1）{
printf（"除数为0\n"）;
}
else{
printf（"商:
\n"）;
C.Display（）;
printf（"余数:
\n"）;
X.Display（）;
}
}
};
intmain（）{
charp[MAX],q[MAX];
intg,h;
TESTtest;
while（scanf（"%s%s",p,q）!
=EOF）{
BigInta;
BigIntb;
a.Mov（p）;
b.Mov（q）;
//a.Display（）;
//b.Display（）;
a.Mov（p）;
b.Mov（q）;
/*printf（"testA+B\n"）;
test.add（a,b）;
printf（"testA-B\n"）;
test.sub（a,b）;
printf（"testA*B\n"）;
test.mul（a,b）;
printf（"testA/B\n"）;
test.div（a,b）;
*/
}
return0;
}
postedon2007-04-0823:
57small-fat阅读（1216）评论（5）编辑收藏引用所属分类:
之ACM.............、DataOfACM
Comments
#re:
高精度算法
an
应该找不到FAT和NTFS算法吧，微软不会公布出来吧？
突然对这两个算法感兴趣了，结果搜不到，不过看看你的，还是先赞个吧。
Posted@2008-12-1420:
50回复更多评论
#re:
高精度算法
an
while（scanf（"%s%s",p,q）!
=EOF）{
BigInta;
BigIntb;
a.Mov（p）;
b.Mov（q）;
a.Mov（p）;
b.Mov（q）;}
主函数中的这个不会有问题吧、？
一直输入，没看懂，如何停止输入啊？
EOF不就是-1么。
scanf流怎么会=Eof呢？
？
？
否则无止境的输入下去了。
。
Posted@2008-12-1420:
58回复更多评论
#re:
高精度算法
an
scanf后的p、q需要取地址符
可是没了还能运行？
我晕啊
大哥，您到底何种水平啊？
我就是学过一丁点c++，没一点经验。
while（scanf（"%s%s",&p,&q）!
=EOF）{
printf（"p=%s\t",p）;
printf（"q=%s\n",q）;
...
}这样就好点了。
。
p、q、数组都是一万。
。
。
能给我介绍下么？
你这到底干什么的，我还是不明白。
。
。
。
Posted@2008-12-1421:
08回复更多评论
#re:
高精度算法
郭如君
就是用字符串表示一个数，如从1乘到1000，每位数用一个字节表示，负数表示如
-12345，等价于-1,8,7,6,5,5,高位肯定是-1。
Posted@2009-07-1615:
52回复更多评论
#re:
高精度算法
郭如君
数据可以用字符串表示，并可以参与运算。
比如：
-12345，这个数据可以用字符串表示为：
-1，-2，-34，-5，经过补码运算，可以表示为：
-1，8，7，65，5。
从而可以运算，负数的补码运算以后，高位肯定是：
-1。
也可以表示为，-1，9，8，7，6，5，5。
这就要退一位，即把该数的长度减一位。
望各为专业人士能看懂。
Posted@2009-07-1812:
22回复更多评论
刷新评论列表
td{font-size:
12px}
.commentTextBox
{
font-family:
Verdana;
font-size:
13px;
}
.userData{BEHAVIOR:
url（#default#userdata）}
找优秀程序员，就在博客园
IT新闻：
·Dan计划：
重新定义人生的10000个小时
·谷歌前产品高级副总裁：
正与施密特一起写书
·消息称Napster两名创始人正从事新项目
·XX说吧今日新版上线：
取消强制身份认证
·Flurry报告：
iOS和Android持续蚕食掌上游戏机市场推荐职位：
·北京.NET高级程序员（We7开源CMS）
·北京ASP.NET开发工程师（广州博梦网络）
·北京.NET软件开发工程师（北京国双科技）
·广州.NET软件工程师（广州知微科技）
·ASP.NET开发工程师（北京环宇嘉艺）
·北京.NET高级工程师（月薪15k）（北京盛安德）
·高级ASP.NET开发工程师（上海乐丽网络）
·厦门高级.NET软件工程师（服务于美国Amazon）
博客园首页随笔：
·【自然框架】注册会员活动——第一份代码的修改建议（第一版）
·设计模式（5）-己所不欲，施之于人（代理模式）
·一个简单的行拖动效果
·出身在二三线城市软件工作者的悲哀
·iPhone中预览文档的三种方式
知识库：
·给页面加速，干掉DomLevel0Event
·告别程序员生涯，一点感慨
·开发工程师人生之路
·使用WCF实现SOA面向服务编程——架构设计
·带你走进缓存世界相关文章:
Trie数+DP
pow函数比较不稳定，可以用自定义的pown函数进行计算
multimap实现一对多映射
多源最短路径+最小路径覆盖
动态创建二维数组
用链表构造邻接矩阵
nlogn的最大上升子序列长度算法
高精度算法
最小堆
快速计算某个日期是星期几的经验公式网站导航:
博客园IT新闻博客园个人主页BlogJava博客生活IT博客网PHP博客博客园社区管理最简洁阅读版式：
高精度算法
升级会员 