复习建议📝

Tip

1. 伪代码

  由于最后考的题目部分算法要百无一漏的在考场上实现是很不现实的  
  所以算法考试会有大概三道题目用伪代码实现  
  目的是考察算法思想，这个算法你有没有理解  
  但是需要用相对"规范"的语言讲出来，所以提前熟悉下伪代码
  让老师直观的看懂你的思路，然后把分给你是很有必要的

伪代码（Pseudocode）就像是程序员世界里的“通用世界语”。它不是一种可以被计算机直接编译或运行的真实编程语言，而是一种介于自然语言和编程语言之间、用来描述算法逻辑的工具。

以下是对伪代码及其规范书写方式的全面总结：

一、什么是伪代码？

1. 核心定义 伪代码使用结构化的文字来表达程序的执行流程。它的目的是让人类（尤其是其他程序员、面试官或研究人员）能够快速理解算法的思想，而不需要陷入特定编程语言（如 Java 的类声明、C++ 的指针、Python 的缩进要求等）的繁琐语法细节中。

2. 核心特点 * 重逻辑，轻语法：你不需要考虑有没有漏写分号、变量是否声明了类型。 * 跨语言通用：写得好的伪代码，无论是写 Python、Go 还是 Java 的人，都能一眼看懂并翻译成自己熟悉的语言。 * 灵活混搭：可以直接把数学公式或人类自然语言嵌在代码逻辑里（例如：找到数组中的最大值 就可以作为一行伪代码）。

二、在算法题中如何规范书写伪代码？

虽然伪代码没有像 C++ 或 Java 那样绝对的国际标准，但在算法面试、学术论文（如 IEEE 格式）和教材中，有一套公认的“潜规则”和规范格式。

1. 标题与输入输出声明

在写复杂算法时，开头最好明确说明算法的名称、输入参数和预期输出。

Algorithm FunctionName(param1, param2) Input: 关于输入的描述 Output: 关于输出的描述

2. 变量与赋值

赋值：通常使用向左的箭头 ← 或 := 来表示赋值，以区别于数学中的相等 =。在简单的白板面试中，直接用 = 也可以，但 ← 更严谨。
- 规范：max_value ← 0 或 swap(A[i], A[j])
数学符号：可以直接使用标准的数学符号，例如 \(\leq\)、\(\geq\)、\(\neq\)、\(\times\)、\(\div\) 等，这比代码里的 <= 或 != 更直观。

3. 控制流（关键字大写）

为了让逻辑结构清晰，通常会将控制流关键字全部大写，并配合严格的缩进来代替大括号 {}。

条件分支：

IF condition THEN
    do something
ELSE IF another_condition THEN
    do something else
ELSE
    do default
END IF

循环结构：

// For 循环
FOR i ← 1 TO n DO
    do something
END FOR

// While 循环
WHILE condition DO
    do something
END WHILE

4. 数组与对象引用

数组/列表：通常用大写字母（如 \(A\)、\(B\)）表示数组，用方括号表示索引。例如：A[1...n]、A[i]。注意：学术伪代码通常从下标 1 开始，而工程伪代码往往从 0 开始，面试时最好提前说明。
对象属性：使用点号表示法，如 node.left、node.value。

5. 注释

使用双斜杠 // 或 /* ... */ 来解释复杂的自然语言步骤。

三、实战示例：二分查找（Binary Search）

结合上面的规范，我们来看一个标准的二分查找伪代码应该长什么样：

Algorithm BinarySearch(A, target)
// Input: A sorted array A of n elements, and a target value.
// Output: The index of the target in A, or -1 if not found.

    left ← 0
    right ← length(A) - 1

    WHILE left <= right DO
        mid ← left + (right - left) / 2  // 防止溢出

        IF A[mid] == target THEN
            RETURN mid
        ELSE IF A[mid] < target THEN
            left ← mid + 1
        ELSE
            right ← mid - 1
        END IF
    END WHILE

    RETURN -1

四、面试/笔试中的避坑指南

不要写成某一种具体的语言：如果你写出了 std::vector<int> 或者 public static void main，这就不是伪代码了，面试官会认为你过分拘泥于语言细节。
避免过度自然语言化：虽然可以混入自然语言，但不要写成纯小作文。例如“一直循环直到找到为止”，应该写成规范的 WHILE not found DO。
忽略无关紧要的边界报错：在伪代码中，除非这个边界条件是算法的核心考点，否则不用花大量篇幅去写 if input_array is null return error 这种工程防御性代码，直奔核心算法逻辑即可。

