Level3题解（1-10）

  2. 主页
  4. 文档
  6. Level3题解（1-10）
  8. 第1课 高精度计算

第1课 高精度计算

什么是高精度?

高精度算法，属于处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，我们可以将这个数字拆开，拆成一位一位的，或者是几位几位的存储到一个数组中， 用一个数组去表示一个数字，这样这个数字就被称为是高精度数。高精度算法就是能处理高精度数各种运算的算法，但又因其特殊性，故从普通数的算法中分离，自成一家。对于这类问题，不要指望long double这些东西了，基本数据类型不可能存的下。我们可以把这两个数当成字符串输入到数组中，然后模拟手动的竖式运算得出结果。

重点：
高精度数的读入与输出
高精度数的加减乘除
进一步熟悉函数的使用（模块化编程的思想）
难点：
高精度数的除法
高精度计算的优化
为什么要用到高精度计算？
int
long long
double
等进行计算的精度只有十几位，如果要进行数十、百、千、万位的数的计算就要用到高精度计算

高精度计算的基本方法
用字符串来读入数据：将字符串转为整数数组，该数组的每一个元素对应一位十进制数，下标顺序指明每一位的序号（为了计算对位的方便，一般会进行倒序存储），一般还用其下标0来存储该数的位数，如a[0]，也是为了方便计算和输出等。
然后对每一位进行计算，运算规则如同算术运算。
输出的时候一般也是倒序（因为存储的时候是倒序的）。

高精度存储

一般用int数组倒着存放高精度的数.
为什么?

  • 比较容易实现减法, 低位自动对齐, 高位默认都是0
  • 这样比较方便处理进位的问题.

数组的第一位用于存放有效数字的长度.

void convert(char ca[], int a[])
{
    int len = strlen(ca);
	for(int i = 1; i <= len; i++) {
		a[i] = ca[len - i] - '0';
	}
	a[0] = len;
}

高精度输出:

void print(int ans[])
{
    for(int i = ans[0]; i >=1; i--)
        printf("%d", ans[i]);
}

高精度比较大小

  1. 比较两个数的长度，长度更长的数越大。
  2. 如果两个数长度相等，那么就从高位到低位一位一位比较，如果某一位数字不同时，较大的数大。否则继续比较下一位。
  3. 如果比到最后都没有比出谁大谁小，就说明这两个数一样大。
// 1 代表大于,  -1 代表小于, 0 代表相等.
int compare(int a[], int b[])
{
    int lena = a[0];
    int lenb = b[0];
    
    if(lena > lenb) return 1;
    if(lenb > lena) return -1;
    
    //从高位开始比较 
    for(int i = lena; i >=1; i--)
    {
        if(a[i] > b[i]) return 1;
        if(a[i] < b[i]) return -1;
    }
    
    return 0; //a==b
}

//字符串比较
bool compare(char *p1, char *p2)
{
	int l1= strlen(p1);
	int l2= strlen(p2);
	
	if(l1 > l2)
		return true;
	if(l1 < l2)
		return false;
	
	if(strcmp(p1, p2) > 0)
		return true;
	else
		return false;
}

例题 P1781 宇宙总统

#include <bits/stdc++.h>
using namespace std;

char p[108];
char maxp[108];
int m;
int maxid;

bool compare(char *p1, char *p2)
{
	int l1= strlen(p1);
	int l2= strlen(p2);
	if(l1 > l2)
		return true;
	if(l1 < l2)
		return false;
	
	if(strcmp(p1, p2) > 0)
		return true;
	else
		return false;
}

int main()
{
	scanf("%d", &m);
	for(int i = 1; i <=m; i++) {
		scanf("%s", p);
		if(compare(p, maxp)) {
			maxid = i;
			strcpy(maxp, p);
		}				
	}
	
	printf("%d\n%s", maxid, maxp);
	
	return 0;
}

高精度加法

P1601 A+B Problem（高精）Ci = Ai + Bi 再考虑进位

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 506;
int a[MAXN], b[MAXN], sum[MAXN];
char ac[MAXN], bc[MAXN];

//int lena, lenb, lensum;
// 使用a[0] b[0] sum[0] 表示长度 

void convert(char ca[], int a[])
{
    int len = strlen(ca);
	for(int i = 1; i <= len; i++)
	{
		a[i] = ca[len - i] - '0';
	}
	a[0] = len;
}

void print(int ans[])
{
    for(int i = ans[0]; i >= 1; i--)
        printf("%d", ans[i]);
}

int add(int a[], int b[], int sum[])
{
	int i = 1, x = 0;
	while(i <= a[0] || i <= b[0]) {
		sum[i] = a[i] + b[i] + x;
		x = sum[i]/10;
		sum[i] = sum[i] % 10;
		i++;
	}
	
	while(x) {
		sum[i] = x % 10;
		x /= 10;
		i++;
	}
	
	sum[0] = i - 1;
}

