欢迎光临散文网 会员登陆 & 注册

C++信息学竞赛例题解析——高精度加法

2020-11-06 23:00 作者:非知名科技区UP  | 我要投稿

近期呢,我们刚学了C++中string字符串的基础与应用。string字符串的一大好处就是输入的格式没有限制,长度不限。并且相较于C语言的char,总体而言方便了不少。当数据大小可能超过long long int的数据范围或者小数后面的位数超过双精度浮点数的时候,通过字符串实现的“高精度”计算就是一个很好的解决方案。在我们做真正的竞赛题时,可能会遇到超大的输入数据规模,这时候使用这种高精度数据的计算就变得很有必要。

我们这次作业中另一道题的数据规模,注意被除数是长度不超过30万位!!

历经本UP主3天3夜的思考+爆肝,我终于弄明白了这样的一道题的解法。

题目源自我们学校的信息竞赛题库——BNDSOJ,网址124.205.120.153

我的解决方案:

实际上这个题的难点有这么几个:

  1. 要让你的程序判定输入数据是否有小数点并且做出相应反馈。

  2. 要把小数和整数分开计算,但是小数到整数的进位问题是不可以忽视的。

  3. 根据我个人的习惯以及节约时间的原则,我会把计算用的数组给提前开辟好,在主程序开始前将需要的内存空间申请下来。但是再输出的时候我需要保证不输出多余的“0”

  4. 小数中的十分位进位到个位是一大难点。

我的程序详解


#include <iostream>
#include <string>
#include <cstring>

using namespace std;
【5】 bool ata = false,atb = false;
  string pa,pb,pc;
   int y = 0;
  bool sta = false,jin = false;
 int sn[40],ln[40];
【10】int main(){
 cin >> pa >> pb;//最基本的,声明数组和数据输入
 if(pa.find('.')==-1){
  ata = true;
   }  
【15】if(pb.find('.')==-1){ 
  atb = true; //确定输入的数据中有无整数
  }

 int sc[40][2],lc[40][2];
 int x = 0;
【20】 memset (sc,0,sizeof sc);
 memset (lc,0,sizeof lc);//清空用于计算的数组

  int g =pa.find('.'),h=pb.find('.');
 if(ata ==true)
 g = pa.size();
【25】if(atb == true)
 h = pb.size();//确定小数点在string数组中的位置

程序至此就算完成了基本的数据情况的设置,接下来,就是核心的计算环节了。

for(int a=g,b=h;a<=pa.size()||b<=pb.size();a++,b++,x++){
  if(pa[a]>='0'&&pa[a]<='9')
  sc[x][0]=pa[a]-'0';
 【30】 if(pb[b]>='0'&&pb[b]<='9')
  sc[x][1]=pb[b]-'0';            ''
   }

  memset (lc,0,sizeof lc);
 int a =pa.find('.'),b=pb.find('.');
 【35】if(ata ==true)
 a = pa.size();
 if(atb == true)
 b = pb.size();
 for( ;a>=0||b>=0;a--,b--,y++){
 【40】 if(pa[a]>='0'&&pa[a]<='9')
  lc [y][0]=pa[a]-'0';
  if(pb[b]>='0'&&pb[b]<='9')
  lc[y][1]=pb[b]-'0';
   }

//上面的环节是将字符串形式的数据转化成便于进行计算加工的数组形式。先转化的是小数部分,然后是整数部分。两个部分分别存放在两个不同的二维数组里,准备运算。
 【45】for(int z = 39;z>=0;z--){
  sn[z]=(sc[z][0]+sc[z][1])%10;
  sc[z-1][0]=sc[z-1][0]+((sc[z][0]+sc[z][1])/10);
   }
 if(sn[0]==1){
 【50】jin=true;//bool变量“ jin”反应的是小数是否需要进位到整数
 lc[0][0]=lc[0][0]+1;}
  for(int z = 0;z<=39;z++){
   if(jin==true&&z==0){
    ln[z]=ln[z]+((lc[z][0]+lc[z][1])%10);
 【55】 lc[z+1][0]=lc[z+1][0]+((lc[z][0]+lc[z][1])+1/10);
     }
  else{
  ln[z]=(lc[z][0]+lc[z][1])%10;
 lc[z+1][0]=lc[z+1][0]+((lc[z][0]+lc[z][1])/10);}
 【60】 }

这里是最中心的运算环节。记住我们应该从最小的一位算起,先算小数,再看是否需要进位,再算整数。此时答案已经被存储在in和sn两个数组里了。

最后的输出环节中,两个数组分别需要用不同的办法排除数组里多余的“0”,然后判断是否需要输出小数点以及后面的数。

for(int z = 30;z>0;z--){
  if(ln[z]!=0)
  sta = true;
  if(sta == true)
  cout << ln[z];
   }
 if(sta==false)
 cout <<"0"; //输出整数的部分

 int j = 29;
while(j>0&&sn[j]==0){
 j = j -1; }//通过一个while循环来确定输出多少位小数

if(j)
cout << ".";//确定输出小数点

 for(int a = 1;a<=j;a++){
  cout <<sn[a];
   }//输出小数,程序结束。
 return 0; }

由于本题中给的数据规模较小,我可以将程序写的相对复杂。但为了贯彻“节约每一毫秒的运行时间”的原则,我将数组和各类变量、string字符串的申请放到了主程序开始之前——这样测评机就不会将调用内存空间的时间计入运行时间内。



C++信息学竞赛例题解析——高精度加法的评论 (共 条)

分享到微博请遵守国家法律