2. 算法模板

  穷途末路的做法
  遇到实际问题，题目会告诉你用什么算法
  你哪怕不理解算法，不知道如何将算法和实际题意结合
  为了避免分数爆零
  这边建议准备些基础算法的模板进考场
  至少能拿到些许过程分和同情分

2.1 回溯算法（Backtracking）

适用于：排列组合、子集、N 皇后、路径搜索等。

伪代码：

procedure Backtrack(step)

if 已达到结束条件 then
    输出答案
    return

for 每一种可行选择 do
    if 当前选择合法 then
        做选择
        Backtrack(step + 1)
        撤销选择

C++ 示例（输出 1~n 的全排列）：

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

int n;
bool vis[10];
vector<int> path;

void dfs(int step)
{
    if(step == n)
    {
        for(int x : path) cout << x << " ";
        cout << endl;
        return;
    }

    for(int i = 1; i <= n; i++)
    {
        if(!vis[i])
        {
            vis[i] = true;
            path.push_back(i);

            dfs(step + 1);

            path.pop_back();
            vis[i] = false;
        }
    }
}

int main()
{
    cin >> n;
    dfs(0);
}

2.2 泛洪算法（Flood Fill）

适用于：连通块统计、地图染色、岛屿问题。

伪代码：

procedure FloodFill(x, y)

if 越界 或 已访问 或 不合法 then
    return

标记已访问

向上、下、左、右继续搜索

C++ 示例：

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

int n, m;
char g[105][105];
bool vis[105][105];

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void floodfill(int x, int y)
{
    if(x < 0 || x >= n || y < 0 || y >= m) return;
    if(vis[x][y] || g[x][y] == '#') return;

    vis[x][y] = true;

    for(int i = 0; i < 4; i++)
        floodfill(x + dx[i], y + dy[i]);
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> g[i];

    int cnt = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(!vis[i][j] && g[i][j] == '.')
            {
                cnt++;
                floodfill(i, j);
            }

    cout << cnt;
}

2.3 BFS（广度优先搜索）

适用于：最短步数问题、迷宫最短路。

伪代码：

队列 q
起点入队
标记起点

while q 非空 do
    取队首

    for 每个相邻状态 do
        if 未访问 then
            标记
            入队

C++ 示例（迷宫最短路）：

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

struct Node
{
    int x, y, step;
};

int n, m;
char g[105][105];
bool vis[105][105];

int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

int bfs()
{
    queue<Node> q;
    q.push({0,0,0});
    vis[0][0] = true;

    while(!q.empty())
    {
        Node cur = q.front();
        q.pop();

        if(cur.x == n-1 && cur.y == m-1)
            return cur.step;

        for(int i=0;i<4;i++)
        {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            if(nx>=0 && nx<n && ny>=0 && ny<m &&
               !vis[nx][ny] && g[nx][ny]=='.')
            {
                vis[nx][ny] = true;
                q.push({nx, ny, cur.step+1});
            }
        }
    }

    return -1;
}

int main()
{
    cin >> n >> m;
    for(int i=0;i<n;i++) cin >> g[i];

    cout << bfs();
}

2.4 DFS（深度优先搜索）

适用于：连通块、遍历、搜索所有方案。

伪代码：

procedure DFS(x)

标记 x 已访问

for 每个邻点 y do
    if y 未访问 then
        DFS(y)

C++ 示例：

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

vector<int> g[105];
bool vis[105];

void dfs(int x)
{
    vis[x] = true;
    cout << x << " ";

    for(int y : g[x])
        if(!vis[y])
            dfs(y);
}

int main()
{
    int n, m;
    cin >> n >> m;

    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1);
}

2.5 Dijkstra 算法

适用于：非负边权单源最短路。

伪代码：

dist[起点] ← 0
优先队列加入起点

while 队列非空 do
    取距离最小点 u

    for 每条边 u -> v do
        if dist[v] > dist[u] + w then
            更新 dist[v]
            入队

C++ 示例：

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

typedef pair<int,int> PII;
const int INF = 1e9;

vector<PII> g[100005];
int dista[100005];
bool vis[100005];

