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

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

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

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

項(xiàng)目要點(diǎn)

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

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

3.本人采用字符串進(jìn)行存儲(chǔ)，應(yīng)注意char的特點(diǎn)

比如：char a=161；

cout<<(int)a;

此時(shí)會(huì)輸出-95，而不是161，char類型首個(gè)比特位是作為正負(fù)號(hào)的

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

需要用到之前博客提到的減法運(yùn)算minus

核心思想：

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

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

比如861mod21=861%21

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

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

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

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

即得出861%21=0

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

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

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

因?yàn)閗 mod a<a,(-k) mod a<a

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

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

運(yùn)行截圖及代碼如下：

#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)//判斷兩個(gè)正數(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)//取模運(yùn)算
{
 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í)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: