知识点

文本文件是字符均为ascii编码的文件；其余为二进制文件
注意’0’在char和int之间的作用
第一步。对输入的数据标准化，明确每个数据/变量的含义、类型，增强代码的可解释性
测试用例的挑选。选最小的规模的能体现问题所在的用例。一旦出现问题，马上进行分析更改，脑中运行后，再开始run, 节省机器运行时间
解决问题的思路：搭建步骤框架，解决最小子问题（构建积木），然后搭积木（建大厦）。
1. 单元测试和集成测试必不可少

加法

    #include<iostream>
    #include<cmath>
    #include<string>
    #include<iterator>
    #include<algorithm>

    using namespace std;
    
    // big num add
    string bigNumAdd(string num1,string num2){
        // reverse
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());

        // standard-process data
        string bignum,smallnum,sumnum;
        if(num1.size()>num2.size()){
            bignum = num1; smallnum = num2;
        }else{
            bignum = num2; smallnum = num1;
        }
        sumnum = bignum;

        // add
        for(int i=0;i<smallnum.size();i++){
            int lowposVal = smallnum[i]-'0'+sumnum[i]-'0';
            int lowpos = i;
            sumnum[lowpos] = lowposVal+'0';
            while(lowposVal>9){
                sumnum[lowpos] = lowposVal+'0'-10;
                if(lowpos+1>=sumnum.size()){
                    sumnum.append(1,'0');
                }
                sumnum[lowpos+1] += 1;
                lowposVal = sumnum[lowpos+1]-'0';
                lowpos += 1;
            }

        }

        // return
        reverse(sumnum.begin(),sumnum.end());
        cout <<  sumnum << endl;
        return sumnum;
    }

    int main(){
        string num1,num2,sumnum;
        cin >> num1 >> num2;
        sumnum = bigNumAdd(num1,num2);
        return 0;
    }

减法

在加法的基础上改动，增加了符号判断函数

 char cmpStr(string num1,string num2){
     char sign = '+';
     // 1.size; 2. equation
    if(num1.size()>num2.size()){
        sign = '+';
    }else if(num1.size()<num2.size()){
        sign = '-';
    }else{
        for(int i=0;i<num1.size();i++){
            if(num1[i]>num2[i]){
                sign = '+';  break;
            }else if(num1[i]<num2[i]){
                sign = '-';  break;
            }else{}
        }
    }
    return sign;
 }
 // big num sub
 string bigNumSub(string num1,string num2){
     // get-sign
     char sign = cmpStr(num1,num2);
    
     // reverse
     reverse(num1.begin(),num1.end());
     reverse(num2.begin(),num2.end());
    
     // standard-process data
     string bignum,smallnum,sumnum;
     if(sign=='+'){
         bignum = num1; smallnum = num2;
     }else{
         bignum = num2; smallnum = num1;
     }
     sumnum = bignum;
    
     // sub
     for(int i=0;i<smallnum.size();i++){
         int lowposVal = sumnum[i]-smallnum[i];
         int lowpos = i;
         sumnum[lowpos] = lowposVal+'0';
         while(lowposVal<0){
             sumnum[lowpos] = 10+lowposVal+'0';
 //            if(lowpos+1>=sumnum.size()){
 //                sumnum.append(1,'0');
 //            }
             sumnum[lowpos+1] -= 1;
             lowposVal = sumnum[lowpos+1]-'0';
             lowpos += 1;
         }
    
     }
    
     // return
     reverse(sumnum.begin(),sumnum.end());
     cout <<  sign << sumnum << endl;
     return sumnum;
 }

乘法

先写出函数，实现大数与一位整数相乘

#include #include #include #include #include #include "bignumadd.h" using namespace std; string mulOnepos(string bignum, char smallOne){ string res; int curNum=0, lowNum=0, highNum=0;

// reverse(bignum.begin(),bignum.end());

 for(int i=0;i<bignum.size();i++){
     curNum = highNum + (bignum[i]-'0')*(smallOne-'0');
     lowNum = curNum % 10;
     if(curNum>=10){
         highNum = curNum / 10;
     }else{
         highNum = 0;
     }
     res.append(1,lowNum+'0');
 }
 if(highNum!=0){
     res.append(1,highNum+'0');
 }
 reverse(res.begin(),res.end());
 return res;  }