int main()
{
	scanf("%s", ac);
	scanf("%s", bc);
	
	convert(ac, a);
	convert(bc, b);
	
	add(a, b, sum);
	
    print(sum);
		
	return 0;
}

P2142 高精度减法

Ci = Ai – Bi 再考虑借位

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10088;
char ac[MAXN], bc[MAXN];
int a[MAXN], b[MAXN], ans[MAXN];
// 使用a[0] b[0] ans[0] 表示长度 

void convert(char ca[], int a[])
{
    int len = strlen(ca);
    
	for(int i = 1; i <= len; i++)
	{
		a[i] = ca[len - i] - '0';
	}
	a[0] = len;
}

void print(int ans[])
{
    for(int i = ans[0]; i >=1; i--)
        printf("%d", ans[i]);
}

int compare(int a[], int b[])
{
    int lena = a[0];
    int lenb = b[0];
    
    if(lena > lenb) return 1;
    if(lenb > lena) return -1;
    
    for(int i = lena; i >=1; i--)
    {
        if(a[i] > b[i]) return 1;
        if(a[i] < b[i]) return -1;
    }
    
    return 0; //a==b
}

int sub(int a[], int b[], int ans[])
{
	int i;
	int *big, *little;
	
	if(compare(a, b) >= 0) {
		big = a;
		little = b;	
	} else {
		big = b;
		little = a;
	}
	
	for(i = 1; i <= big[0]; i++) {
		ans[i] = big[i] - little[i] + ans[i];
		if(ans[i] < 0) {
			ans[i] += 10;
			ans[i + 1] -= 1;
		}
	}
	i = big[0];
	while(ans[i] == 0 && i > 1)
		i--;
	
	if(big == b)
		ans[i] *= -1;
	
	ans[0] = i;
}

int main()
{
	scanf("%s", ac);
	scanf("%s", bc);

	convert(ac, a);
	convert(bc, b);
	sub(a, b, ans);
	print(ans);	
		
	return 0;
}

P1303 A*B Problem

c[i+j-1] += a[i] * b[j];

#include <bits/stdc++.h>
using namespace std;

char ac[2008], bc[2008];
int a[2008], b[2008], ans[4000008];
// 使用a[0] b[0] ans[0] 表示长度 

void convert(char ca[], int a[])
{
    int len = strlen(ca);
	for(int i = 1; i <= len; i++)
	{
		a[i] = ca[len - i] - '0';
	}
	a[0] = len;
}

void print(int ans[])
{
    for(int i = ans[0]; i >=1; i--)
        printf("%d", ans[i]);
}

void mult(int a[], int b[], int ans[])
{
	int i, j, len;
	
	for(i = 1; i <= a[0]; i++) {
		for(j = 1; j <= b[0]; j++) {
			ans[i+j-1] += a[i] * b[j];
		}
	}
	
	len = a[0] + b[0];
	for(i = 1; i < len; i++) {
		ans[i + 1] += ans[i] / 10;
		ans[i] %= 10;
	}
	
	while(ans[i] == 0 && i > 1)
		i--;
		
	ans[0] = i;	
}

int main()
{
	scanf("%s", ac);
	scanf("%s", bc);

	convert(ac, a);
	convert(bc, b);
	mult(a, b, ans);
	print(ans);	
		
	return 0;
}

P1480 A/B Problem

Ci = (x * 10 + Ai) / B; 
x = (x * 10 + Ai) % B;

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5008;
char ac[MAXN];
int a[MAXN], b, ans[MAXN];
// 使用a[0] b[0] ans[0] 表示长度 

void convert(char ca[], int a[])
{
    int len = strlen(ca);
	for(int i = 1; i <= len; i++)
	{
		a[i] = ca[len - i] - '0';
	}
	a[0] = len;
}

void print(int ans[])
{
    for(int i = ans[0]; i >=1; i--)
        printf("%d", ans[i]);
}

void div(int a[], int b, int ans[])
{
	int i, x = 0;
	
	for(i = a[0]; i >= 1; i--) {
		x = x * 10 + a[i];
		ans[i] = x / b;
		x = x % b;
	}
	
	i = a[0];
	while(ans[i] == 0 && i > 1)
		i--;
		
	ans[0] = i;	
}

int main()
{
	scanf("%s", ac);
	scanf("%d", &b);

	convert(ac, a);
	div(a, b, ans);
	print(ans);	
		
	return 0;
}

P1080 国王游戏

#include <bits/stdc++.h>
using namespace std;

int n;
struct person {
	int left;
	int right;
	int lr;
};

