重启数据结构与算法5

[Ray-56]

重启数据结构与算法5

重启数据结构与算法，一些代码案例使用 Deno 与 TypeScript 实现，相关代码都在这里

1. 重启数据结构与算法1
2. 重启数据结构与算法2
3. 重启数据结构与算法3
4. 重启数据结构与算法4
5. 重启数据结构与算法5

递归

递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。 ----维基百科

解决问题：

• 各种数学问题、汉诺塔、阶乘、球和篮子
• 算法中的快排、归并、二分、分治
• 栈解决 => 递归解决，代码更加简洁

注意点：

• 局部变量，不会相互影响
• 引用类型，就会共享
• 向退出条件逼近，否则进入死循环
• 使用尾调用优化

迷宫回溯

给定一个迷宫，指明起点和终点，找出从起点出发到终点的有效可行路径，就是迷宫问题

为了方便我们定义一些规则：

• 使用8 x 7的网格
• 数字表示：
  • 0：没走过
  • 1：墙
  • 2：通路可以走
  • 3：已走过，不通
• 起始点[1][1]，终点[6][5]
• 指定策略，下 -> 右 -> 上 -> 左

先将最终结果放上来

class MiGong {
    public map: number[][] = Array(8)
        .fill(0)
        .map(() => Array(7).fill(0));
    constructor() {
        // 构造墙
        for (let i = 0; i < 7; i++) {
            this.map[0][i] = 1;
            this.map[7][i] = 1;
        }
        for (let i = 0; i < 8; i++) {
            this.map[i][0] = 1;
            this.map[i][6] = 1;
        }
        // 设置挡板
        this.map[3][1] = 1;
        this.map[3][2] = 1;
    }
    /**
     * 设置道路
     * @param map
     * @param i
     * @param j
     */
    public static setWay(map: number[][], i: number, j: number): boolean {
        // [6][5] 为 2 的时候就是走到了终点
        if (map[6][5] === 2) return true;
        // 未走过，就按照策略开始走
        if (map[i][j] == 0) {
            map[i][j] = 2; // 假定可以通
            if (this.setWay(map, i + 1, j)) { // 向下
                return true;
            } else if (this.setWay(map, i, j + 1)) { // 向右
                return true;
            } else if (this.setWay(map, i - 1, j)) { // 向上
                return true;
            } else if (this.setWay(map, i, j - 1)) { // 向左
                return true;
            } else {
                // 都无法走，说明是死路
                map[i][j] = 3;
                return false;
            }
        } else {
            // map[i][j] !== 0, 可能为 1，2，3 。
            return false;
        }
    }
}

window.onload = function main() {
    const miGong = new MiGong();
    console.table(miGong.map);
    MiGong.setWay(miGong.map, 1, 1);
    console.table(miGong.map);
};

八皇后问题

八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

理论上我们需要8*8的二维数组，但是实际情况我们用一维数组array[index] = value也可以表示，数组的index + 1表示列，value表示行

class Queen8 {
    private max = 8;
    public count = 0;
    private array = Array(this.max).fill(0);
    /** 输出每次的正解 */
    private print() {
        console.log(...this.array);

        this.count++;
    }
    /** 检查该位置是否可以放置 */
    private judge(n: number): boolean {
        for (let i = 0; i < n; i++) { // 因为每次的 i 都不相同，所以不需要判断是否同行
            if (
                this.array[i] === this.array[n] // 判断同列
                || Math.abs(n - i) === Math.abs(this.array[n] - this.array[i]) // 判断斜线，与设置的数据结构有关，使用二维数组此表达式不适用
            ) {
                return false;
            }
        }
        return true;
    }
    public check(n: number) {
        if (n === this.max) { // 表示已放好
            this.print();
            return;
        }
        for (let i = 0; i < this.max; i++) {
            this.array[n] = i; // 先放在第一列
            if (this.judge(n)) { // 条件不满足时，进入下个循环
                // 当前位置可以放入，进入下一个找可以放入的位置
                this.check(n + 1);
            }
        }
    }
}

window.onload = function main() {
    const q = new Queen8();
    q.check(0);
    console.log(`共有${q.count}种解法`);
}

下期预告

• 排序