int main()
{
    int n,m,s;
    cin >> n >> m >> s;

    while(m--)
    {
        int u,v,w;
        cin >> u >> v >> w;
        g[u].push_back({v,w});
    }

    for(int i=1;i<=n;i++) dista[i]=INF;

    priority_queue<PII, vector<PII>, greater<PII>> pq;
    dista[s]=0;
    pq.push({0,s});

    while(!pq.empty())
    {
        int u=pq.top().second;
        pq.pop();

        if(vis[u]) continue;
        vis[u]=true;

        for(auto e:g[u])
        {
            int v=e.first,w=e.second;
            if(dista[v] > dista[u] + w)
            {
                dista[v]=dista[u]+w;
                pq.push({dista[v],v});
            }
        }
    }

    for(int i=1;i<=n;i++) cout << dista[i] << " ";
}

2.6 A* 算法

适用于：带目标点的最短路径搜索。

核心：

f(x) = g(x) + h(x)

g(x): 起点到当前代价
h(x): 当前到终点估价

伪代码：

优先队列按 f 最小排序

起点入队

while 队列非空 do
    取 f 最小状态

    if 到终点 then 返回答案

    扩展相邻状态

C++ 示例（二维网格）：

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

struct Node
{
    int x,y,g,f;

    bool operator < (const Node& other) const
    {
        return f > other.f;
    }
};

int n,m;
char mp[105][105];
bool vis[105][105];

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int h(int x,int y)
{
    return abs(n-1-x)+abs(m-1-y);
}

int astar()
{
    priority_queue<Node> pq;
    pq.push({0,0,0,h(0,0)});

    while(!pq.empty())
    {
        Node cur=pq.top();
        pq.pop();

        if(vis[cur.x][cur.y]) continue;
        vis[cur.x][cur.y]=true;

        if(cur.x==n-1 && cur.y==m-1)
            return cur.g;

        for(int i=0;i<4;i++)
        {
            int nx=cur.x+dx[i];
            int ny=cur.y+dy[i];

            if(nx>=0&&nx<n&&ny>=0&&ny<m&&
               !vis[nx][ny]&&mp[nx][ny]=='.')
            {
                int ng=cur.g+1;
                pq.push({nx,ny,ng,ng+h(nx,ny)});
            }
        }
    }

    return -1;
}

2.7 状态空间搜索

适用于：八数码、魔方、机关按钮、字符串变换。

本质：把每种局面当作一个状态，用 BFS / A* 搜索。

伪代码：

初始状态入队
记录已访问

while 队列非空 do
    取当前状态

    if 为目标状态 then 成功

    枚举所有操作
        生成新状态
        若未访问则入队

C++ 示例（字符串交换到目标）：

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

int bfs(string start, string target)
{
    queue<pair<string,int>> q;
    unordered_set<string> vis;

    q.push({start,0});
    vis.insert(start);

    while(!q.empty())
    {
        auto cur=q.front();
        q.pop();

        string s=cur.first;
        int step=cur.second;

        if(s==target) return step;

        for(int i=0;i<(int)s.size()-1;i++)
        {
            string t=s;
            swap(t[i],t[i+1]);

            if(!vis.count(t))
            {
                vis.insert(t);
                q.push({t,step+1});
            }
        }
    }

    return -1;
}

int main()
{
    string a,b;
    cin >> a >> b;
    cout << bfs(a,b);
}

3. 考试重点

  这里我梳理一下考试的重点和老师大概率不会考的部分（仅供参考）

复习建议📝

1. 伪代码

一、 什么是伪代码？

二、 在算法题中如何规范书写伪代码？

1. 标题与输入输出声明

2. 变量与赋值

3. 控制流（关键字大写）

4. 数组与对象引用

5. 注释

三、 实战示例：二分查找（Binary Search）

四、 面试/笔试中的避坑指南

2. 算法模板

2.1 回溯算法（Backtracking）

2.2 泛洪算法（Flood Fill）

2.3 BFS（广度优先搜索）

2.4 DFS（深度优先搜索）

2.5 Dijkstra 算法

2.6 A* 算法

2.7 状态空间搜索

3. 考试重点

一、什么是伪代码？

二、在算法题中如何规范书写伪代码？

三、实战示例：二分查找（Binary Search）

四、面试/笔试中的避坑指南