person p[10008];
bool compare(person p1, person p2)
{
	return p1.lr < p2.lr;
}


int total[1000000]={0, 1,};
int len = 1;
int coin[1000000]= {0}, lc;
int cmax[1000000], lmax;

const int jinzhi = 10;

void multiply(int m)
{
	int idx;
	int x = 0;
	for(idx = 1; idx <= len; idx++) {
		total[idx] = total[idx] * m + x;
		x = total[idx] / jinzhi;
		total[idx] %= jinzhi;
	}
	
	while(x) {
		len++;
		total[len] = x % jinzhi;
		x /= jinzhi;
	}	
}

void div(int k)
{
	int idx;
	int x = 0;
	
	memset(coin, 0, sizeof(coin));
	for(idx = len; idx>=1; idx--) {
		coin[idx] = (x * jinzhi + total[idx]) / k;
		x = (x * jinzhi + total[idx]) % k;		
	}
	
	lc = len;
	while(coin[lc] == 0) {
		if(lc == 1)
			break;
		lc--;
	}
}

void cmpmax()
{
	int i;
	if(lc < lmax)
		return;
		
	if(lc == lmax) {
		for(i = lmax; i >= 1; i--) {
			if(cmax[i] > coin[i])
				return;
			if(cmax[i] < coin[i])
				break;	
		}
			
	}	
		
	for(i = 1; i<=lc; i++) {
		cmax[i] = coin[i];
	}
	lmax = lc;
}

int main()
{
//	freopen("coin.in", "r", stdin);
//	freopen("coin.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 0; i <= n; i++) {
		scanf("%d %d", &p[i].left, &p[i].right);
		p[i].lr = p[i].left * p[i].right;
	}
	
	sort(p+1, p+n+1, compare);

	for(int i = 1; i <= n; i++) {
		 multiply(p[i-1].left);
		 div(p[i].right);
		 cmpmax();
	}	
	
		
	while(lmax>=1){
		printf("%d", cmax[lmax]);
		lmax--;
	}
	
	return 0;
}

高精度除以高精度

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 506;
int a[MAXN], b[MAXN], c[MAXN];
char ac[MAXN], bc[MAXN];

// 使用a[0] b[0] c[0] 表示长度 

void convert(char ca[], int a[])
{
    int len = strlen(ca);
	for(int i = 1; i <= len; i++)
	{
		a[i] = ca[len - i] - '0';
	}
	a[0] = len;
}

void print(int ans[])
{
    for(int i = ans[0]; i >= 1; i--)
        printf("%d", ans[i]);
}


// 1 代表大于,  -1 代表小于, 0 代表相等.
int compare(int a[], int b[])
{
    int lena = a[0];
    int lenb = b[0];
    
    if(lena > lenb) return 1;
    if(lenb > lena) return -1;
    //从高位开始比较 
    for(int i = lena; i >=1; i--)
    {
        if(a[i] > b[i]) return 1;
        if(a[i] < b[i]) return -1;
    }
    
    return 0; //a==b
}
 
void sub(int a[],int b[])//计算a=a-b
{
    int flag;
    int i;
 
    flag=compare(a,b);
    if(flag==0)//相等
    {
        a[0]=0;
        return;
    }
    if(flag==1)//大于
    {
        for(i=1;i<=a[0];i++)
        {
            if(a[i]<b[i])//若不够向上借位
            {
                a[i+1]--;
                a[i]+=10;
            }
            a[i]-=b[i];
        }
        while(a[0]>0&&a[a[0]]==0)//删除前导0
            a[0]--;
        return;
    }
}

int main()
{
    cin>>ac>>bc;
    
	convert(ac, a);
	convert(bc, b);
 
    int temp[MAXN], i, j;
    
    c[0]=a[0]-b[0]+1;
    for(i = c[0]; i > 0; i--)
    {
        memset(temp,0,sizeof(temp));
        for(j = 1; j <= b[0]; j++)//从i开始的地方，复制数组b到数组temp
            temp[j+i-1]=b[j];
        temp[0]=b[0]+i-1;
 
        while(compare(a,temp)>=0)//用减法模拟
        {
            c[i]++;
            sub(a,temp);
        }
    }
 
    while(c[0]>0 && c[c[0]]==0)//删除前导0
        c[0]--;
 
    cout<<"商为：";
    if(c[0]==0)//输出结果
        cout<<0<<endl;
    else
    {
        for(i=c[0];i>0;i--)
            cout<<c[i];
        cout<<endl;
    }
 
    cout<<"余数为：";
    if(a[0]==0)//输出余数
        cout<<0<<endl;
    else
    {
        for(i=a[0];i>0;i--)
            cout<<a[i];
        cout<<endl;
    }
 
    return 0;
}

文章