Polaris6G's blog

Stay humble,stay hungry.

0%

蓝桥杯-1

Posted on Valine:

学习高精度计算

高精度的接收方法和存储方法

输入

  • 字符串方式
  • 循环加数组
1
2
3
4
5
6
7
8
void init(int a[]){
	string s;
	cin>>s;
	len = length(s);
	for(int i=0;i<len;i++){
		a[i]=s[len-i]-'0';//将数串s转换为数组a，并倒序存储 
	}
}//或直接用循环加数组方式输入出具

进位 借位

加法进位

1
2
c[i]=a[i]+b[i];
if(c[i]>=10){c[i]%=10;++c[i+1];}

算法描述如下：

1
2
3
4
5
6
7
8
9
10
int c[101];
void add(int a[],int b[])
{
	int i=0,x=0;
    while(i<=length(a)||i<=length(b))
	c[i]=a[i]+b[i]+x;
	x=c[i]/10;
    c[i]%=10;
    i++;
}

减法借位

1
2
if(a[i]<b[i]){--a[i+1];a[i]+=10;}
c[i]=a[i]-b[i];

算法描述如下：

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
#include<bits/stdc++.h>
using spacename std;

int main(){
    int a[256],b[256],c[256],lena,lenb,lenc,i;
    char n[256],n1[256],n2[256];
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
    printf("Input minuend:");gets(n1);//输入被减数
    printf("Input subtrahend:");gets(n2);//输入减数
    if(strlen(n1)<strlen(n2)||strlen(n1)==strlen(n2)&&strcmp(n1,n2)<0)//结果为负
    {
        strcpy(n,n1);
        strcpy(n1,n2);
        strcpy(n2,n);
        cout<<"-";
    }
    lena=strlen(n1);lenb=strlen(n2);
    for(i=0;i<=lena-1;i++)a[lena-i]=int(n1[i]-'0');//被减数放入a数组
    for(i=0;i<=lenb-1;i++)b[lenb-i]=int(n2[i]-'0');//减数放入b数组
    i=1;
    while(i<=lena||i<=lenb){
        if(a[i]<b[i]){
            --a[i+1];
            a[i]+=10;
        }
        c[i]=a[i]-b[i];
        i++;
    }
    lenc=i;
    while((c[lenc]==0)&&(lenc>1))lenc--;//最高位的0不输出
    for(i=lenc;i>=1;i--)cout<<c[i];
    cout<<endl;
    return 0;
}

乘法进位

1
2
3
c[i+j-1]=a[i]*a[j]+x+c[i+j-1];
x=c[i+j-1]/10;
c[i+j-1]%=10;

按位相除

高精除以低精

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//char a1[101]="12345";被除数
//int b = 3;除数
//a[100];存放数
//x=0;借位数
for(i=1;i<=lena;i++){
    c[i]=(x*10+a[i])/b;
    x=(x*10+a[i])%b;
}
lenc=1;//起始为0
while(c[lenc]==0&&lenc<lena)
    lenc++; //删除前导0
for(i=lenc;i<=lena;i++)
    cout<<c[i];
cout<<endl;

高精除以高精

用减法模拟出发，对被除数的每一位都减去除数见到当前位置的数字小于除数

栗子

回文数

若依个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称为回文数。

写一个程序，给定一个N（2<N<=10或N=16）进制数M，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输入“impossible”

输入样例

1
9 87

输出样例

1
6

算法分析

N进制算法：

  • 当前位规范由%10改为%n
  • 进位处理由/10改为/n
  • 其他运算规则不变

代码如下：

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 <bits/stdc++.h>
using namespace std;

int n,a[101],b[101],ans;

void init(int a[]){
	string s;
	cin>>n>>s;
	memset(a,0,sizeof(a));
	a[0] = s.length();
	for(int i=1;i<=a[0];i++){
		if(s[a[0]-i]>='0'&&s[a[0]-i]<='9')a[i]=s[a[0]-i]-'0';
		else a[i]=s[a[0]-i]-'A'+10;//将数串s转换为数组a，并倒序存储 
	}
}

