信息学奥赛一本通 高精度计算


阅读数: 次   
字数统计: 2.8k字   |   阅读时长: 16分

信息学奥赛一本通 基础算法
解决大整形数字加减问题。
已有高精度加法，高精度减法，高精度乘法（存储数组每个位置存储1位）（存储数组每个位置存储多位）
高精度除法 回文数

高精度加法

重新写了一遍简洁一点儿的

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
#include<iostream>
#include<cstring> 
using namespace std;
void init(int a[])
{
	string s;
	cin>>s;
	a[0]=s.length();
	for(int i=1;i<=a[0];i++)
		a[i]=s[a[0]-i]-'0';
}
void add(int a[],int b[],int s[])
{
	s[0]=a[0]>b[0]?a[0]+1:b[0]+1;
	for(int i=1;i<=s[0];i++)
		s[i]=s[i]+a[i]+b[i];
	for(int i=1;i<=s[0];i++)
		if(s[i]>=10)
		{
			s[i+1]+=s[i]/10;
			s[i]%=10;
		}
}
void print(int a[])
{
	while(a[0]>0&&a[a[0]]==0)
		a[0]--;
	for(int i=a[0];i>=1;i--)
		cout<<a[i];
}
int main()
{
	int a[10000],b[10000],sum[10000];
	init(a);
	init(b);
	add(a,b,sum);
	print(sum);
	return 0;
}

下面是原来写的

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
#include<iostream>
#include<string>
using namespace std;
int maxlen=0;
void init(int a[])                              //输入函数init()，倒序储存
{
	string s;
	int slen; 
	cin>>s;
	if(s.length()>maxlen)
	{
		maxlen=s.length();
	}
	slen=s.length();
	for(int i=1;i<=slen;i++)
	{
		a[i]=s[slen-i]-'0';
	}
}
void add(int num1[],int num2[],int len)         //两个数组每一位对应相加
{
	int sum[100]={0};
    int sumlen=l;
	for(int i=1;i<=l;i++)
	{
		if(num1[i]+num2[i]+sum[i]>=10)          //进位
		{
			sum[i+1]++;
			sum[i]=(num1[i]+num2[i]+sum[i])%10;
			if(i==len)
			{
				sumlen++;
			}
		}
		else
		{
			sum[i]=num1[i]+num2[i]+sum[i];
		}
	}
	for(int i=sumlen;i>=1;i--)
	{
		cout<<sum[i];
	}
}
int main()
{
	freopen("高精度加法2in.txt","r",stdin);
	freopen("高精度加法2out.txt","w",stdout);
	int num1[100]={0},num2[100]={0};
	init(num1);
	init(num2);
	add(num1,num2,maxlen);
	return 0;
}

高精度减法

写高精度除法的时候又写了一遍，发现差别还挺大的

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
73
74
75
76
77
#include<iostream>
#include<string>
using namespace std;

int check(int a[],int b[])
{
	if(a[0]>b[0])
		return 1;
	else if(a[0]<b[0])
		return -1;
	else 
	{
		for(int i=a[0];i>=1;i--)
		{
			if(a[i]>b[i])return 1;
			else if(a[i]<b[i])return -1;
		}
	}
	return 0;
}

void init(int a[])
{
	string s;
	cin>>s;
	for(int i=1;i<=s.length();i++)
		a[i]=s[s.length()-i]-'0';
	a[0]=s.length();
}

void sub(int a[],int b[])
{
	for(int i=1;i<=a[0];i++)
	{
		if(a[i]>=b[i])
			a[i]=a[i]-b[i];
		else 
		{
			a[i]=a[i]-b[i]+10;
			a[i+1]--;
		}
	}
}

void print(int a[])
{
	while(a[a[0]]==0)
			a[0]--;
	for(int i=a[0];i>=1;i--)
		cout<<a[i];
	cout<<endl;
	return;
}

int main()
{
	int a[100000],b[100000];bool k=0;
	init(a);
	init(b);
	if(check(a,b)==1)
	{
		sub(a,b);
		print(a);
	}
	else if(check(a,b)==-1)
	{
		sub(b,a);
		cout<<"-"; 
		print(b);
	}
	else 
	{
		cout<<0;
		return 0;
	}
	return 0;
}

下面是原来写的

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<string>
using namespace std;

int numlen[10];                                  //储存数字[1]或[2]的长度
int symbol=0;
int target[11000]={0};
int maxlen=0;

void init(int a[],int n)
{
	string s;
	cin>>s;
	if(maxlen<s.length())
	{
		maxlen=s.length();
	}
	numlen[n]=s.length();
	for(int i=1;i<=numlen[n];i++)
	{
		a[i]=s[numlen[n]-i]-'0';
	}
}

