C++使用string的大數(shù)取模運算（5）

更新時間：2019年09月18日 11:29:51 作者：好想告訴你wt

這篇文章主要為大家詳細介紹了C++使用string的大數(shù)取模運算，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本次項目目標(biāo)：使用C++完成對于大數(shù)的相關(guān)運算，具體有加減乘除取模。

項目要點

1.大數(shù)指的是遠超long long int的數(shù)據(jù)

2.將大數(shù)用矩陣進行存儲，并通過矩陣實現(xiàn)運算

3.本人采用字符串進行存儲，應(yīng)注意char的特點

比如：char a=161；

cout<<(int)a;

此時會輸出-95，而不是161，char類型首個比特位是作為正負號的

取模運算其實和取余差不多，主要是取模在負數(shù)方面與取余不同

需要用到之前博客提到的減法運算minus

核心思想：

先來看自然數(shù)的取模運算

與取余相同，與除法思路相同

比如861mod21=861%21

先用86去減21 知道數(shù)值小于21時停止也就是2

再添加上下一位，就變成了21

如果這個數(shù)大于等于21，則再用這個數(shù)減去它

21-21=0，當(dāng)已經(jīng)取出最后一位，而且這個數(shù)字小于21時停止

即得出861%21=0

接下來來看負整數(shù)的情況

假設(shè)有一個正整數(shù)k,a，(-k) mod a+k mod a=0 mod a

(-k) mod a=0 mod a - k mod a

因為k mod a<a,(-k) mod a<a

所以(-k) mod a=a - k mod a

即一個負整數(shù)的模a，就為a-其絕對值的模a

運行截圖及代碼如下：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define n 10
string dezero(string a)//用來去掉正數(shù)前面的0，也就是說可以輸入000001類似這樣的數(shù)字
{
 long int i;
 for(i=0;i<a.length();i++)
 {
 if(a.at(i)>48) break;
 }
 if(i==a.length()) return "0";
 a.erase(0,i);
 return a;
}
int judge(string a,string b)//判斷兩個正數(shù)的大小
{
 if(a.length()>b.length()) return 1;
 if(a.length()<b.length()) return -1;
 long int i;
 for(i=0;i<a.length();i++)
 {
 if(a.at(i)>b.at(i)) return 1;
 if(a.at(i)<b.at(i)) return -1;
 }
 return 0;
}
string minus(string a,string b)//自然數(shù)減法（在之前博客中寫到過，這里直接挪過來調(diào)用了）
{
 a=dezero(a);
 b=dezero(b);
 long int i,j=0;
 string c="0";
 string c1,c2;
 string d="-";
 if(judge(a,b)==0) return c;
 if(judge(a,b)==1)
 {
 c1=a;
 c2=b;
 }
 if(judge(a,b)==-1)
 {
 c1=b;
 c2=a;
 j=-1;
 }
 reverse(c1.begin(),c1.end());
 reverse(c2.begin(),c2.end());
 for(i=0;i<c2.length();i++)
 {
 if(c2.at(i)>=48&&c2.at(i)<=57) c2.at(i)-=48;
 if(c2.at(i)>=97&&c2.at(i)<=122) c2.at(i)-=87;
 }
 for(i=0;i<c1.length();i++)
 {
 if(c1.at(i)>=48&&c1.at(i)<=57) c1.at(i)-=48;
 if(c1.at(i)>=97&&c1.at(i)<=122) c1.at(i)-=87;
 }
 for(i=0;i<c2.length();i++)
 {
 c1.at(i)=c1.at(i)-c2.at(i);
 }
 for(i=0;i<c1.length()-1;i++)
 {
 if(c1.at(i)<0)
 {
 c1.at(i)+=n;
 c1.at(i+1)--;
 }
 }
 for(i=c1.length()-1;i>=0;i--)
 {
 if(c1.at(i)>0) break;
 }
 c1.erase(i+1,c1.length());
 for(i=0;i<c1.length();i++)
 {
 if(c1.at(i)>=10) c1.at(i)+=87;
 if(c1.at(i)<10) c1.at(i)+=48;
 }
 reverse(c1.begin(),c1.end());
 if(j==-1) c1.insert(0,d);
 return c1;
}
string mod(string a,string b)//取模運算
{
 long int i,j=0;
 string c1,c2,c3,d;
 if(a.at(0)=='-') j=1;
 if(judge(a,b)==0) return "0";
 if(judge(a,b)==-1)
 {
 return a;
 }
 c1=dezero(a);
 c2=dezero(b);
 d="";
 for(i=0;i<c1.length();i++)
 {
 d=d+c1.at(i);
 while(judge(d,b)>=0)
 {
 d=minus(d,b);
 d=dezero(d);
 }
 }
 if(j==1) d=minus(b,d);
 return d;
}
int main()
{
 string a,b;
 while(cout<<"input:"&&cin>>a>>b)
 {
 cout<<"output:"<<mod(a,b)<<endl;
 }
 return 0;
}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: