运筹学与最优化理论基础——高精度加减乘除(C++实现)
运筹学与最优化理论基础——高精度加减乘除(C++实现)
AI那点小事
发布于 2020-04-20 12:34:46
发布于 2020-04-20 12:34:46
修正
在写单纯形算法时，发现了高精度分数存在bug与不足，所以必须对相关函数进行修改。主要有bug的函数是string DIVIDE_INT(string str1,string str2,int flag)，之前是为了运算简单起见，对于特殊除数与被除数进行特定的判断来减小计算复杂度，但是发现存在逻辑bug，判断这些条件之后，未直接返回结果使得程序仍然会执行正常的除法操作，因此对这个bug进行修正。同时为了方便之后的单纯型算法的编写，在此又特意添加两个函数int Compare2Zero()和int Compare2Fraction(Fraction fraction)，分别来比肩与0和分数fraction的大小。 在写两阶段单纯形算法时，发现了高精度分数中缺少相关取反和取倒数等接口导致代码出现大量重复代码。因此再次对高精度分数类进行修改。主要实现了分数取反和分数取倒数，并将整体代码进行了优化。由于两个函数过于简单，因此不对这两个函数进行讲解。
概要
这是本学期运筹学和最优化理论课的第一次作业。导师要求是实现含分数的高精度加减乘除运算，不能含有浮点数，这样会造成计算误差。为了实现分数的高精度加减乘除运算，我们首先必须实现整数的高精度加减乘除运算，之后将分数运算转化成分子和分母相关的高精度计算。所有代码上传自己的github，如有需要请移步：高精度计算
整数高精度加法
整数高精度加法运算算法如下： 1 若str1为0，直接返回str2，若str2为0，直接返回str1。 2 否则初始化标志位sign=1，来记录两个数中是否存在负数，初始化两个数str1和str2，这两个数用字符串表示。 3 若str1和str2都为负数时，sign=-1，表示结果应该为负数。之后去掉str1和str2的最前面的负号得到两个正数，之后计算两个正数加法的结果。 4 若str1为正，str2为负，将str2的最前面的负号去掉，转化为str1与-str2之间减法，即调用整数高精度减法函数。 5 若str1为负，str2为正，将str1的最前面的负号去掉，转化为str2与-str1之间减法，即调用整数高精度减法函数。 6 若str1和str2都为正数，首先比较str1和str2字符串长度大小，较短的字符串在前面添加字符串长度之差的个数的0，以用来对齐。之后初始化int1=int2=0，结果字符串str为空，int1用来记录每一位的对应加法结果，int2记录进位。将str1和str2从后往前遍历，int1=(int(str1[i])-‘0’+int(str2[i])-‘0’+int2)%10,即int1保留对应位加法的个位结果，int2=(int(str1[i])-‘0’+int(str2[i])-‘0’+int2)/10，即int2保留对应位加法十位结果，str=char(int1+‘0’)+str。结束遍历之后，若int不为零，说明仍然有进位，那么直接将int2追加到结果字符串的最前面。 7 最后判断sign是否为-1，若为-1，且str不为0，那么必须在结果字符串str前加上负号。 部分代码如下：
//整数加法
string ADD_INT(string str1,string str2)
{
if(str1.compare("0") == 0){
return str2;
}
if(str2.compare("0") == 0){
return str1;
}
//高精度加法
int sign=1; //sign 为符号位
string str;
if(str1[0]=='-'){ //str1为负数
if (str2[0]=='-'){ //str2为负数
sign=-1; //-1代表两个负数相加
// 去掉两个符号后相加
str=ADD_INT(str1.erase(0,1),str2.erase(0,1));
}else{//str2为正数
//去掉str1的符号，转化为减法
str=SUB_INT(str2,str1.erase(0,1));
}
}else{ // str1为正数
if(str2[0]=='-'){ //str2为负数
// 去掉str2的负数，转化为减法
str=SUB_INT(str1,str2.erase(0,1));
}else{ //str2为正数
//把两个整数对齐，短整数前面加0补齐
string::size_type L1,L2;
int i;
L1=str1.size();
L2=str2.size();
if(L1<L2){ // str1的长度比str2小，str1在前补充0
for(i=1;i<=L2-L1;i++){
str1="0"+str1;
}
}else{ // str2的长度比str2小，str2在前面补充0
for(i=1;i<=L1-L2;i++){
str2="0"+str2;
}
}
int int1=0,int2=0; //int2 记录进位，int1记录结果
for(i=str1.size()-1;i>=0;i--){
int1=(int(str1[i])-'0'+int(str2[i])-'0'+int2)%10;
int2=(int(str1[i])-'0'+int(str2[i])-'0'+int2)/10;
str=char(int1+'0')+str;
}
if(int2!=0){ //计算结束后还有进位，直接在前面补充
str=char(int2+'0')+str;
}
}
}
//运算后处理符号位
if((sign==-1)&&(str[0]!='0')){
str="-"+str;
}
return str;
}整数高精度减法
整数高精度减法运算算法如下： 1 若str1为0，那么若str2为0直接返回0，若身直接返回str2，若str2不为0，返回str2的相反数。若str2为0，直接返回str1。 2 否则初始化标志位sign=1，来记录两个数中是否存在负数，初始化两个数str1和str2，str1为被减数，str2为减数。这两个数用字符串表示。 3 若str2为负数，去掉str2的最前面的负号，将str1与str2之间的减法转化为str1与str2的相反数之间的加法得到结果str。 4 若str1为负，str2为正，将转化为str2与str1相反数之间加法，得到其结果str，之后将str加上符号就是我们想要的结果。 5 若str1和str2都为正，首先判断str1和str2两个字符串的大小，若相等则直接返回字符串“0”，若str1小于str2，那么sign=-1，并将str1与str2互换tempint =str1.size()-str2.size()，tempint记录连个字符串长度之差。之后值较小的字符串(str2)进行反向遍历，str1[i+tempint]<str2[i]时，j=1利用j记录偏移位，之后开始循环，若str1[i+tempint-j]==‘0’，说明第i位之前j位的数字为0，需要进行借位，借位之后需要将该位置成“9”，即str1[i+tempint-j]=‘9’，否则str1[i+tempint-j]=char(int(str1[i+tempint-j])-1)，并在此中断循环。之后在结果字符串前面加上char(str1[i+tempint]-str2[i]+’:’)，即str=char(str1[i+tempint]-str2[i]+’:’)+str。若str1[i+tempint]>=str2[i],那么对应相减即可，即str=char(str1[i+tempint]-str2[i]+‘0’)+str。遍历结束后，若有多余位，则直接追加到str前面。 6 最后将结果str的最前面可能存在在0给去掉，之后判断sign是否为-1，若为将str前加上负号。 部分代码：
//整数减法
string SUB_INT(string str1,string str2)
{
//高精度减法
int sign=1; //sign为符号位
string str;
int i,j;
if(str2[0]=='-'){ //str2为负数
// 去掉str2的符号，转化为加法
str=ADD_INT(str1,str2.erase(0,1));
}else{ // str2为正数
if(str1[0] == '-'){ //str1为负数，转化为加法
str = ADD_INT(str1.erase(0,1),str2);
str = "-"+str;
}else{ //str1为正数
// 判断str1和str2大小
int res=compare(str1,str2);
//cout<<"==="<<res<<endl;
if(res==0){ //str1和str2相等
return "0";
}
if(res<0){ //str1小于str2
sign=-1; //标志位置为-1
// str1和str2互换
string temp =str1;
str1=str2;
str2=temp;
}
string::size_type tempint;
tempint=str1.size()-str2.size();
// 按值较小者的进行遍历，tempint=0说明长度相等，大于0则str1长度大于str2
// 从最后一位开始遍历
for(i=str2.size()-1;i>=0;i--){
// str1的对应为小于str2的对应位
if(str1[i+tempint]<str2[i]){
j=1; //偏移位
//开始循环，开始寻找借位
while(1){
//前面的位为0，借1置成9
if(str1[i+tempint-j]=='0'){
str1[i+tempint-j]='9';
j++;
}else{//前面的位为0，借1，当前位减1
str1[i+tempint-j]=char(int(str1[i+tempint-j])-1);
break;
}
}
str=char(str1[i+tempint]-str2[i]+':')+str;
}else{
str=char(str1[i+tempint]-str2[i]+'0')+str;
}
}
//把多余为进行向前补充
for(i=tempint-1;i>=0;i--){
str=str1[i]+str;
}
}
}
//去除结果中多余的前导0
str.erase(0,str.find_first_not_of('0'));
if(str.empty()){
str="0";
}
if((sign==-1) && (str[0]!='0')){
str ="-"+str;
}
return str;
}整数高精度乘法
整数高精度乘法运算算法如下： 1 初始化标志位sign=1，来记录两个数中是否存在负数，初始化两个数str1和str2。这两个数用字符串表示。 2 若str1为负数，去掉str1的最前面的负号，sign = -1。即有一个是负数，乘积为负数。 3 若str2为负数，去掉str2的最前面的负号，sign=-1。即两个负数乘积为正数。 4 * str保初始化为空，保存两个数的乘积结果。根据str2进行方向遍历，tempstr保存每次循环的计算记过，int1=0，int2=0，i=L2-1，int3=int(str2[i])-‘0’，判断int3是否为0，若不为0，那么在tempstr前端补0，个数为(L2-1-i)。之后对str1进行反向遍历，int1=(int3*(int(str1[j])-‘0’)+int2)%10，int2=(int3*(int(str1[j])-‘0’)+int2)/10，即int1记录个位数，int记录十位数。tempstr=char(int1+‘0’)+tempstr，即将个位数追加到tempstr前面。对str1遍历结束后，若int2不为0，那么必须将int2追加到tempstr前面。之后将str和tempst进行相加。* 5 str2遍历结束后，去除结果中最前面连续的0。之后若str为空，那么str=“0”，若sign=-1，且str不为0，那么str前加上负号。 部分代码如下：
//整数乘法
string MUL_INT(string str1,string str2)
{
//str1和str2至少存在1个0，直接返回0
if(str1.compare("0") == 0 || str2.compare("0") == 0){
return "0";
}
//str1为1直接返回str2
if(str1.compare("1") == 0){
return str2;
}
//str2为1直接返回str1
if(str2.compare("1") == 0){
return str1;
}
//str1为-1
if(str1.compare("-1") == 0){
//str2为负数
if(str2.compare("0") < 0){
return str2.erase(0,1);
}
//str2为正数
return "-"+str2;
}
//str2为1
if(str2.compare("-1") == 0){
//str1为负数
if(str1.compare("0") < 0){
return str1.erase(0,1);
}
//str1为正数
return "-"+str1;
}
//高精度乘法
int sign=1; //sign 为符号位
string str;
// str1为负数
if(str1[0]=='-'){
sign*=-1; // 标志位乘-1
str1 =str1.erase(0,1); // 去掉负号
}
// str2为负数
if(str2[0]=='-'){
sign*=-1; // 标志位乘-1
str2 =str2.erase(0,1); // 去掉负号
}
int i,j;
string::size_type L1,L2;
L1=str1.size();
L2=str2.size();
for(i=L2-1;i>=0;i--){ //模拟手工乘法竖式
string tempstr;
int int1=0,int2=0,int3=int(str2[i])-'0';
if(int3!=0){
// 下面的循环实现结果后端补0操作
for(j=1;j<=(int)(L2-1-i);j++){
tempstr="0"+tempstr;
}
for(j=L1-1;j>=0;j--){
// int1记录个位数，int记录十位数
int1=(int3*(int(str1[j])-'0')+int2)%10;
int2=(int3*(int(str1[j])-'0')+int2)/10;
tempstr=char(int1+'0')+tempstr;
}
if(int2!=0){
tempstr=char(int2+'0')+tempstr;
}
}
// 当前结果和tempstr向将
str=ADD_INT(str,tempstr);
}
//去除结果中的前导0
str.erase(0,str.find_first_not_of('0'));
if(str.empty()){
str="0";
}
if((sign==-1) && (str[0]!='0')){
str="-"+str;
}
return str;
}整数高精度除法
整数高精度除法运算算法如下： 1 quotient，residue分别记录商和余数。若str2为0时，那么quotient，residue置为“ERROR”，若str1为“0”时，quotient，residue置为1，若str2为“1”，quotient=str1，residue=“0”, str2为“-1”时，str1若位负数，quotient=str1的相反数，若为正数，quotient = “-”+str1，不管str1为正数还是负数，residue = “0”。 2 否则，初始化标志位sign1=1,sign2=1,初始化两个数str1和str2。这两个数用字符串表示。 3 若str1为负数，那么直接返回去掉str1的最前面的负号，sign1 = -1，sign2 = -1，即一正一负的的商和余数都为负数 4 若str2为负数，去掉str2的最前面的负号，sign1 = -1，sign2 = -1。即两个负数的商和余数为正数。 5 比较str1和str2的大小，若str1小于str2，那么quotient=“0”，residue =str1 6 若str1等于str2，quotient=“1”，residue =“0”。 7 若str1大于str2，L1=str1.size()，L2=str2.size()，tempstr保存当前结果，从L2-1遍历到L1，tempstr=tempstr+str1[i]，之后去掉前导0，若tempstr为空，那么tempstr = “0”。反之，从ch=9一直遍历到0进行试商，找到之后停止试商quotient=quotient+ch，tempstr =SUB_INT(tempstr,MUL_INT(str2,str));。循环结束后，residue=tempstr; 8 之后去除商的前导0。判断sign1，sign2是否为-1，若为，那么将商和余数加上负号。返回商和余数 str保初始化为空，保存两个数的乘积结果。根据str2进行方向遍历，tempstr保存每次循环的计算记过，int1=0，int2=0，i=L2-1，int3=int(str2[i])-‘0’，判断int3是否为0，若不为0，那么在tempstr前端补0，个数为(L2-1-i)。之后对str1进行反向遍历，int1=(int3(int(str1[j])-‘0’)+int2)%10，int2=(int3(int(str1[j])-‘0’)+int2)/10，即int1记录个位数，int记录十位数。tempstr=char(int1+‘0’)+tempstr，即将个位数追加到tempstr前面。对str1遍历结束后，若int2不为0，那么必须将int2追加到tempstr前面。之后将str和tempst进行相加。 部分代码如下：
//整数除法
string DIVIDE_INT(string str1,string str2,int flag)
{
//高精度除法。flag==1时,返回商; flag==0时,返回余数
string quotient,residue; //定义商和余数
int sign1=1,sign2=1;
//判断除数是否为0
if(str2 == "0"){
quotient= "ERROR!";
residue = "ERROR!";
if(flag==1){
return quotient;
}else{
return residue;
}
}
//判断被除数是否为0
if(str1=="0"){
quotient="0";
residue ="0";
if(flag == 1){
return quotient;
}else{
return residue;
}
}
//被除数为1，直接返回str1
if(str2 == "1"){
quotient = str1;
residue = "0";
if(flag == 1){
return quotient;
}else{
return residue;
}
}
//被除数为-1
if(str2 == "-1"){
if(str1.compare("0") < 0){
quotient = str1.erase(0,1);
}else{
quotient = "-"+str1;
}
residue = "0";
if(flag == 1){
return quotient;
}else{
return residue;
}
}
// str1为负数
if(str1[0]=='-'){
str1 = str1.erase(0,1); //去除前导0
sign1 *= -1;
sign2 = -1;
}
// str2为负数
if(str2[0]=='-'){
str2 = str2.erase(0,1); //去除前导0
sign1 *= -1;
}
//比较str1和str2的大小
int res=compare(str1,str2);
// str1小于str2
if(res<0){
// 商为0，余数为str1
quotient="0";
residue =str1;
}else if(res == 0){
// str1与str2相等,商为1，余数为0
quotient="1";
residue ="0";
}else{
// str1大于str2
string::size_type L1,L2;
L1=str1.size();
L2=str2.size();
string tempstr;
tempstr.append(str1,0,L2-1);
for(int i=L2-1;i<L1;i++){ //模拟手工除法竖式
tempstr=tempstr+str1[i];
//可能出现不够除的情况，那么必须把前导0去掉
tempstr.erase(0,tempstr.find_first_not_of('0'));
if(tempstr.empty()){
tempstr="0";
}
for(char ch='9';ch>='0';ch--){ //试商
string str;
str=str+ch;
if(compare(MUL_INT(str2,str),tempstr)<=0){
quotient=quotient+ch;
tempstr =SUB_INT(tempstr,MUL_INT(str2,str));
break;
}
}
}
residue=tempstr;
}
//去除结果中的前导0
quotient.erase(0,quotient.find_first_not_of('0'));
if(quotient.empty()){
quotient="0";
}
if((sign1==-1)&&(quotient[0]!='0')){
quotient="-"+quotient;
}
if((sign2==-1)&&(residue [0]!='0')){
residue ="-"+residue ;
}
if(flag==1){
return quotient;
}else{
return residue;
}
}
//整数除法，返回商
string DIV_INT(string str1,string str2
{
//高精度除法,返回商
return DIVIDE_INT(str1,str2,1);
}
//整肃除法，返回余数
string MOD_INT(string str1,string str2)
{
//高精度除法,返回余数
return DIVIDE_INT(str1,str2,0);
}两个整数的最大公约数
两个整数的最大公约数算法流程： 1 初始化sign=1，标志其中两个数是否有负数，两个数用str1和str2表示，字符串存储 2 若str1为负数，sign*=-1，即一正一负的最大公约数为负数 3 若str2为负数，sign*=-1，即两个负数的最大公约数为正数 4 若str1和str2至少有一个为1，判断sign是否为-1，若是返回-1，否则返回1 4 反之利用辗转相除法求得最大公约数，之后判断sign是否为-1，若是最大公约数前加负号。之后返回最大公约数 部分代码：
//计算两个数最大公约数
string gcd(string str1,string str2){
int sign = 1;
if(str1[0] == '-'){ // str1为负数，去除前导负号
sign *= -1; //标志位取相反数
str1 = str1.erase(0,1);
}
if(str2[0] == '-'){ // str2为负数，去除前导负号
sign *= -1; //标志位取相反数
str2 = str2.erase(0,1);
}
if(str1.compare("1") == 0 || str2.compare("1") == 0){ //str1或str2为1时
if(sign == -1){ //标志位位-1，str2加负号
return "-1";
}
return "1";
}else{ //str1和str2都不为1时，利用辗转相除法求最大公约数
string gcd;
while(str2.compare("0") != 0){
gcd = this->MOD_INT(str1,str2);
str1 = str2;
str2 = gcd;
}
gcd = str1;
if(sign == -1){
gcd = "-"+gcd;
}
return gcd;
}
} 分数高精度加法
分数高精度加法运算算法如下： 1 若num1的分母不为0，num2的分子为0，则返回num1。 2 若num2的分母不为0，num1的分子为0，则返回num2。 3 否则，若num1和num2的分母相等，num的分母为num1的分母，num的分子为num1和num2的分子之和。然后寻求分子和分母的最大公约数，然后将分子分母除以这个最大公约数。 4 反之，num1和num2的分母不相等，首先对分数进行通分，进行之后进行分子加法，然后对分子分母进行约分。即执行下列操作： string fenzi1 = this->MUL_INT(num1.fenzi,num2.fenmu); string fenzi2 = this->MUL_INT(num2.fenzi,num1.fenmu); fenzi = this->ADD_INT(fenzi1,fenzi2); fenmu = this->MUL_INT(num1.fenmu,num2.fenmu); gcd = this->gcd(fenmu,fenzi); fenmu = this->DIV_INT(fenmu,gcd); fenzi = this->DIV_INT(fenzi,gcd); 部分代码：
//分数加法
Fraction ADD(Fraction num1,Fraction num2)
{
string fenmu,fenzi,gcd;
//num1分母不为0，num1分子为0，直接返回num2
if(num1.fenmu.compare("0") != 0 && num1.fenzi.compare("0") == 0){
return num2;
}
//num1分母不为0，num2分子为0，直接返回num1
if(num2.fenmu.compare("0") != 0 && num2.fenzi.compare("0") == 0){
return num1;
}
if(num1.fenmu.compare(num2.fenmu) == 0){//两个分母相等
fenmu = num1.fenmu; //保留分母
fenzi = this->ADD_INT(num1.fenzi,num2.fenzi); //计算分子
gcd = this->gcd(fenmu,fenzi); //计算最大公约数
if(gcd.compare("1") != 0){ //最大公约数不为1时，需要进行约分
fenmu = this->DIV_INT(fenmu,gcd); //约分后的分母
fenzi = this->DIV_INT(fenzi,gcd); //约分后的分子
}
}else{//分母不相等
string fenzi1 = this->MUL_INT(num1.fenzi,num2.fenmu); //计算通分后的分子1
string fenzi2 = this->MUL_INT(num2.fenzi,num1.fenmu); //计算通分后的分子2
fenzi = this->ADD_INT(fenzi1,fenzi2); //计算分子
fenmu = this->MUL_INT(num1.fenmu,num2.fenmu); //计算分母
gcd = this->gcd(fenmu,fenzi); //计算分子和分母的最大公约数
if(gcd.compare("1") != 0){ //最大公约数不为1时，需要进行约分
fenmu = this->DIV_INT(fenmu,gcd); //计算通分后的分母
fenzi = this->DIV_INT(fenzi,gcd); //计算通分后的分子
}
}
Fraction result;
result.set(fenmu,fenzi);
return result;
}分数高精度减法
分数高精度减法运算算法如下： 1 若num1的分母不为0，num1的分子为0，则返回num2的相反数。 2 若num2的分母不为0，num2的分子为0，则返回num1。 3 否则，若num1和num2的分母相等，num的分母为num1的分母，num的分子为num1和num2的分子之和。然后寻求分子和分母的最大公约数，然后将分子分母除以这个最大公约数。 4 反之，num1和num2的分母不相等，那么执行下列操作： string fenzi1 = this->MUL_INT(num1.fenzi,num2.fenmu); string fenzi2 = this->MUL_INT(num2.fenzi,num1.fenmu); fenzi = this->SUB_INT(fenzi1,fenzi2); fenmu = this->MUL_INT(num1.fenmu,num2.fenmu); gcd = this->gcd(fenmu,fenzi); fenmu = this->DIV_INT(fenmu,gcd); fenzi = this->DIV_INT(fenzi,gcd);
部分代码：
//分数减法
Fraction SUB(Fraction num1,Fraction num2)
{
//num1为0时，返回num2的相反数
if(num1.fenmu.compare("0") != 0 && num1.fenzi.compare("0") == 0){
num2.setOpposite();
return num2;
}
//num2为0时，返回num1
if(num2.fenmu.compare("0") != 0 && num2.fenzi.compare("0") == 0){
return num1;
}
string fenmu,fenzi,gcd;
if(num1.fenmu.compare(num2.fenmu) == 0){//两个分母相等
fenmu = num1.getFenmu(); //保留分母
fenzi = this->SUB_INT(num1.getFenzi(),num2.getFenzi()); //计算分子
gcd = this->gcd(fenmu,fenzi); //计算最大公约数
if(gcd.compare("1") != 0){ //最大公约数不为1时，需要进行约分
fenmu = this->DIV_INT(fenmu,gcd); //约分后的分母
fenzi = this->DIV_INT(fenzi,gcd); //约分后的分子
}
}else{//分母不相等
string fenzi1 = this->MUL_INT(num1.fenzi,num2.fenmu); //计算通分后的分子1
string fenzi2 = this->MUL_INT(num2.fenzi,num1.fenmu); //计算通分后的分子2
fenzi = this->SUB_INT(fenzi1,fenzi2); //计算分子
fenmu = this->MUL_INT(num1.fenmu,num2.fenmu); //计算分母
gcd = this->gcd(fenmu,fenzi); //计算分子和分母的最大公约数
if(gcd.compare("1") != 0){ //最大公约数不为1时，需要进行约分
fenmu = this->DIV_INT(fenmu,gcd); //计算通分后的分母
fenzi = this->DIV_INT(fenzi,gcd); //计算通分后的分子
}
}
Fraction result;
result.set(fenmu,fenzi);
return result;
}分数高精度乘法
分数高精度减法运算算法如下： 1 num1和num2的分子中出现至少一个0，是直接返回0； 2 若num1为1时 返回num2，若num2为1时返回num1 3 若num1为-时 返回num2相反数，若num2为-1时返回num1相反数 4 若num1和num2的分母中出现都为1时，fenmu = 1;若num1分母为1，num2的分母不为1时，fenmu = num2.fenmu,若num2分母为1，num1的分母不为1时，fenmu = num1.fenmu 5 若num1和num2的分子中出现都为1时，fenzi = 1;若num1分子为1，num2的分子不为1时，fenzi= num2.fenzi,若num2分子为1，num1的分子不为1时，fenzi = num1.fenzi 6 分子分母都不为1时需要进行约分，计算分子分母的最大公约数，进行约分。 部分代码：
//分数乘法
Fraction MUL(Fraction num1,Fraction num2)
{
string fenmu,fenzi;
//两个分母至少有一个0时，直接返回无穷大("9999999/1")
if(num1.fenmu.compare("0") == 0|| num2.fenmu.compare("0") == 0){
Fraction result;
result.set("9999999/1");
return result;
}
//两个分子至少有一个0时，直接返回0
if(num1.fenzi.compare("0") == 0|| num2.fenzi.compare("0") == 0){//分子出现0时，直接返回0
Fraction result;
result.set("0/1");
return result;
}
//计算分母
if(num1.fenmu.compare("1") == 0 && num2.fenmu.compare("1") == 0){
//两个分母全为1
fenmu = "1";
}else if(num1.fenmu.compare("1") == 0 && num2.fenmu.compare("1") != 0){
//num1分母为1
fenmu = num2.fenmu;
}else if(num1.fenmu.compare("1") != 0 && num2.fenmu.compare("1") == 0){
//num2分母为1
fenmu = num1.fenmu;
}else{//两个分母都不为1
fenmu = this->MUL_INT(num1.fenmu,num2.fenmu);
}
//计算分子
if(num1.fenzi.compare("1") == 0 && num2.fenzi.compare("1") == 0){
//两个分子全为1
fenzi = "1";
}else if(num1.fenzi.compare("1") == 0 && num2.fenzi.compare("1") != 0){
//num1分子为1
fenzi = num2.fenzi;
}else if(num1.fenzi.compare("1") != 0 && num2.fenzi.compare("1") == 0){
//num2分子为1
fenzi = num1.fenzi;
}else{//两个分子都不为1
fenzi = this->MUL_INT(num1.fenzi,num2.fenzi);
}
//分母都不为1,且分子不为0时可能需要进行约分
if(fenmu.compare("1") != 0 && fenzi.compare("1") != 0){
string gcd = this->gcd(fenmu,fenzi);
if(gcd.compare("1") != 0){//最大公约数不为1时，需要进行约分
fenmu = this->DIV_INT(fenmu,gcd); //计算通分后的分母
fenzi = this->DIV_INT(fenzi,gcd); //计算通分后的分子
}
}
Fraction result;
result.set(fenmu,fenzi);
return result;
} 分数高精度除法
分数高精度减法运算算法如下： 1 num1为0时，直接返回0； 2 num2为1时，直接返回num1 3 否则转化为num1与num2的导数的乘积运算。
部分代码：
//分数除法
Fraction DIV(Fraction num1,Fraction num2)
{
// num1为0时
if(num1.fenmu.compare("0") != 0 && num1.fenzi.compare("0") == 0){
Fraction result;
result.set("0/1");
return result;
}
//num2为1时
if(num2.fenmu.compare("1") == 0 && num2.fenzi.compare("1") == 0){
return num1;
}
//num2为0时，我们将结果初始化为"9999999/1"
if(num2.fenmu.compare("1") == 0 && num2.fenzi.compare("0") == 0){
Fraction result;
result.set("9999999/1");
return result;
}
string fenmu = num2.fenzi;
string fenzi = num2.fenmu;
//除法转化为乘法
Fraction tmp;
tmp.set(fenmu,fenzi);
return tmp.MUL(num1,tmp);
} 与0比较大小
与0比较大小算法如下： 1 设置分子分母正负标志sign_fenzi和sign_fenmu，都初始化为1，代表为正数； 2 若分子为负，sign_fenzi = -1，分子去掉前导负号 3 若分母为负，sign_fenmu = -1，分母去掉前导负号 4 分别比较分子分母的绝对值与0的大小，分别将比较结果记录在ans_fenzi和ans_fenmu。 5 若sign_fenmu == -1,ans_fenmu1,则ans_fenmu = -1 6 若sign_fenzi == -1,ans_fenzi1,则ans_fenzi = -1 7 若ans_fenzi == 0且ans_fenmu != 0，即分子为0，分母不为0，返回0 8 若ans_fenzians_fenmu >0即分子分母同号，返回1 9 若ans_fenzians_fenmu < 0即分子分母异号，返回-1 部分代码如下：
//判断分数与0的大小
int Compare2Zero()
{
int sign_fenzi = 1;
int sign_fenmu = 1;
int sign = 1; //记录是否分子含有负号
string fenzi = this->fenzi;
string fenmu = this->fenmu;
if(fenzi[0] == '-'){ //分子为负数时，改变标志位
sign_fenzi = -1;
fenzi = fenzi.erase(0,1);
}
if(fenmu[0] == '-'){ //分子为负数时，改变标志位
sign_fenmu = -1;
fenmu = fenmu.erase(0,1);
}
//比较分子的绝对值与0的大小
int ans_fenzi = this->compare(fenzi,"0");
//比较分母的绝对值与0的大小
int ans_fenmu = this->compare(fenmu,"0");
if(sign_fenzi == -1 && ans_fenzi == 1){
ans_fenzi = -1;
}
if(sign_fenmu == -1 && ans_fenmu == 1){
ans_fenmu = -1;
}
int flag;
if(ans_fenzi == 0 && ans_fenmu != 0){
//分子为0，分母不为0，返回0
flag = 0;
}
if(ans_fenzi*ans_fenmu > 0){ //分子分母同号，返回1
flag = 1;
}
if(ans_fenzi*ans_fenmu < 0){ //分子分母异号，返回-1
flag = -1;
}
return flag;
}与特定分数比较大小
与特定分数比较大小算法如下： 1 两个分数作差 2 返回两个分数的差值与0的大小即可 部分代码如下：
//两个分数之间的比较
int Compare2Fraction(Fraction fraction)
{
Fraction ans,tmp;
/*cout<<"/////////////////////////"<<endl;
cout<<"当前分数："<<this->result()<<endl;
cout<<"作对比的分数:"<<fraction.result()<<endl;*/
tmp.set(this->getFenmu(),this->getFenzi());
//减后的结果与0作对比就是两个分数之间的大小关系
ans = ans.SUB(tmp,fraction);
/*cout<<"相减结果为："<<ans.result()<<endl;
cout<<"对比结果为："<<ans.Compare2Zero()<<endl;
cout<<"/////////////////////////"<<endl;*/
return ans.Compare2Zero();
} C++ 代码
由于代码过长，请转移至github下载进行阅读。该代码的github网址为：高精度分数计算
#include <iostream>
#include <string>
using namespace std;
class Fraction{
private:
string fenmu; //分母
string fenzi; //分子
public:
//分数类的构造函数
void set(string str){
//字符串中没有'/'，直接分母置为1，分子为str
if(str.find('/') == string::npos){
this->fenmu = "1";
this->fenzi = str;
}else{
int index = str.find('/'); //找到'/'的位置
string fenzi = str.substr(0,index); //0到index之前为分子
string fenmu = str.substr(index+1,str.length()-index-1); //index之后的字符串为分母
this->setFenmu(fenmu);
this->setFenzi(fenzi);
}
}
//分数类的设置函数
void set(string fenmu,string fenzi){
if(fenmu[0] == '-' && fenzi[0] == '-'){ // 分子分母同为负
fenmu = fenmu.erase(0,1);
fenzi = fenzi.erase(0,1);
}else if(fenmu[0] == '-' && fenzi[0] != '-'){ //分母为负 分子为正
fenmu = fenmu.erase(0,1);
fenzi = "-"+fenzi;
}
if(fenzi[0] == '-'){ //分子为0时，前面有负号
string tmp = fenzi.substr(1,fenzi.length()-1);
if(tmp.compare("0") == 0){
fenzi = tmp;
}
}
this->setFenmu(fenmu);
this->setFenzi(fenzi);
}
//初始化分子
void setFenzi(string fenzi){
this->fenzi = fenzi;
}
//初始化分母
void setFenmu(string fenmu){
this->fenmu = fenmu;
}
//获取分子
string getFenzi(){
return this->fenzi;
}
//获取分母
string getFenmu(){
return this->fenmu;
}
//分数取反
void setOpposite(){
int flag = this->Compare2Zero();
//为0不需要置反，保持原样即可
//下面主要考虑负0的情况
if(flag != 0){
string fenzi = this->getFenzi();
if(flag == -1){//为负数时
fenzi = fenzi.erase(0,1); //去掉前面的符号
}else if(flag == 1){//为正数时
fenzi = "-"+fenzi;
}
this->setFenzi(fenzi);
}
}
//分数倒数
void setReciprocal(){
//0没有导数，不给予考虑
Fraction one,_one;
one.set("1/1");
_one.set("-1/1");
//分数为1或者-1时这一条件不成立时，直接不需要进行分子分母变换
if(!(this->Compare2Fraction(one) == 0 || this->Compare2Fraction(_one) == 0)){
string fenmu = this->getFenmu();
string fenzi = this->getFenzi();
this->set(fenzi,fenmu);
}
}
//按字符串返回分数
string result(){
string res = this->fenzi;
if(this->fenmu.compare("0") != 0){
if(this->fenmu.compare("1") != 0){
res = res+"/"+this->fenmu;
}
}
return res;
}
//这是比较两个正数之间大小的函数
int compare(string str1,string str2){
//相等返回0，大于返回1，小于返回-1
if(str1.size()>str2.size()){
return 1; //长度长的整数大于长度小的整数
}else if(str1.size()<str2.size()){
return -1;
}else{
return str1.compare(str2); //若长度相等，则头到尾按位比较
}
}
//计算两个数最大公约数
string gcd(string str1,string str2){
int sign = 1;
if(str1[0] == '-'){ // str1为负数，去除前导负号
sign *= -1; //标志位取相反数
str1 = str1.erase(0,1);
}
if(str2[0] == '-'){ // str2为负数，去除前导负号
sign *= -1; //标志位取相反数
str2 = str2.erase(0,1);
}
if(str1.compare("1") == 0 || str2.compare("1") == 0){ //str1或str2为1时
if(sign == -1){ //标志位位-1，str2加负号
return "-1";
}
return "1";
}else{ //str1和str2都不为1时，利用辗转相除法求最大公约数
string gcd;
while(str2.compare("0") != 0){
gcd = this->MOD_INT(str1,str2);
str1 = str2;
str2 = gcd;
}
gcd = str1;
if(sign == -1){
gcd = "-"+gcd;
}
return gcd;
}
}
//计算两个数最小公倍数
string gcm(string str1,string str2){
if(str1.compare("1") == 0 || str2.compare("1") == 0){
return "1";
}
if(str1.compare("-1") == 0 || str2.compare("-1") == 0){
return "-1";
}
string tmp1 = str1;
string tmp2 = str2;
string gcd = this->gcd(tmp1,tmp2); //计算最大公约数
string gcm = this->MUL_INT(str1,str2);
gcm = this->DIV_INT(gcm,gcd); //计算最小公倍数
return gcm;
}
//分数加法
Fraction ADD(Fraction num1,Fraction num2){
string fenmu,fenzi,gcd;
//num1分母不为0，num1分子为0，直接返回num2
if(num1.fenmu.compare("0") != 0 && num1.fenzi.compare("0") == 0){
return num2;
}
//num1分母不为0，num2分子为0，直接返回num1
if(num2.fenmu.compare("0") != 0 && num2.fenzi.compare("0") == 0){
return num1;
}
if(num1.fenmu.compare(num2.fenmu) == 0){//两个分母相等
fenmu = num1.fenmu; //保留分母
fenzi = this->ADD_INT(num1.fenzi,num2.fenzi); //计算分子
gcd = this->gcd(fenmu,fenzi); //计算最大公约数
if(gcd.compare("1") != 0){ //最大公约数不为1时，需要进行约分
fenmu = this->DIV_INT(fenmu,gcd); //约分后的分母
fenzi = this->DIV_INT(fenzi,gcd); //约分后的分子
}
}else{//分母不相等
string fenzi1 = this->MUL_INT(num1.fenzi,num2.fenmu); //计算通分后的分子1
string fenzi2 = this->MUL_INT(num2.fenzi,num1.fenmu); //计算通分后的分子2
fenzi = this->ADD_INT(fenzi1,fenzi2); //计算分子
fenmu = this->MUL_INT(num1.fenmu,num2.fenmu); //计算分母
gcd = this->gcd(fenmu,fenzi); //计算分子和分母的最大公约数
if(gcd.compare("1") != 0){ //最大公约数不为1时，需要进行约分
fenmu = this->DIV_INT(fenmu,gcd); //计算通分后的分母
fenzi = this->DIV_INT(fenzi,gcd); //计算通分后的分子
}
}
Fraction result;
result.set(fenmu,fenzi);
return result;
}
//分数减法
Fraction SUB(Fraction num1,Fraction num2){
//num1为0时，返回num2的相反数
if(num1.fenmu.compare("0") != 0 && num1.fenzi.compare("0") == 0){
num2.setOpposite();
return num2;
}
//num2为0时，返回num1
if(num2.fenmu.compare("0") != 0 && num2.fenzi.compare("0") == 0){
return num1;
}
string fenmu,fenzi,gcd;
if(num1.fenmu.compare(num2.fenmu) == 0){//两个分母相等
fenmu = num1.getFenmu(); //保留分母
fenzi = this->SUB_INT(num1.getFenzi(),num2.getFenzi()); //计算分子
gcd = this->gcd(fenmu,fenzi); //计算最大公约数
if(gcd.compare("1") != 0){ //最大公约数不为1时，需要进行约分
fenmu = this->DIV_INT(fenmu,gcd); //约分后的分母
fenzi = this->DIV_INT(fenzi,gcd); //约分后的分子
}
}else{//分母不相等
string fenzi1 = this->MUL_INT(num1.fenzi,num2.fenmu); //计算通分后的分子1
string fenzi2 = this->MUL_INT(num2.fenzi,num1.fenmu); //计算通分后的分子2
fenzi = this->SUB_INT(fenzi1,fenzi2); //计算分子
fenmu = this->MUL_INT(num1.fenmu,num2.fenmu); //计算分母
gcd = this->gcd(fenmu,fenzi); //计算分子和分母的最大公约数
if(gcd.compare("1") != 0){ //最大公约数不为1时，需要进行约分
fenmu = this->DIV_INT(fenmu,gcd); //计算通分后的分母
fenzi = this->DIV_INT(fenzi,gcd); //计算通分后的分子
}
}
Fraction result;
result.set(fenmu,fenzi);
return result;
}
//分数乘法
Fraction MUL(Fraction num1,Fraction num2){
string fenmu,fenzi;
//两个分母至少有一个0时，直接返回无穷大("9999999/1")
if(num1.fenmu.compare("0") == 0|| num2.fenmu.compare("0") == 0){
Fraction result;
result.set("9999999/1");
return result;
}
//两个分子至少有一个0时，直接返回0
if(num1.fenzi.compare("0") == 0|| num2.fenzi.compare("0") == 0){ //分子出现0时，直接返回0
Fraction result;
result.set("0/1");
return result;
}
//计算分母
if(num1.fenmu.compare("1") == 0 && num2.fenmu.compare("1") == 0){ //两个分母全为1
fenmu = "1";
}else if(num1.fenmu.compare("1") == 0 && num2.fenmu.compare("1") != 0){ //num1分母为1
fenmu = num2.fenmu;
}else if(num1.fenmu.compare("1") != 0 && num2.fenmu.compare("1") == 0){ //num2分母为1
fenmu = num1.fenmu;
}else{ //两个分母都不为1
fenmu = this->MUL_INT(num1.fenmu,num2.fenmu);
}
//计算分子
if(num1.fenzi.compare("1") == 0 && num2.fenzi.compare("1") == 0){ //两个分子全为1
fenzi = "1";
}else if(num1.fenzi.compare("1") == 0 && num2.fenzi.compare("1") != 0){ //num1分子为1
fenzi = num2.fenzi;
}else if(num1.fenzi.compare("1") != 0 && num2.fenzi.compare("1") == 0){ //num2分子为1
fenzi = num1.fenzi;
}else{ //两个分子都不为1
fenzi = this->MUL_INT(num1.fenzi,num2.fenzi);
}
//分母都不为1,且分子不为0时可能需要进行约分
if(fenmu.compare("1") != 0 && fenzi.compare("1") != 0){
string gcd = this->gcd(fenmu,fenzi);
if(gcd.compare("1") != 0){ //最大公约数不为1时，需要进行约分
fenmu = this->DIV_INT(fenmu,gcd); //计算通分后的分母
fenzi = this->DIV_INT(fenzi,gcd); //计算通分后的分子
}
}
Fraction result;
result.set(fenmu,fenzi);
return result;
}
//分数除法
Fraction DIV(Fraction num1,Fraction num2){
// num1为0时
if(num1.fenmu.compare("0") != 0 && num1.fenzi.compare("0") == 0){
Fraction result;
result.set("0/1");
return result;
}
//num2为1时
if(num2.fenmu.compare("1") == 0 && num2.fenzi.compare("1") == 0){
return num1;
}
//num2为0时，我们将结果初始化为"9999999/1"
if(num2.fenmu.compare("1") == 0 && num2.fenzi.compare("0") == 0){
Fraction result;
result.set("9999999/1");
return result;
}
Fraction tmp;
string fenmu = num2.getFenmu();
string fenzi = num2.getFenzi();
tmp.set(fenmu,fenzi);
tmp.setReciprocal(); //计算导数
//除法转化为乘法
return tmp.MUL(num1,tmp);
}
//整数加法
string ADD_INT(string str1,string str2){
//str1为0，返回str2
if(str1.compare("0") == 0){
return str2;
}
//str2为0，返回str1
if(str2.compare("0") == 0){
return str1;
}
//高精度加法
int sign=1; //sign 为符号位
string str;
if(str1[0]=='-'){ //str1为负数
if (str2[0]=='-'){ //str2为负数
sign=-1; //-1代表两个负数相加
// 去掉两个符号后相加
str=ADD_INT(str1.erase(0,1),str2.erase(0,1));
}else{//str2为正数
//去掉str1的符号，转化为减法
str=SUB_INT(str2,str1.erase(0,1));
}
}else{ // str1为正数
if(str2[0]=='-'){ //str2为负数
// 去掉str2的负数，转化为减法
str=SUB_INT(str1,str2.erase(0,1));
}else{ //str2为正数
//把两个整数对齐，短整数前面加0补齐
string::size_type L1,L2;
int i;
L1=str1.size();
L2=str2.size();
if(L1<L2){ // str1的长度比str2小，str1在前补充0
for(i=1;i<=L2-L1;i++){
str1="0"+str1;
}
}else{ // str2的长度比str2小，str2在前面补充0
for(i=1;i<=L1-L2;i++){
str2="0"+str2;
}
}
int int1=0,int2=0; //int2 记录进位，int1记录结果
for(i=str1.size()-1;i>=0;i--){
int1=(int(str1[i])-'0'+int(str2[i])-'0'+int2)%10;
int2=(int(str1[i])-'0'+int(str2[i])-'0'+int2)/10;
str=char(int1+'0')+str;
}
if(int2!=0){ //计算结束后还有进位，直接在前面补充
str=char(int2+'0')+str;
}
}
}
//运算后处理符号位
if((sign==-1)&&(str[0]!='0')){
str="-"+str;
}
return str;
}
//整数减法
string SUB_INT(string str1,string str2){
//str1为0，返回str2
if(str1.compare("0") == 0){
//str2为正数
if(str2.compare("0") == 1){
return "-"+str2;
}else if(str2.compare("0") == 0){
return "0";
}else{
return str2.erase(0,1);
}
}
//str2为0，返回str1
if(str2.compare("0") == 0){
return str1;
}
//高精度减法
int sign=1; //sign为符号位
string str;
int i,j;
if(str2[0]=='-'){ //str2为负数
// 去掉str2的符号，转化为加法
str=ADD_INT(str1,str2.erase(0,1));
}else{ // str2为正数
if(str1[0] == '-'){ //str1为负数，转化为加法
str = ADD_INT(str1.erase(0,1),str2);
str = "-"+str;
}else{ //str1为正数
// 判断str1和str2大小
int res=compare(str1,str2);
//cout<<"==="<<res<<endl;
if(res==0){ //str1和str2相等
return "0";
}
if(res<0){ //str1小于str2
sign=-1; //标志位置为-1
// str1和str2互换
string temp =str1;
str1=str2;
str2=temp;
}
string::size_type tempint;
tempint=str1.size()-str2.size();
// 按值较小者的进行遍历，tempint=0说明长度相等，大于0则str1长度大于str2
// 从最后一位开始遍历
for(i=str2.size()-1;i>=0;i--){
// str1的对应为小于str2的对应位
if(str1[i+tempint]<str2[i]){
j=1; //偏移位
//开始循环，开始寻找借位
while(1){
//前面的位为0，借1置成9
if(str1[i+tempint-j]=='0'){
str1[i+tempint-j]='9';
j++;
}else{//前面的位为0，借1，当前位减1
str1[i+tempint-j]=char(int(str1[i+tempint-j])-1);
break;
}
}
str=char(str1[i+tempint]-str2[i]+':')+str;
}else{
str=char(str1[i+tempint]-str2[i]+'0')+str;
}
}
//把多余为进行向前补充
for(i=tempint-1;i>=0;i--){
str=str1[i]+str;
}
}
}
//去除结果中多余的前导0
str.erase(0,str.find_first_not_of('0'));
if(str.empty()){
str="0";
}
if((sign==-1) && (str[0]!='0')){
str ="-"+str;
}
return str;
}
//整数乘法
string MUL_INT(string str1,string str2){
//str1和str2至少存在1个0，直接返回0
if(str1.compare("0") == 0 || str2.compare("0") == 0){
return "0";
}
//str1为1直接返回str2
if(str1.compare("1") == 0){
return str2;
}
//str2为1直接返回str1
if(str2.compare("1") == 0){
return str1;
}
//str1为-1
if(str1.compare("-1") == 0){
//str2为负数
if(str2.compare("0") < 0){
return str2.erase(0,1);
}else{
//str2为正数
return "-"+str2;
}
}
//str2为1
if(str2.compare("-1") == 0){
//str1为负数
if(str1.compare("0") < 0){
return str1.erase(0,1);
}else{
//str1为正数
return "-"+str1;
}
}
//高精度乘法
int sign=1; //sign 为符号位
string str;
// str1为负数
if(str1[0]=='-'){
sign*=-1; // 标志位乘-1
str1 =str1.erase(0,1); // 去掉负号
}
// str2为负数
if(str2[0]=='-'){
sign*=-1; // 标志位乘-1
str2 =str2.erase(0,1); // 去掉负号
}
int i,j;
string::size_type L1,L2;
L1=str1.size();
L2=str2.size();
for(i=L2-1;i>=0;i--){ //模拟手工乘法竖式
string tempstr;
int int1=0,int2=0,int3=int(str2[i])-'0';
if(int3!=0){
// 下面的循环实现结果后端补0操作
for(j=1;j<=(int)(L2-1-i);j++){
tempstr="0"+tempstr;
}
for(j=L1-1;j>=0;j--){
// int1记录个位数，int记录十位数
int1=(int3*(int(str1[j])-'0')+int2)%10;
int2=(int3*(int(str1[j])-'0')+int2)/10;
tempstr=char(int1+'0')+tempstr;
}
if(int2!=0){
tempstr=char(int2+'0')+tempstr;
}
}
// 当前结果和tempstr向将
str=ADD_INT(str,tempstr);
}
//去除结果中的前导0
str.erase(0,str.find_first_not_of('0'));
if(str.empty()){
str="0";
}
if((sign==-1) && (str[0]!='0')){
str="-"+str;
}
return str;
}
//整数除法
string DIVIDE_INT(string str1,string str2,int flag){
//高精度除法。flag==1时,返回商; flag==0时,返回余数
string quotient,residue; //定义商和余数
int sign1=1,sign2=1;
if(str2 == "0"){ //判断除数是否为0
quotient= "ERROR!";
residue = "ERROR!";
if(flag==1){
return quotient;
}else{
return residue;
}
}
//判断被除数是否为0
if(str1=="0"){
quotient="0";
residue ="0";
if(flag == 1){
return quotient;
}else{
return residue;
}
}
//被除数为1，直接返回str1
if(str2 == "1"){
quotient = str1;
residue = "0";
if(flag == 1){
return quotient;
}else{
return residue;
}
}
//被除数为-1
if(str2 == "-1"){
if(str1.compare("0") < 0){
quotient = str1.erase(0,1);
}else{
quotient = "-"+str1;
}
residue = "0";
if(flag == 1){
return quotient;
}else{
return residue;
}
}
// str1为负数
if(str1[0]=='-'){
str1 = str1.erase(0,1); //去除前导0
sign1 *= -1;
sign2 = -1;
}
// str2为负数
if(str2[0]=='-'){
str2 = str2.erase(0,1); //去除前导0
sign1 *= -1;
}
//比较str1和str2的大小
int res=compare(str1,str2);
// str1小于str2
if(res<0){
// 商为0，余数为str1
quotient="0";
residue =str1;
}else if(res == 0){
// str1与str2相等,商为1，余数为0
quotient="1";
residue ="0";
}else{
// str1大于str2
string::size_type L1,L2;
L1=str1.size();
L2=str2.size();
string tempstr;
tempstr.append(str1,0,L2-1);
for(int i=L2-1;i<L1;i++){ //模拟手工除法竖式
tempstr=tempstr+str1[i];
//可能出现不够除的情况，那么必须把前导0去掉
tempstr.erase(0,tempstr.find_first_not_of('0'));
if(tempstr.empty()){
tempstr="0";
}
for(char ch='9';ch>='0';ch--){ //试商
string str;
str=str+ch;
if(compare(MUL_INT(str2,str),tempstr)<=0){
quotient=quotient+ch;
tempstr =SUB_INT(tempstr,MUL_INT(str2,str));
break;
}
}
}
residue=tempstr;
}
//去除结果中的前导0
quotient.erase(0,quotient.find_first_not_of('0'));
if(quotient.empty()){
quotient="0";
}
if((sign1==-1)&&(quotient[0]!='0')){
quotient="-"+quotient;
}
if((sign2==-1)&&(residue [0]!='0')){
residue ="-"+residue ;
}
if(flag==1){
return quotient;
}else{
return residue;
}
}
//整数除法，返回商
string DIV_INT(string str1,string str2){
//高精度除法,返回商
return DIVIDE_INT(str1,str2,1);
}
//整肃除法，返回余数
string MOD_INT(string str1,string str2){
//高精度除法,返回余数
return DIVIDE_INT(str1,str2,0);
}
//判断分数与0的大小
int Compare2Zero(){
int sign_fenzi = 1;
int sign_fenmu = 1;
int sign = 1; //记录是否分子含有负号
string fenzi = this->fenzi;
string fenmu = this->fenmu;
if(fenzi[0] == '-'){ //分子为负数时，改变标志位
sign_fenzi = -1;
fenzi = fenzi.erase(0,1);
}
if(fenmu[0] == '-'){ //分子为负数时，改变标志位
sign_fenmu = -1;
fenmu = fenmu.erase(0,1);
}
int ans_fenzi = this->compare(fenzi,"0"); //比较分子的绝对值与0的大小
int ans_fenmu = this->compare(fenmu,"0"); //比较分母的绝对值与0的大小
if(sign_fenzi == -1 && ans_fenzi == 1){
ans_fenzi = -1;
}
if(sign_fenmu == -1 && ans_fenmu == 1){
ans_fenmu = -1;
}
int flag;
if(ans_fenzi == 0 && ans_fenmu != 0){ //分子为0，分母不为0，返回0
flag = 0;
}
if(ans_fenzi*ans_fenmu > 0){ //分子分母同号，返回1
flag = 1;
}
if(ans_fenzi*ans_fenmu < 0){ //分子分母异号，返回-1
flag = -1;
}
return flag;
}
//两个分数之间的比较
int Compare2Fraction(Fraction fraction){
Fraction ans,tmp;
tmp.set(this->getFenmu(),this->getFenzi());
//减后的结果与0作对比就是两个分数之间的大小关系
ans = ans.SUB(tmp,fraction);
return ans.Compare2Zero(); //返回两个数之间差与0的大小比较结果
}
};
int main()
{
string s1,s2;
char ch;
while(cin>>s1>>ch>>s2){
Fraction num1;
num1.set(s1);
Fraction num2;
num2.set(s2);
Fraction res;
res.set("1/1");
switch(ch){
case '+':res=res.ADD(num1,num2);break;
case '-':res=res.SUB(num1,num2);break;
case '*':res=res.MUL(num1,num2);break;
case '/':res=res.DIV(num1,num2);break;
default : break;
}
cout<<res.result()<<endl;
}
return 0;
}
在这里插入图片描述
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录