void sub(int num1[],int num2[])                  //数组对应相减函数，num1为大数，num2为小数
{
	for(int i=1;i<=maxlen;i++)
	{
		if(num1[i]-num2[i]<0)
		{
			num1[i+1]--;
			target[maxlen-i+1]=num1[i]+10-num2[i];
		}
		else
		{
			target[maxlen-i+1]=num1[i]-num2[i];  //结果正序存储在target数组里面，在已知maxlen的情况下方便输出
		}
	} 	
	int first=maxlen;
	for(int i=1;i<=maxlen;i++)
	{
		if(target[i]!=0)                         //找到第一个不为0的数的数组下标
		{
			first=i;
			break;
		}
	}
	for(int i=first;i<=maxlen;i++)
	{
		cout<<target[i];
	}
}

void judge(int num1[],int num2[])                //判断函数，判断num1和num2谁大（看位数多少或者位数相同时看高位大小）。
{
	if(numlen[1]>numlen[2])
	{
		symbol=0;
	}
	else if(numlen[1]<numlen[2])
	{
		symbol=1;
	}
	else
	{
		for(int i=maxlen;i>=1;i--)
		{
			if(num1[i]>num2[i])
			{
				symbol=0;
				break;
			}
			else if(num1[i]<num2[i])
			{
				symbol=1;
				break;
			}
		}
	}
}

int main()
{
	freopen("高精度减法in.txt","r",stdin);
	freopen("高精度减法out.txt","w",stdout);
	int num1[11000]={0},num2[11000]={0};
	init(num1,1);
	init(num2,2);
	judge(num1,num2);
	if(symbol==0)                               //num1大于num2
	{			
		sub(num1,num2);
	}
	else                                        //num1小于num2
	{
		cout<<"-";
		sub(num2,num1);
	}
	return 0;
}

高精度乘法

存储数组每个位置存1位数字

重写后的

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
#include<iostream>
#include<string>
using namespace std;

void init(int a[])
{
	string s;
	cin>>s;
	a[0]=s.length();
	for(int i=1;i<=a[0];i++)
		a[i]=s[a[0]-i]-'0';
}

void print(int a[])
{
	while(a[0]>0&&a[a[0]]==0)a[0]--;
	for(int i=a[0];i>=1;i--)
		cout<<a[i];
}

void mul(int a[],int b[],int s[])
{
	s[0]=a[0]+b[0];
	for(int i=1;i<=a[0];i++)
	{
		for(int j=1;j<=b[0];j++)
		{
			s[i+j-1]+=a[i]*b[j];
		}
	}
	for(int i=1;i<=s[0];i++)
	{
		if(s[i]>=10)
		{
			s[i+1]+=s[i]/10;
			s[i]%=10;
		}
	}
}

int main()
{
	int a[10000],b[10000],s[10000];
	init(a);
	init(b);
	mul(a,b,s);
	print(s);
	return 0;
 }

之前的

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
#include<iostream>
#include<string>
using namespace std;
int target[1000100]={},len[3]={};

void init(int a[],int n)
{
	string s;
	int slen; 
	cin>>s;
	slen=s.length();
	int i=1;
	for(;i<=slen;i++)
	{
		a[i]=s[slen-i]-'0';
	}
	len[n-1]=slen;
}

void mul(int a[],int b[])
{
	for(int i=1;i<=len[0];i++)
	{
		for(int j=1;j<=len[1];j++)
		{
			target[i+j-1]=target[i+j-1]+a[i]*b[j];
		}
	}
	for(int i=1;i<=len[0]+len[1];i++)
	{
		if(target[i]>=10)
		{
			target[i+1]+=target[i]/10;
			target[i]%=10;
		}
	}
} 

int main()
{
	int num1[1010],num2[1010];
	init(num1,1);
	init(num2,2);
	len[2]=len[0]+len[1];
	mul(num1,num2);
	while(target[len[2]]==0&&len[2]>1)
	len[2]--;
	for(int i=len[2];i>=1;i--)
	{
		cout<<target[i];
	}
	return 0;
}

存储数组每个位置存多位数字

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
73
#include<iostream>
#include<string>
using namespace std;
int target[10001]={0};
int num1[101]={0},num2[101]={0};
void init(int a[])
{
	string s;
	cin>>s;
	int i=1;
	for(;3*(i-1)<=s.length();i++)
	{
		for(int j=1;j<=3&&((i-1)*3+j)<=s.length();j++)
		{
			if(s.length()-(i-1)*3>3)
			a[i]=a[i]*10+s[s.length()-(i-1)*3+j-4]-'0';  
			else
			a[i]=a[i]*10+s[j-1]-'0';
		}
	}
	if(s.length()%3==0)
	a[0]=i-2;
	else
	a[0]=i-1;
}

void mul(int a[],int b[])
{
	for(int i=1;i<=a[0];i++)
	{
		for(int j=1;j<=b[0];j++)
		{
			
			target[i+j-1]=target[i+j-1]+a[i]*b[j];
		}
	}
	for(int i=1;i<=a[0]+b[0];i++)
	{
		if(target[i]>=1000)
		{
			target[i+1]+=target[i]/1000;
			target[i]%=1000;
		}
	}
} 

int main()
{
	
	init(num1);
	init(num2);
	target[0]=num1[0]+num2[0];
	mul(num1,num2);
	while(target[target[0]]==0&&target[0]>1)
	target[0]--;
	for(int i=target[0];i>=1;i--)
	{

		if(target[i]>=100||i==target[0])
		{
			cout<<target[i];
		}
		else if(target[i]>=10)
		{
			cout<<"0"<<target[i];
		}
		else 
		{
			cout<<"00"<<target[i];
		}
	}
	return 0;
}

