HHU计信院研算法考试要点整理

简答题

算法：能解决某类问题的程序，算法设计五大要素：正确性、工作量，空间量、简单和最优性。
算法的复杂性：算法运行时所需要的计算及资源量即占用计算机的时间和空间量。
最坏情况：使复杂性最大的那个输入为最坏情况。
最坏情况下算法的下界：在使复杂性最大的输入的情况下，至少执行的计算次数。
多项式有界：算法最坏情况下的复杂性在一个关于输入多项式范围之内。
P问题：多项式有界的决策问题。P问题是可以在多项式时间内被确定机(通常意义的计算机)解决的问题.
NP问题：多项式的非决定算法的决策问题。是指可以在多项式时间内被非确定机解决的问题.
NP完全问题/ NPC问题：如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题（Non-deterministic Polynomial complete problem）。
有限状态自动机：是一种识别装置的抽象概念。有限状态自动机拥有有限数量的状态，每个状态可以迁移到0个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。
激活帧：递归程序调用过程中用来保存程序，局部变量、实参、临时变量、返回值等的基本存储单元。
反向拓扑序列：每条起点的编号大于终点的编号。
（两个无向图的）合成图：设G1=（V1，E1），G2=（V2，E2），则G1，G2的合成图，记为G1[G2(V1,V2)]，=（V，E）。其中V=V1*V2，每个顶点对应合成图中的一个顶点，边集E为E1和E2的并集，由本地和远程两类边构成。
子问题图：假设一个递归算法A能觉某个问题，则A的子问题就是一个有向图，他的节点代表一个实例的输入，当解决问题时，他的有向边I→J代表当算法A的实例被激活后立即递归调用J实例。
动态集合：计算过程中成员在变化的集合。
锦标赛法：将N个数据元素两两分组，分别按关键字是进行比较，得到二分之N个比较的优胜者作为第一步比较的结果保留下来（如果出现奇数个则随机选出一个作为胜出者），然后对二分之N个数据元素再两两分组，分别安抚按键字比较，直至选出最大或最小元素。
最优二叉搜索树：假设键k1, k2, ... kn被查询的概率为p1, p2, ... pn, ci为查找到ki所做比较的次数，则二叉树T中平均查找次数A(T)= ，平均查找次数最小的树叫最优二叉搜索树。
哈密顿回路：由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次的路径。
哈密顿图：一个无向图的哈密顿图是一个简单路径，它含有图中所有节点，并且每个节点经过且只经过一次，存在这样路径的图称之为哈密顿图。
旅行售货员问题：售货员从原点出发访问领域内所有城市再回到原点，使旅行开销最小。
FFD策略：受贪心算法的启示，首先将物体按其尺寸从大到小排序，然后把每个物体放在第一个能够容纳它的的箱子中。
动态规划：将一个大问题分解成为若干个相同类型的子问题，通过解决子问题而得到原问题的解。保留子问题的解，避免重复计算，通常是自底而上进行。
装箱问题：有n件物品，每件物品体积为s1,s2,..,sn,其中0<si≤1，有无数只箱子，每只箱子容积为1，求能容纳这些物品的最小箱子数。
背包问题：给出n个尺寸为S1...sn的物品和容积为c的背包，能否找到n个物品的一部分使得背包尽肯能多的填满。
着色问题：图着色问题即为将顶点分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。
子集和问题：给一个整数集合s和一个整数n，请问s中是否存在一个子集合，这个集合里的元素和等于n。
决策问题：决策是针对某一问题，根据确定的目标及当时的实际情况制订多种候选方案，然后按一定的标准从中选出最佳方案的过程。
贪心算法：每次取得局部最优，最后找到整体最优解。
分治算法：分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。
回溯算法：当完成一个尝试序列后，算法回溯到最近选择的点上，并尝试另一个选择。当在该选择点上的所有选择都完成后，回溯到更早的选择点上，并尝试该点的选择。如此循环知道所有选择都被考虑。

证明题

感觉会了这个就会其他的了。数学归纳法，利用等于k/2时来证明等于k时。

动态规划