void add(int a[]){
	for(int i=1;i<=a[0];i++)b[i]=a[a[0]-i+1];
	for(int i=1;i<=a[0];i++)a[i]+=b[i];
	for(int i=1;i<=a[0];i++){
		a[i+1]+=a[i]/n;
		a[i]%=n;
	}
	if(a[a[0]+1]>0)a[0]++;//修正新的a的位数(a+b)最多只能有一个进位 
}

bool check(int a[]){
	for(int i=1;i<=a[0];i++){
		if(a[i]!=a[a[0]-i+1])return false;
	}
	return true;
}

int main(){
	init(a);
	if(check(a)){
		cout<<0;return 0;
	}
	ans = 0;
	while(ans++<=30){
		add(a);
		if(check(a)){
			cout<<ans;
			return 0;
		}
	}
	cout<<"Impossible";
	return 0;
}

利用重载运算符进行高精度计算

定义

1
2
3
4
5
const int MAXN=4000;
str BIGNUM{
	int len,s[MAXN];
    BIGNUM(){len=1;memset(s,0,sizeof(s));}
}

BIGNUM x;有x.len=1,x.s中全部元素均为0

赋值=

1
2
3
4
5
6
7
8
9
10
11
12
BIGNUM operator = (const char* num){ //operator是关键字
    len = strlen(num);
    for(int i=0;i<len;++i)s[i]=num[len-i-1]-'0';
    return *this;
}

BIGNUM operator = (const int num){
    char a[MAXN];
    sprintf(a,"%d",num);
    *this = a;
    return *this;
}

初始化

1
2
BIGNUM(int num){*this=num;}//数值型初始化
BIGNUM(const char *num){*this=num;}//字符串初始化

输出<<

对<<的重载

1
2
3
4
5
ostream& operator << (ostream & out,const BIGNUM& x){
	for(int i=x.len-1;i>=0;--i)
		cout<<x.s[i];
	return out;
}

输入>>

对>>的重载

1
2
3
4
5
6
istream& operator >> (istream &in,BIGNUM &x){
	char num[MAXN];
    in>>num;
    x=num;
    return in;
}

运算 +，+=

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
BIGNUM operator + (const BIGNUM &a){
	BIGNUM c;//sum
    c.len=max(len,a.len)+1;//，默认两个数相加有进位
    for(int i=0,x=0;i<c.len;++i){
        c.s[i]=s[i]+a.s[i]+x;
        x=c.s[i]/10;
        c.s[i]=c.s[i]%10;
    }
    if(c.s[c.len-1])--c.len;//如果没有进位长度就减1
    return c;
}

BIGNUM operator += (const BIGNUM &a){
	*this = *this+a;
    return *this;
}

比较<, >, <=, >=, ==, !=

<

1
2
3
4
5
6
7
bool operator < (const BIGNUM &x)const{
    if(len!=x.len)return len<x.len;//注意不能有前导零
    for(int i=len-1;i>=0;--i){
        if(s[i]!=x.s[i])return s[i]<x.s[i];
    }
    return false;//全部都相等，说明小于不成立
}

其他：

1
2
3
4
5
bool operator > (const BIGNUM &x)const{return x<*this;}
bool operator <= (const BIGNUM &x)const{return !(*this>x);}
bool operator >= (const BIGNUM &x)const{return !(*this<x);}
bool operator == (const BIGNUM &x)const{return !(x<*this||*this<x);}
bool operator != (const BIGNUM &x)const{return x<*this||*this<x;}

实例

计算10000以内n的阶乘（0<=n<=10000）

输入：整数n 输出：一行，即n!的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n,x,len=1;//x进位 
	int a[40010]; 
	cin>>n;
	a[1]=1;
	for(int i=1;i<=n;i++){
		x=0;
		for(int j=1;j<=len;j++){
			a[j]=a[j]*i+x;
			x=a[j]/10;
			a[j]%=10;
			if(x!=0&&j==len)len++;
		}
	}
	for(int i=len;i>=1;i--)cout<<a[i];
	return 0; 
}