董晓算法

算法学习

A01 高精度加法

Luogu P1601 A+B Problem(高精)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//加法逻辑的时候要先加当为,再处理进位t的数值,然后要注意长短数的加,用max,min
//还有,首先,要翻转数组来对低位操作
t=(a[i]+b[i]-'0'-'0'+t)/10;//特别是注意这里,不能直接t+
//即t+=(a[i]+b[i]-'0'-'0')/10;这样会导致前面的t累加后没有经过除10的操作
//然后wa代码:
#include<bits/stdc++.h>

using namespace std;

int main(){
string a,b;
cin>>a>>b;
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
int t=0;
string s;
int i=0;
for(i=0;i<min(a.size(),b.size());++i){
s+=to_string((a[i]+b[i]-'0'-'0'+t)%10);
t=(a[i]+b[i]-'0'-'0'+t)/10;
}
for(int j=i;j<max(a.size(),b.size());++j){
if(a.size()>b.size()){

s+=to_string((a[j]-'0'+t)%10);
t=(a[j]-'0'+t)/10;
}
else if(a.size()<b.size()){

s+=to_string((b[j]-'0'+t)%10);
t=(b[j]-'0'+t)/10;
}
}
if(t!=0)s+=to_string(t);
reverse(s.begin(),s.end());
cout<<s;
return 0;
}

//但是,上面我的做法还是有点复杂了,看董晓的做法是:
//他处理长短不一的时候是把两个数组int化,然后翻转的时候不足的高位直接由全局变量而补0了,此时找出两个的最大长度lm,然后以此为准,进位取余,无论如何最高位都不会受到影响,这简便了很多:

#include<bits/stdc++.h>

using namespace std;
int a[550],b[550],c[550];//感觉这个的缺陷就是范围是固定的,可以用vector
int la,lb,lc;

int main(){
string ma,mb;
cin>>ma>>mb;
la=ma.size();
lb=mb.size();
lc=max(la,lb);
for(int i=0;i<la;++i) a[i]=ma[la-i-1]-'0';
for(int i=0;i<lb;++i) b[i]=mb[lb-i-1]-'0';
int t=0;
for(int i=0;i<lc;++i){
c[i]=(a[i]+b[i]+t)%10;
t=(t+a[i]+b[i])/10;
}
if(t){

c[lc] = t;
lc++;

}
for(int i=lc-1;i>=0;--i){
cout<<c[i];
}
return 0;
}

A02 高精度减法

Luogu P2142 高精度减法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//这里董晓算法中是先搞个cmp来判断两个数的大小,然后把两个数换成大减小(负号特判)
//cmp是bool类型的函数,原理和strcmp有点像
bool cmp(int a[],int b[]){
if(la!=lb) return la<lb;//如果位数不等于,就直接比较
for(int i=la;i;--i){
if(a[i]!=b[i]) return a[i]<b[i];//位数相等就直接比较
}
return false;//防止-0情况的出现
}

//减法关键逻辑---if(a[i]<b[i]) a[i+1]--,a[i]+=10; c[i]=a[i]-b[i];//如果遇到位数小的减不过来了,就进一,此时i+1是上一位

//最后去0操作:while(c[lc]==0&&lc>1) lc--;注意每一位的这个


//wa代码:
#include<bits/stdc++.h>

using namespace std;
#define N 10100
int a[N],b[N],c[N];
int la,lb,lc;

bool cmp(int a[],int b[]){
if(la!=lb)return la<lb;
for(int i=la;i>0;--i){
if(a[i]!=b[i])return a[i]<b[i];
}
return false;
}

void sub(int a[],int b[],int c[]){
for(int i=1;i<=lc;++i){
if(a[i]<b[i]){
a[i+1]--;
a[i]+=10;

}
c[i]=a[i]-b[i];
}
while(c[lc]==0&&lc>1)lc--;
}
int main(){
string ma,mb;
cin>>ma>>mb;
la=ma.size();
lb=mb.size();
for(int i=1;i<=la;++i){
a[i]=ma[la-i]-'0';
}
for(int i=1;i<=lb;++i){
b[i]=mb[lb-i]-'0';
}
lc=max(la,lb);
if(cmp(a,b)){
cout<<"-";
swap(a,b);
}
sub(a,b,c);
for(int i=lc;i>0;--i){
cout<<c[i];
}
return 0;
}

A03 高精度乘法

Luogu P1303 A*B Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//这个是模拟手工乘法的过程,时间复杂度是o方

//模拟的竖式乘法算法,如下:
1 2 3
× 4 5
-------
1 5 (3×5)
1 0 (2×5, 左移一位)
0 5 (1×5, 左移两位)
-------
1 2 (3×4, 左移一位)
0 8 (2×4, 左移两位)
0 4 (1×4, 左移三位)
-------
5 5 3 5
//代码:
void mul(int a[],int b[],int c[]){
for(int i=1;i<=la;i++){
for(int j=1;j<=lb;++j){
c[i+j-1]+=a[i]*b[j]//存位,模拟上述的第一步
}
}
for(int i=1;i<lc;++i){
c[i+1]+=c[i]/10;
c[i]%=10;//这里是处理每一位的进位
}
while(c[lc]==0&&lc>1) lc--;去除前导0
}


//ac代码:
#include<bits/stdc++.h>

using namespace std;
int la,lb,lc;
int a[2020],b[2020],c[4000010];


int main(){
string ma,mb;
cin>>ma>>mb;
la=ma.size();
lb=mb.size();
lc=la+lb;
for(int i=1;i<=la;++i) a[i]=ma[la-i]-'0';
for(int i=1;i<=lb;++i) b[i]=mb[lb-i]-'0';
for(int i=1;i<=la;++i){
for(int j=1;j<=lb;++j){
c[i+j-1]+=a[i]*b[j];

}
}
for(int i=1;i<lc;++i){
c[i+1]+=c[i]/10;
c[i]%=10;
}
while(c[lc]==0 &&lc>1) lc--;
for(int i=lc;i>=1;--i){
cout<<c[i];
}
return 0;
}

A04 高精度除法

Luogu P1480 A/B Problem

1