// big num multiply string bigNumMul(string num1,string num2){ // reverse reverse(num1.begin(),num1.end()); reverse(num2.begin(),num2.end());

 // standard-process data
 string bignum,smallnum,sumnum;
 if(num1.size()>num2.size()){
     bignum = num1; smallnum = num2;
 }else{
     bignum = num2; smallnum = num1;
 }
    
 // multiply
 for(int i=0;i<smallnum.size();i++){
     string tmp = mulOnepos(bignum, smallnum[i]);
     tmp.append(i,'0');  //        cout << i << " : tmp after o-add: " << tmp << endl;
     sumnum = bigNumAdd(tmp,sumnum);  //        cout << i << " : sumnum " << sumnum << endl;
 }

// reverse(sumnum.begin(),sumnum.end()); cout « sumnum « endl; return sumnum; }

int main(){ string num1,num2,sumnum; cin » num1 » num2; sumnum = bigNumMul(num1,num2); // cout « mulOnepos(num1,num2[0]) « endl; return 0; }

除法

基于减法操作

符号判断时，要加入为０的判断。同时，要去除前缀的冗余０

string rmDupZero(string num1){ int len = num1.size(),i; for(i=0;i<len;i++){ if(num1[i]!=’0’){ break; } } num1 = num1.substr(i,len-i); return num1; } char cmpStr(string num1,string num2){ char sign = ‘+’; // remove duplicate-zero num1 = rmDupZero(num1); num2 = rmDupZero(num2);

// 1.size; 2. equation
if(num1.size()>num2.size()){
    sign = '+';
}else if(num1.size()<num2.size()){
    sign = '-';
}else{
    for(int i=0;i<num1.size();i++){
        if(num1[i]>num2[i]){
            sign = '+';  break;
        }else if(num1[i]<num2[i]){
            sign = '-';  break;
        }else{
            sign = '=';
        }
    }
}
return sign;  }  // big num sub  string bigNumSub(string num1,string num2){
 // get-sign
 char sign = cmpStr(num1,num2);

 // reverse
 reverse(num1.begin(),num1.end());
 reverse(num2.begin(),num2.end());

 // standard-process data
 string bignum,smallnum,sumnum;
 if(sign=='+'){
     bignum = num1; smallnum = num2;
 }else{
     bignum = num2; smallnum = num1;
 }
 sumnum = bignum;

 // sub
 for(int i=0;i<smallnum.size();i++){
     int lowposVal = sumnum[i]-smallnum[i];
     int lowpos = i;
     sumnum[lowpos] = lowposVal+'0';
     while(lowposVal<0){
         sumnum[lowpos] = 10+lowposVal+'0';  //            if(lowpos+1>=sumnum.size()){  //                sumnum.append(1,'0');  //            }
         sumnum[lowpos+1] -= 1;
         lowposVal = sumnum[lowpos+1]-'0';
         lowpos += 1;
     }

 }

 // return
 reverse(sumnum.begin(),sumnum.end());  //    cout <<  sign << sumnum << endl;
 return sign+sumnum;  }

string bigNumDiv(string num1, string num2){ if(num2[0]==’0’){ string hint = “zero-error”; return hint; } string res,tmp; string num1Copy = num1, num2Copy = num2; int len1 = num1.size(); int len2 = num2.size(); int dlen = len1 - len2; for(int i=0;i<=dlen;i++){ res.append(1,’0’); num2.append(dlen-i,’0’); tmp = bigNumSub(num1,num2); while(tmp[0]==’+’){ res[i] += 1; num1 = tmp.substr(1,tmp.size()-1);

         cout << "num1(after-sub): num2(division) = " << num1 << " , " << num2<< endl;
         cout << "res: " << res << endl;
         tmp = bigNumSub(num1,num2);
         cout << "tmp(next-try): " << tmp << endl;
         cout << "******************" << endl;
     }
     num2 = num2Copy;
 }
 if(tmp[0]=='='){
     res[res.size()-1] += 1;
 }
 cout << res << endl;
 return res;  }

oj-大数的四则运算

知识点

加法

减法

乘法

除法

Similar Posts

Comments