小码王の笔记
2024-10-12 20:35:27
发布于：浙江
高精度
高精度算法通常被用于解决大数字之间的加减乘除的问题。
而我们在上两节课的学习过当中，认识到了整数的高精度加减乘除方法。
高精度算法的操作步骤
1. 存储
假如说现在有一个需要输入存储在计算机当中。为了存储这个数字，我们会采用数组的方式来储存。
使用数组当中的每一格来存储数字的每一位的数值。
通常我们会去使用string的数据类型来存储输入进来的特别大的数字。
在面对加、乘、减的运算的时候，我们是从个位的开始运算的，为了使得两个计算操作数个位对齐，在存储的时候我们还会将其逆序存储到数字数组
int a[MAXN];
int b[MAXN];
string s1,s2;
cin >> s1 >> s2;
int len1 = s1.size() ;
int len2 = s2.size();
for(int i = 0 ; i < len1 ; i ++)
{
a[i] = s1[len1 - i - 1] - '0';
}
for(int i = 0 ; i < len2 ; i ++)
{
b[i] = s2[len2 - i - 1] - '0';
}
在除法的时候，因为计算是从最高位开始，所以则正序存储
string s;
cin >> s;
int len = s.size();
for(int i = 0 ;i < len ; i ++ )
{
a[i] = s[i] - '0';
}
模拟竖式计算
加法： 两两相加，可能出现进位情况
int c[100005];
int len = max(len1,len2); // 获取较**大小
for(int i = 0 ; i < len ; i ++ )
{
// 两两相加
c[i] += a[i] + b[i];
if(c[i] >= 10) { // 进位
c[i] %= 10;
c[i+1] += 1;
}
}
减法: 两两相减，不够借位
for(int i = 0 ; i < len ; i ++ )
{
c[i] = a[i] - b[i];
if(c[i] < 0){
// 借位
c[i] += 10;
c[i+1] -= 1;
}
}
乘法: 两位相乘，结果位数为两位的位数相加开始向前进位
for(int i = 0 ; i < len1 ; i ++ )
{
for(int j = 0 ; j < len2 ; j ++ )
{
c[i + j] += c[i] * c[j] ;
if(c[i + j] >= 10){
// 进位
c[i + j + 1] += c[i + j] / 10 ;
c[i + j] %= 10;
}
}
}
除法: 最高位开始进行除，余数进位与后一位结合继*除，直到全部除完才结束。
long long r = 0 ; // 余数
for(int i = 0 ; i < len ; i ++ )
{
r = r * 10 + a[i]; // 进位 结合后一位
c[i] = r / b ; // b是除数
r %= b;
}
3. 去除前导零/判断进位
4. 正序/逆序输出
树的表示法
赋予每一个节点编号，我们可以利用每一个节点的编号作为数组的下标，开辟一个数组来保存每个节点的相关信息。
例如一棵树当中有节点编号。我们就可以开一个数组来保存节点的信息到a[1],a[3],a[5],a[7],a[9]的数组空间当中。
1. 父亲表示法
利用孩子编号作为下标的数组空间当中，保存了他父亲节点的相关编号信息。
假如说现在存在一个节点编号为的节点，他的父亲节点为号，我们就可以用数组空间a[3] = 1来表示3号节点的父亲为1号节点。
2.孩子表示法
利用当前节点编号作为下标，开辟一个静态链表（通常可以使用vector来表示），储存孩子的编号
举个糖炒栗子,假如现在有一个节点，孩子为，我们就可以开辟一个vector数组 ve[100005]，使用ve[3]保存数字4,5,6，即ve[3] = {4,5,6}。 来代表3号节点的孩子存在4,5,6。
*孩子表示法与父亲表示法结合
我们可以发现无论是哪种表示法都是采用当前节点编号作为下标来保存父亲/孩子的编号，那么我们就可以开辟一个结构体，同时创建出两片空间来保存父亲和孩子 即
struct Node{
int father;
vecotr<int> son ;
}a[10005];
当你存在一个节点,父亲节点为1且孩子节点为6,7时，你就可以这样保存它。
a[3].father = 1; // 保存父亲编号
a[3].son.push_back(6);
a[3].son.push_back(7); // 保存孩子编号
哈夫曼编码
哈夫曼编码可以粗略的理解为 从根结点走到某一个节点的路径记录。
记录方式为: 从根结点开始，构建出一个字符串作为路径的记录依据。 每次向左走在字符串末尾添加字符'0',向右走在字符串当中添加字符'1'。
通常题目会问
Q1 :从根结点到达某个节点的哈夫曼编码长度为多少?
A1 :从根结点到达某个节点的路径长度为多少？ -> 输出路径长度即可。
A2:从根结点开始出发到达某个节点的哈夫曼编码为多少？
Q2:从根结点开始往下走，走到目标节点的01字符串则为哈夫曼编码
有帮助，赞一个