高精度除法

高精除低精

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
#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s1;
	cin>>s1;
	int s2,s3[s1.length()];
	cin>>s2;
	int x=0;
	for(int i=0;i<s1.length();i++)
	{
		x=x*10+int(s1[i])-48;
		s3[i]=x/s2;
		x=x%s2;
	}
	int j=0,k=0;
	while(s3[j]==0)
	{
		j++;
	}
	for(;j<s1.length();j++)
	{
		k++;
		cout<<s3[j];
	}
	if(k==0)
		cout<<s3[j-1];
	return 0;
}

高精除高精

如果想要减少时间的话，还要像乘法那样做压位处理

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<iostream>
#include<cstring>
using namespace std;

void init(int a[])
{
	string s;
	cin>>s;
	for(int i=1;i<=s.length();i++)
		a[i]=s[s.length()-i]-'0';
	a[0]=s.length();
}

int check(int a[],int b[])
{
	if(a[0]>b[0])
		return 1;
	else if(a[0]<b[0])
		return -1;
	else 
	{
		for(int i=a[0];i>=1;i--)
		{
			if(a[i]>b[i])return 1;
			else if(a[i]<b[i])return -1;
		}
	}
	return 0;
}

void sub(int a[],int b[])
{
	int flag=check(a,b);
	if(flag==1)
	{
		for(int i=1;i<=a[0];i++)
		{
			if(a[i]>=b[i])
				a[i]=a[i]-b[i];
			else 
			{
				a[i]=a[i]-b[i]+10;
				a[i+1]--;
			}
		}
	}
	else if(flag==0)
	{
		a[0]=0;
		return;
	}
	while(a[0]>0&&a[a[0]]==0)
		a[0]--;
	return;
}

void numcpy(int a[],int b[],int c)
{
	for(int i=1;i<=a[0];i++)
		b[c+i-1]=a[i];	
	b[0]=a[0]+c-1;
}

void div(int a[],int b[],int s[])
{
	int tmp[100001];
	s[0]=a[0]-b[0]+1;
	for(int i=s[0];i>0;i--)
	{
		memset(tmp,0,sizeof(tmp));
		numcpy(b,tmp,i);
		while(check(a,tmp)>=0)
		{
			s[i]++;
			sub(a,tmp);
		}
	}
	while(s[0]>0&&s[s[0]]==0) 
		s[0]--;	
}

void print(int a[])
{
	if(a[0]==0)
	{
		cout<<0<<endl;
		return; 
	}
	for(int i=a[0];i>=1;i--)
		cout<<a[i];
	cout<<endl;
	return;
}

int main()
{
	int a[100001]={0},b[100001]={0},s[100001]={0};
	init(a);
	init(b);
	div(a,b,s);
	print(s);
	//print(a);
	return 0;
}

回文数

链接
高精度+模拟

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<cstring>
using namespace std;

void init(int a[])
{
	string s;
	cin>>s;
	a[0]=s.length();
	for(int i=1;i<=a[0];i++)
	{
		if(s[a[0]-i]>=48&&s[a[0]-i]<=57)
			a[i]=s[a[0]-i]-'0';
		else
			a[i]=s[a[0]-i]-'A'+10;
	}
}

void print(int a[])
{
	while(a[0]>0&&a[a[0]]==0)
		a[0]--;
	for(int i=a[0];i>=1;i--)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}

bool check(int a[])
{
	for(int i=1;i<=a[0]/2;i++)
	{
		if(a[i]==a[a[0]-i+1])
			continue;
		else
			return 0;
	}
	return 1;
}

void numcpy(int a[],int b[])
{
	memset(a,0,sizeof(a));
	for(int i=0;i<=b[0];i++)
		a[i]=b[i];
}

void add(int a[],int s[],int k)
{
	for(int i=1;i<=a[0];i++)
	{
		s[i]=s[i]+a[i]+a[a[0]-i+1];
		
		if(i==a[0]&&s[i]>=k)
			s[0]=a[0]+1;
		else if(i==a[0])
			s[0]=a[0];
			
		if(s[i]>=k)
		{
			s[i+1]+=s[i]/k;
			s[i]%=k;
		}
	}
	
}

int main()
{ 	
	int n,s1[100001],s[100001],sy=0;
	cin>>n;
	init(s1);
	numcpy(s,s1);
	while(check(s)!=1&&sy<=30)
	{
		memset(s,0,sizeof(s));
		add(s1,s,n);
		sy++;
		numcpy(s1,s);
	}
	if(check(s)==1)
		cout<<"STEP="<<sy<<endl;
	else
		cout<<"Impossible!";
	return 0;
}


-------------本文结束感谢您的阅读-------------



赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码
本站总访问量次 本站访客数人次

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

朱登榜，来自河南郑州，河南大学学生，倘若文章有错误，望提醒修正，感谢！<br>qq:879322660<br>微信:z15981855791