感觉动态规划考的还是挺多的，但是题型比较固定，例如字符串匹配（2-difference）问题，矩阵相乘问题，文本分行问题，最优搜索二叉树问题等。

最优搜索二叉树

定义如下：给定一个n个不同关键字已排序的序列 K=<k1,k2,...,kn> (因此 k1<k2<...<kn)，我们希望用这些关键字构造一棵二叉搜索树。对每个关键字 ki，都有一个概率pi表示其搜索频率。我们希望构造一棵期望搜索代价最小的二叉搜索树，我们称之为最优二叉搜索树。二叉搜索树不一定是高度最矮的。而且，概率最高的关键字也不一定出现在二叉树搜索树的根结点。

根据算法导论，不设置虚拟键，就按照考试考的来，令e[i][j]为i到j的关键字的最优搜索子树的搜索代价，root[i][j]表示i到j关键字组成的最优搜索子树的根，我们再开一个w[i][j]数组表示i到j的概率和。最后我们要求的就是e[1][n]。代码如下：

for(l=1;l<n;l++){   // n为关键字的总数
    for(i=1;i<=n-l+1;i++){
        j = i+l-1;
        e[i][j]=inf;
        w[i][j]=w[i][j-1]+p[j];    //更新i到j的概率和
        for(k=i;k<=j;k++){
            temp=e[i][k-1]+e[k+1][j]+w[i][j];   //这步比较关键，因为把k当作根节点，所以除了k之外的其他节点代价都要加上自己的概率，因为树高度增加了1
            if(temp<e[i][j]){
                e[i][j]=t;
                root[i][j]=r;     // 更新节点
            }
        }
    }
}

当然，数量少手推也可以，例如：

cost数组就是e数组。

文本分行

是一个dp问题，dp[i][j]=max(dp[i-1][j]+p[i],dp[i-2][j]+p[i-1][i],...) 其中p[i][j]为i到j分为一行的代价。

题目如图所示，贪心很简单，然后动态规划需要考虑一下最后为0的情况即可。手推的话就像上面，我写了个代码，如下：

#include<bits/stdc++.h>
using namespace std;
int a[13] = {0,6,4,7,9,4,5,4,10,3,7,4};
int dp[20][20],w[20],n=11;
int count_loss(int x){
    return pow(17-x, 3);
}
int main(){
    memset(dp, 0, sizeof(dp));
    memset(w, 0, sizeof(w));
    for(int i=1;i<=11;i++){
        w[i] = w[i-1]+a[i];
    }
    for(int i=0;i<=n;i++){
        dp[i][i]=(17-a[i])*(17-a[i])*(17-a[i]);
    }
    dp[11][11]=0,dp[10][11]=0,dp[9][11]=0;
    for(int l=1;l<n;l++){
        for(int i=1;i<=n-l;i++){
            int j = l+i;
            dp[i][j]=65535;
            for(int k=i+1;k<=j;k++){
                if(w[k]-w[i-1]<=17){
                    //做一个判断  让最后一行的代价为0 
                    if(w[j]-w[k]<=17&&j==11)
                    dp[k+1][j]=0;
                    int temp = count_loss(w[k]-w[i-1])+dp[k+1][j];
                    if(dp[i][j]>temp)
                        dp[i][j] = temp;
                }
                else
                    break;
            }
        }
    }
    cout<<dp[1][11]<<endl;
    return 0;
}

矩阵相乘

感觉和上面一样一样的，也附一张图把。算出它的两个矩阵，一个是cost一个是last，cost是两个维度之间的最小代价，last是下一个分开相乘的位置。递推公式：

假设k是对矩阵链A[i,j]一分为二得到最优解时的断开位置，则m[i,k]和m[k+1,j]分别是两个子矩阵链A[i,k]和A[k+1,j]的最优解。两个矩阵最后要相乘才能得到A[i,j]，因此，最后要加上p_{i-1}p_kp_j，也就是两子矩阵相乘的数乘次数，才能得到总的数乘次数。

近似字符匹配

