高精度的实现及递归的结合
前置知识点：
1 如何向字符串类型数据里中添加单个字符
例如:字符串str string str="234"
在他的前面添加字符‘1’使之变成“1234”的方法
str=char(1+'0')+str;
或者 str =‘1’+str；
2 string函数的应用
#include<bits/stdc++.h>
using namespace std;
int main()
{
string str="abcdefab";
1. cout<<str.find_first_not_of('h')<<endl;
//第二个参数为0,默认从原串下标为0开始查找。第一个a就和带查字符不同，故输出a的下标0。
2. cout<<str.find_first_not_of("twj",1)<<endl;
//从下标为1开始查，第一个b就和待查子串任一字符不同，故输出b的下标1。
3. cout<<str.find_first_not_of("wbj",1)<<endl;
//从下标为1开始，第一个b与待查子串中的b一样，故b不符合，继续c再和子串任一字符比较，结果都不同，故输出c的下标2。
4.cout<<str.find_first_not_of("abcdefg")<<endl;
//原串任一字符都出现在子串中，故找不到，返回npos。
5.cout<<str.find_last_not_of('h')<<endl;
//第二个参数为0，默认从npos逆向查。原串倒数第一个字符b和h就不同，故输出b的小标7。
6.cout<<str.find_last_not_of("ab",6)<<endl;
//从原串下标为6开始逆向查询，第一个a和待查串中的字符a相同，不符合，故继续逆向比较。f和待查子串任一字符不同，故输出f的下标5。
7.cout<<str.find_last_not_of("abcdefhu")<<endl;
//原串任一字符都出现在子串中，故找不到，返回npos。
return 0;
}
//有效的下标应该在0~len-1范围内。len=str.size();
高精度的实现的三种形式
- 字符串数据类型
- 结构体数据类型
第一种字符串数据类型
#include<bits/stdc++.h>
using namespace std;
//比较大小**
int compare(string s1,string s2)
{
if(s1.length()>s2.length())return 1;
else if(s1.length()<s2.length())return -1;
else return s1.compare(s2);
}//加法**
string add(string s1,string s2)
{
string s3;
int len1=s1.length();
int len2=s2.length();
if(len1<len2)
{
for(int i=1;i<=len2-len1;i++)
{
s1="0"+s1;
}
}
else {
for(int i=1;i<=len1-len2;i++)
{
s2="0"+s2;
}
}
len1=s1.length();
int carry=0;
int temp;
for(int i=len1-1;i>=0;i--)
{
temp=s1[i]-'0'+s2[i]-'0'+carry;
carry=temp/10;
temp%=10;
s3=char(temp+'0')+s3;
}
if(carry!=0)s3=char(carry+'0')+s3;
return s3;
}
//s1>s2(减法)
string sub(string s1,string s2)
{
string s3;
int tmp=s1.length()-s2.length();
int carry=0;
for(int i=s2.length()-1;i>=0;i--)
{
if(s1[tmp+i]<s2[i]+carry)
{
s3=char(s1[tmp+i]-s2[i]-carry+'0'+10)+s3;
carry=1;
}
else {
s3=char(s1[tmp+i]-s2[i]-carry+'0')+s3;
carry=0;
}
}
for(int i=tmp-1;i>=0;i--)
{
if(s1[i]-carry>='0')
{
s3=char(s1[i]-carry)+s3;
carry=0;
}
else {
s3=char(s1[i]-carry+10)+s3;
carry=1;
}
}
s3.erase(0,s3.find_first_not_of('0'));
//s3.erase(0,s3.find_first_not_of('0'));
return s3;
}
//(乘法）
string mul(string s1,string s2)
{
string s3;
int len1=s1.length();
int len2=s2.length();
string tempstr;
for(int i=len2-1;i>=0;i--)
{
tempstr="";
int temp=s2[i]-'0';
int t=0;
int carry=0;
if(temp!=0)
{
for(int j=1;j<=len2-1-i;j++)
tempstr+="0";
for(int j=len1-1;j>=0;j--)
{
t=(temp*(s1[j]-'0')+carry)%10;
carry=(temp*(s1[j]-'0')+carry)/10;
tempstr=char(t+'0')+tempstr;
}
if(carry!=0) tempstr=char(carry+'0')+tempstr;
}
s3=add(s3,tempstr);
}
s3.erase(0,s3.find_first_not_of('0'));
return s3;
}
//高精度除法(未掌握)
//两个正数相除，商为quotient,余数为residue
//需要高精度减法和乘法
void div(string s1,string s2,string "ient,string &residue)
{
quotient=residue="";//清空
if(s2=="0")//判断除数是否为0
{
quotient=residue="ERROR";
return;
}
if(s1=="0")//判断被除数是否为0
{
quotient=residue="0";
return;
}
int res=compare(s1,s2);
if(res<0)
{
quotient="0";
residue=s1;
return;
}
else if(res==0)
{
quotient="1";
residue="0";
return;
}
else
{
int len1=s1.length();
int len2=s2.length();
string tempstr;
tempstr.append(s1,0,len2-1);
for(int i=len2-1;i<len1;i++)
{
tempstr=tempstr+s1[i];
tempstr.erase(0,tempstr.find_first_not_of('0'));
if(tempstr.empty())
tempstr="0";
for(char ch='9';ch>='0';ch--)//试商
{
string str,tmp;
str=str+ch;
tmp=mul(s2,str);
if(compare(tmp,tempstr)<=0)//试商成功
{
quotient=quotient+ch;
tempstr=sub(tempstr,tmp);
break;
}
}
}
residue=tempstr;
}
quotient.erase(0,quotient.find_first_not_of('0'));
if(quotient.empty()) quotient="0";
}第二种 结构体数据类型
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4;
//构建结构体
struct bign{
int d[maxn];
int len;
bign(){
memset(d,0,sizeof(d));
len=0;
}
};
//数据转化
bign charge(char str[])
{
bign a;
a.len=strlen(str);
for(int i=0;i<a.len;i++)
{
a.d[i]=str[a.len-i-1]-'0';
}
return a;
}
//比较大小
int compare(bign a,bign b)
{
if(a.len<b.len)return 1;
else if(a.len<b.len)return -1;
else {
for(int i=a.len-1;i>=0;i--)
{
if(a.d[i]>b.d[i])return 1;
else if(a.d[i]<b.d[i])return -1;
}
return 0;
}
}
//加法
bign add(bign a,bign b)
{
bign c;
int carry=0;
for(int i=0;i<a.len||i<b.len;i++)
{
int temp=a.d[i]+b.d[i]+carry;
c.d[c.len++]=temp%10;
carry=temp/10;
}
if(carry!=0)
{
c.d[c.len++]=carry;
}
return c;
}
//减法
bign sub(bign a,bign b)
{
bign c;
for(int i=0;i<a.len||i<b.len;i++)
{
if(a.d[i]<b.d[i]);
{
a.d[i+1]--;
a.d[i]+=10;
}
c.d[c.len++]=a.d[i]-b.d[i];
}
while(c.len-1>=1&&c.d[c.len-1]==0)
{
c.len--;
}
return c;
}
//乘法
bign multi1(bign a,bign b)
{
bign c;
int carry=0;
for(int i=0;i<a.len;i++)
{
int temp=a.d[i]*b.d[i];
c.d[c.len++]=temp%10;
carry=temp/10;
}
while(carry!=0)
{
c.d[c.len++]=carry%10;
carry/=10;
}
return c;
}
//输出
void print(bign a)
{
for(int i=a.len-1;i>=0;i--)
{
printf("%d",a.d[i]);
}
}
高精度的具体应用
（1）与递推的结合
参考博客；C++string中find_first_not_of()函数和find_last_not_of()函数
同程旅行工作强度 20人发布