【基础算法】高精度（一）

• 定义
  高精度计算（Arbitrary-Precision Arithmetic），也被称作大整数（bignum）计算，运用了一些算法结构来支持更大整数间的运算（数字大小超过语言内建整型）。
• 思考
  
• 高精度的输入和输出
  当一个数据很大的时候，我们用一个整数类型是存不下的，所以我们可以先用一个字符串输入，这样就可以输入很长的数，然后再利用字符串函数和操作运算，将每一位数取出，存入一个数组里，我们用数组里的每一位表示这个数的每一个数位。（一个数组表示一个数）

例如：998244353用数组储存下来，a{3,5,3,4,4,2,8,9,9}，一般是倒着存（数字的长度可能发生变化，但我们希望同样权值位始终保持对齐（例如，希望所有的个位都在下标 [0]，所有的十位都在下标 [1]……）；同时，加、减、乘的运算一般都从个位开始进行（回想小学的竖式运算～），这都给了「反转存储」以充分的理由。
此后我们将一直沿用这一约定。）。

• 输入

 void init(int x[]){
	char s[501];
	cin>>s; 
	x[0]=strlen(s); //记录数字长度
	for(int i=0;i<x[0];i++){
		x[x[0]-i]=s[i]-'0'; //将字符串转换为数字，并倒序存储
	}
}

• 输出

 for(int i=len;i>0;i--)
               printf("%d",a[i]);// 一位一位的输出 

• 高精度比较大小
  高精度比较大小的步骤大致如下：

1、比较两个数的长度，长度更长的数越大。

2、如果两个数长度相等，那么就从高位到低位一位一位比较，如果某一位数字不同时，较大的数大。否则继续比较下一位。

3、如果比到最后都没有比出谁大谁小，就说明这两个数一样大。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
//比较a和b的大小，如果a>b则返回真，否则返回假
int a[6666],b[6666];
int compare(){
        int lena=strlen(a);
        int lenb=strlen(b);
    if(lena>lenb) return 1;//lena表示a这个数的长度，lenb则表示b的长度
    if(lenb>lena) return 0;//步骤1
    for(int i=lena;i>0;i--){//从高位到底位一位一位比较
        if(a[i]>b[i]) return 1;
        if(b[i]>a[i]) return 0;
    }//步骤2
    return 0;//步骤3，a=b，即a不大于b
}