近似字符匹配也是一个动态规划类型题目。是为了计算一个模板串和字符串的匹配程度，x-diference近似可以简单的理解为只需要两次或两次以下的操作可以使得两个字符串相等。操作包括增加一个字符，删除一个字符或替换一个字符。用动态规划：dp[i][j]代表检索到字符串的第i个字符和模板串的第j个字符时二者的差异程度。如果小于等于2则认为是2-difference。那么根据以上想法，可以得到动态规划的关系转移矩阵：

dp[i][j] = dp[i-1][j-1]       if P_i=T_j    
dp[i][j] = min(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1)      otherwise

i和j是当前模板串（待匹配字符）和字符串的位置，因此如果二者相等，自然而然就和dp[i-1][j-1]相等，否则就有三种情况：

  • 将当前两个字符i和j视为错误匹配，那么dp[i][j] = dp[i-1][j-1]+1;
  • 将P_i与空字符匹配，那么dp[i][j] = dp[i][j-1]+1；
  • 将T_j与空字符匹配，那么dp[i][j] = dp[i-1][j]+1。
#include<bits/stdc++.h>
using namespace std;
int dp[100][100];
int minimum(int a,int b,int c){
    return a<b?(a<c?a:c):(b<c?b:c);
}
int main(){
    memset(dp, 0, sizeof(dp));
    string a= " algorithm";
    string b = " The BM algorithm is better than KMP algorism";
    int l1 = a.length()-1;
    int l2 = b.length()-1;
    cout<<l1<<" "<<l2<<endl;
    // 不能少了这一行
    for(int i=0;i<=l1;i++){
        dp[i][0]=i;
    }
    for(int i=1;i<=l1;i++){
        for(int j=1;j<=l2;j++){
            if(a[i]==b[j]){
                dp[i][j] = dp[i-1][j-1];
            }else{
                dp[i][j] = minimum(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1;
            }
        }
    }
    int cnt = 0;
    for(int i=0;i<=l2;i++){
        if(dp[l1][i]<=2){
            cout<<b[i]<<endl;
             cnt++;
        }
    }
    cout<<"There are "<<cnt<<" 2-differece string."<<endl;
    return 0;
}

下面祖传代码给了递推的过程。但是这个代码还是少了一行初始化。因为在递推的时候，第一行和第一列是要先写好值的，否则答案会错误。写这份答案的人认为空的匹配串（就是第一行全为0的这一行）和所有字符串误差都为0，而匹配串和一个空字符' '(第一列）的误差为匹配串的长度，这么想也很正常，但是代码里没有写，递推会出现错误。

排序算法

这一章节主要是写排序算法和排序算法的判定树。开始还很懵逼，这交换得有多少个，仔细看一下，实际上一般只会有3-4个元素的排序，有时候还会给定两个已知元素的大小。按照算法比较就可以了。先上代码：

// 插入排序
void insertSort(int a[], int N)
{
    for(int i = 1; i < N; i++)
    {
        int temp = a[i];
        int j;
        for(j = i; j > 0 && temp < a[j-1]; j--)
            a[j] = a[j-1];
        a[j] = temp;
    }
}
// 冒泡排序
void bubbleSort(int a[], int N)
{
    for(int i = 0; i < N; i++)
    {
        for(int j = i; j < N - i - 1; j++)
        {
            if(a[j] > a[j+1])
            {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}
// 快速排序
void quickSortCore(int a[], int left, int right)
{
    if(left < right)
    {
        int temp = a[left];
        int i = left, j = right;
        while(i < j)
        {
            while(i < j && temp <= a[j])
                j--;
            if(i < j)
                a[i++] = a[j];
            while(i < j && temp >= a[i])
                i++;
            if(i < j)
                a[j--] = a[i];
        }
        a[i] = temp;
        quickSortCore(a, left, i-1);
        quickSortCore(a, i+1, right);
    }

}

void quickSort(int a[], int N)
{
    quickSortCore(a, 0, N-1);
}
// 选择排序
void selectSort(int a[], int N)
{
    for(int i = 0; i < N; i++)
    {
        int k = i;
        for(int j = i + 1; j < N; j++)
        {
            if(a[j] < a[k])
                k = j;
        }
        int temp = a[i];
        a[i] = a[k];
        a[k] = temp;
    }
}
// 归并排序（合并排序）
void merge(int a[], int temp[], int left, int mid, int right)
{
    if(left < right)
    {
        int lpos = left, lend = mid;
        int rpos = mid + 1, rend = right;
        int tpos = left;
        while(lpos <= lend && rpos <= rend)
        {
            if(a[lpos] <= a[rpos])
                temp[tpos++] = a[lpos++];
            else
                temp[tpos++] = a[rpos++];
        }
        while(lpos <= lend)
            temp[tpos++] = a[lpos++];
        while(rpos <= rend)
            temp[tpos++] = a[rpos++];
        for(int i = 0; i <= right; i++)
            a[i] = temp[i];
    }
}
void mergeSortCore(int a[], int temp[], int left, int right)
{
    if(left < right)
    {
        int mid = (left + right) / 2;
        mergeSortCore(a, temp, left, mid);
        mergeSortCore(a, temp, mid+1, right);
        merge(a, temp, left, mid, right);
    }
}
void mergeSort(int a[], int N)
{
    int *temp = new int[N];
    mergeSortCore(a, temp, 0, N-1);
    delete [] temp;
}

如图，12已经有序，先插入3，3>2，则有序，将插入4，4与3比较；若3<2,还要将3继续往前插，和1比较.......按照算法流程即可。毕竟元素个数有限不太复杂。

再如，它这里是从后往前冒泡，最小元素在最左边。x3>x4,x4向前冒泡一位，x4再和x2比较，x4若大于x2则结束，否则还得接着往前冒泡，和1比较，当确定了第一个元素，接着将后三个元素同理即可。必要容易笔误。。。。

再再如图所示，快速排序其实也是一样，把x1作为pivot，x4和x1比较，x4大于x1则右指针往左走，x3和x1比较，x4小于x1则将x4放到最左边，左指针从x2向右走，x2已知大于x1，x2移到后面，还是x3和x1比较......如此反复即可，需要注意的就是在排序的决策树中将已知的比较跳过。

其他算法

装箱问题

问题描述：一维经典装箱问题可描述如下：S=（S1,S2,..Sn）,其中0< Si ≤ 1, 称之为第i个物体的体积（或重量），1≤i≤n,现有n个容积（或载重量）为1 的箱子，要求如何设法将S1,S2,..Sn放入尽可能少的箱中。

　　装箱问题是NP问题,即在多项式时间内无法精确求解,一般采用近似算法,即启发式算法,这样可以迅速得到满意解,而不一定是最优解。

　　常见的算法：NF(Next Fit)近似算法，FF(First Fit)近似算法，FFD（First Fit Decreasing）近似算法，BF(best Fit),BFD(Best Fit Deceasing)等。

　　下次适应算法（NF, Next Fit）：NF算法是最简单也是最早研究的一个算法，它的处理方法是始终维持一个当前打开的箱子，对于每一个要装入的物品，检查该物品是否可以放入当前打开的箱子，如果无法装入，则打开一个空箱子，装入该物品，以该箱子作为当前的箱子，由于每个物品在装入时，只有当前打开的箱子和空箱可以选择，这必然造成装箱的效率低下。

　　首次适应算法(First Fit)：针对下次适应算法的缺陷，首次适应算法FF处理当前物品的时候，检查所有非空箱子，找到第一个能够放下当前物品的箱子并将该物品放入，否则则开启新的箱子。
　　
　　最佳适应算法(Best Fit)：与首次适应算法类似，唯一的区别时当物品装箱时，不是直接装在第一个可装入的箱子中，而是装入在最适合该物体的箱子中，如果没有该箱子，则开启空箱。
　　
　　首次适应算法和最佳适应算法有一个缺陷，即由于物品没有实现排序，则可能由于先装入小的物品，使大的物品在后来放入时无法装入，只得开启新的箱子，造成了空间的浪费,因此才有了这两种算法的改进算法。

　　降序首次适应算法(FFD, First Fit Decreasing)：先对物品按降序排序，再按照首次适应算法进行装箱。

　　降序最佳适应算法(BFD, Best Fit Decreasing)：先对物品按降序排序，再按照最佳适应算法进行装箱。

一般考试就是考FFD（我猜的）。比如这样：

KMP算法

KMP看着就是考有限自动机以及KMP流图。有限自动机先写上标号，然后画箭头就行了,正确的字符就一直往右走，碰到无法向后走的字符需要判断它目前的前缀，指向相应的字符即可：

KMP流图需要理解KMP算法，但其实无脑直接找next数组就可以了。next数组就是当前字符的前面字符的最大相同的前后缀。举例：见上图，第一个字符A的next默认为-1，第四个字符B的数组为1因为ABA有共同的前后缀A，第6个B的数组为3是因为ABABA有共同前后缀ABA长度为3。这样求出next数组，fail直接加1即可。然后把对应的fail箭头指向相应下标的字符。

再说说KMP的核心思想，通常字符串匹配失败之后向后移动一位，但是会造成大量重复和无意义的比较。next数组就是为了每次根据需要移动，KMP的移动位数 = 已匹配的字符数 - 对应的部分匹配值，举例：

网上找的一张图，D匹配失败以后，这个位置的next值为2，那么继续将第二个字符C与空格比较，失效的话再继续找C这个位置的next数组值，一直不匹配最后会从头开始。实现了一下代码，如下：

int KMP(string t, string p) {
    // 获得next数组 
    int next[100];
    next[0] = -1;
    int i = 0;
    int j = -1;

    while(i < p.length() - 1) {
        if (j == -1 || p[i] == p[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
  
    i = 0,j = 0;
    // 开始 
    while (i < t.length() && j < p.length()) {
        // j == -1 表示从搜索词最开始进行匹配
        if (j == -1 || t[i] == p[j]) {
            i++;
            j++;
        // 匹配失败时，查询“部分匹配表”，得到搜索词位置j以前的最大共同前后缀长度
        // 将j移动到最大共同前后缀长度的后一位，然后再继续进行匹配
        } else {
            j = next[j];
        }
    }
    // 搜索词每一位都能匹配成功，返回匹配的的起始位置
    if (j == p.length())
        return i - j;
    else
        return -1;
}

BM算法

BM是个比KMP还要高效的算法，算法包含了两个重要的内容，分别是好后缀和坏字符的规则；

  • 坏字符：当模式串和原串的字符并不匹配时，原串中的字符就称为坏字符；
  • 好后缀：模式串和原串的字符相等时所有的字符串，比如ABCD和BCD，那么它的好后缀则包括第一次匹配的D，和第二次匹配的CD，还有第三次的BCD。

对于坏字符来说：

  • 坏字符没出现在模式串中，这时可以把模式串移动到坏字符的下一个位置，继续比较
  • 若坏字符出现在模式串中，这时可以把模式串中第一个出现（从后往前数第一个出现，也就是从前往后数，最靠右出现的）的坏字符和原串的坏字符对齐；

对于好后缀：

  • 模式串中有子串匹配上好后缀，此时移动模式串，让子串和好后缀对齐即可，如果超过一个子串匹配上好后缀，则选择最靠左边的子串对齐；
  • 模式串中没有子串匹配上后缀，接着寻找模式串中的一个和好后缀（子串）相等的最长前缀，并让该前缀和好后缀对齐即可；
  • 模式串中没有子串匹配上好后缀，并且在模式串中找不到和好后缀（子串）相等的最长前缀，此时，直接移动模式到好后缀的下一个字符。

总结一下，就是模式串有完整的后缀就把模式串最左边后缀对齐，没有的话就看后缀字串有没有与模式串前缀相同的，有就将之对齐，最后才是把整字符串后移。


// a,b 表示主串和模式串；n，m 表示主串和模式串的长度。
public int bm(char[] a, int n, char[] b, int m) {
  int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
  generateBC(b, m, bc); // 构建坏字符哈希表
  int[] suffix = new int[m];
  boolean[] prefix = new boolean[m];
  generateGS(b, m, suffix, prefix);
  int i = 0; // j 表示主串与模式串匹配的第一个字符
  while (i <= n - m) {
    int j;
    for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
      if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是 j
    }
    if (j < 0) {
      return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
    }
    int x = j - bc[(int)a[i+j]];
    int y = 0;
    if (j < m-1) { // 如果有好后缀的话
      y = moveByGS(j, m, suffix, prefix);
    }
    i = i + Math.max(x, y);
  }
  return -1;
}

// j 表示坏字符对应的模式串中的字符下标 ; m 表示模式串长度
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
  int k = m - 1 - j; // 好后缀长度
  if (suffix[k] != -1) return j - suffix[k] +1;
  for (int r = j+2; r <= m-1; ++r) {
    if (prefix[m-r] == true) {
      return r;
    }
  }
  return m;
}

一般说的suffix数组，它的下标 k，表示后缀子串的长度，下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值。

但是似乎和我想得不太一样，matchjump看了下ppt应该是好后缀跳跃的次数。这个也不太对。待补。。。。

背包问题近似解

这个。好像按照顺序排列然后扫描一遍往里填就行了。当然它本身也是个严谨的算法，但是为了考试嘛。。。

斐波那契数列的激活树和子图问题

激活树就是把递归调用的过程化成树的形状，然后把线连起来。子图是把树画成图的形式调用。

独立集问题

有时也会说着色问题，因为着色问题就是把图的顶点着两种或多种颜色，相邻的两个点不同色，这样每个组就形成了一个独立集。

看着只是一个树染色的问题。有一道题戳

二分查找和黄金查找决策树

二分查找就是按照标号来，0直接带入算即可，黄金分割需要找到数的个数，用个数乘0.618。都是取下界。

其他其他算法

还有一些算法不知道是什么，也没书也没听。

5个元素用7次比较排序

有五个数字，[a, b, c, d, e]，进行排序。以下排序均按从小到大进行排序：

  • 将a与b进行排序，排序结果为[a, b]，共用1次比较，累计1次比较；
  • 将c与d进行排序，排序结果为[c, d]，共用1次比较，累计2次比较；
  • 将a’与c’进行比较，若a < c，则a < c < d，同时a < b；否则 c< a < b，同时c < d。共用1次比较，累计3次比较。将未排入序列的数字记为x；
  • 将e向已排序的三个元素中进行插入，最大需2次比较，累计5次比较；
  • 将x将向序列中进行排序。由于已知x比序列序列中一个元素要大，所以x一定比当前序列中最左值要大，所以最多还要和三个元素进行比较，需要2次比较，累计7次比较。

5个元素6次找出中位数

先把a和b、c和d的大小关系找到，例如a<b,c<d。然后比较两个关系的最小值，在这里是a和c。无论大小关系都可以得到两个开头一样的不等式：

  • 若a<c,则a<c<d且a<b
  • 若a>c,则c<a<b且c<d

这样就可以b与e进行比较，若b<e,上面第一种情况里就a<b<e且a<c<d，a最小，还有两次比较并且已经部分有序，就easy了。若b>e，上面第一种情况就变成a<c<d且a<b且e<b，比较e和c，e>c则比较d和e，若e<c则比较b和c。其他同理。

int compare6(int a,int b,int c,int d,int e){
    if(a<b)swap(a,b);
    if(c<d)swap(c,d);
    if(a<c){swap(a,c);swap(b,d);}
    if(b<e)swap(b,e);
    if(b<c){swap(b,c);swap(d,e);}
    if(e<c) return c;
    else return e;
}

12个球三次找出次品

没想出来。直接上链接：传送门

正常的分三组每组4个，如果平衡就是在剩下的一组中，如果不平衡次品球就是在天平上的这8个，轻重未知。其实就是利用更换球的位置平衡是否改变来判断球的位置。

证明递归算法有效性

贴个图，好复习。

参考文章

BM算法

字符串匹配的Boyer-Moore算法

[王峥数据结构与算法]()

中位数比较

Ps：除了BM算法和中位数比较的代码是参考的，文中的扫描图片是祖传的，FDD的解释来自百度百科。其他的是自己写的。图片侵删。

最后修改：2022 年 06 月 21 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