递归算法实例应用(一)

简介: 递归算法实例应用(一):简单Hanoi 问题、N Queens问题。

递归算法实例应用(一)

递归简笔

递归和普通函数调用一样,都是通过函数栈实现。

以斐波那契数列递归调用为例

斐波那契数列函数递归次序.png

递归时函数调用栈的进栈、出栈过程可以由上述图示直观的体现出来,

因此可以得出递归的几个作用:

​ 1)替代多重循环

​ 2)解决以递归形式或潜在以递归形式定义的问题

​ 3)将问题规模分解,分解为规模更小的子问题进行求解

​ ... ... ...


Hanoi (Simple)

Description

古代有一座汉诺塔,塔内有3个座A、B、C,A座上有n个盘子,盘子大小不等,大的在下,小的在上。有一个和尚想把这n个盘子从A座移到C座,但每次只能移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。在移动过程中可以利用B座来放盘子。要求输出移动的步骤。

Input

汉诺塔内的盘子个数n(1 ≤ n ≤ 64)。

Output

输出移动的步骤,每行一步,如从A座移动到C座,输出“A->C”。

Sample Input

3

Sample Output

A->C
A->B
C->B
A->C
B->A
B->C
A->C

这是最简单的Hanoi问题,其余进阶版的Hanoi问题均由此发展而来。

该题是一个非常明显的以递归形式定义的问题,即:

要把A座上的盘子移动到C座的问题分解为三步:

  1. 把A座上的n-1个盘子移动到B座作为中转,且以C座作为中转;
  2. 把A座剩余的一个盘子移动到C座;
  3. 再把B座的n-1个盘子移动到C座,且以A做作为中转。

这样就把原问题的规模减小至n-1,通过逐层递归可以将问题规模减少至1,此时就可以通过直接将A座盘子移动到C座完成,在逐步向上返回至上一层调用函数,直至问题规模n完成求解。

由上述分析显然可知,当问题规模减少至1时为终止条件,此时应将A座盘子移动到C座上,即输出A->C,同时结束本次递归,返回至上一层递归函数处。

所以主函数及递归段代码为:

void Hanoi(int n, char A, char B, char C) {
    if (n == 1) {//问题规模到达1时为递归终止条件
        printf("%c->%c\n", A, C);
        return;
    }
    //将A座n-1个盘子移动至B座,同时以C座作为中转
    Hanoi(n - 1, A, C, B);
    //将A座第n个盘子移动至C座
    printf("%c->%c\n", A, C);
    //将B座的n-1个盘子移动至C座,同时以A座作为中转
    Hanoi(n - 1, B, A, C);
}

int main() {
    int n;
    scanf("%d",&n);
    //将n层汉诺塔中A座移动到C座,同时以B座作为中转
    Hanoi(n, 'A', 'B', 'C');
}

N Queens

Description

The eight queens puzzle is the problem of putting eight chess queens on an 8 × 8 chessboard such that none of them is able to capture any other. The puzzle has been generalized to arbitrary n × n boards. Given n, you are to find a solution to the n queens puzzle.

Input

The input contains multiple test cases. Each test case consists of a single integer n between 8 and 300 (inclusive). A zero indicates the end of input.

Output

For each test case, output your solution on one line. The solution is a permutation of {1,2,...,n }. The number in the ith place means the ith-column queen in placed in the row with that number.

Sample Input

4

Sample Output

2 4 1 3
3 1 4 2

为方便理解题意,依样例输入输出可以画出四皇后图例:

img

题中要求皇后不能在同一行、同一列、同一对角线。

不难想到可以通过枚举所有可能的皇后状态来暴力求解,比如当 N = 4 时,可以通过4重循环嵌套来实现枚举。

但是该问题的问题规模N是一个不确定是整数,N重循环嵌套就无法实现,所以可以考虑采用递归来替代多重循环。

分析至此,本题的递归又自然而然的引出了回溯法这一基本算法理念,当不断的枚举每一种可能的状态时,若发生了与规则矛盾的错误,则应立即终止本层递归,回溯至上层,进行下一状态的枚举。

准备工作:

而如何枚举全每一种可能的状态,有多种方法,如按行枚举、按列枚举、按对角线枚举等,本文采用按行枚举进行操作。所以递归函数的形参就呼之欲出:int n,因为我们假定递归模型是按行进行枚举的,所以n用于表示0~n-1行皇后已经摆好,当前递归函数为处理第n行皇后的位置。

所以应再设置一个PosOfQueen的一维数组,其下标表示棋盘的第i行,其值PosOfQueen[i]表示第i行皇后摆放在第几列,如PosOfQueen[2]=4,表明第2行(棋盘的第3行)皇后摆放第4列(棋盘的第五列)。


算法逻辑:

其中,NofQueen表示N皇后中的规模N

  1. 若本层递归参数n==NofQueen,即表明N皇后已经摆放正确,所以此时为该问题的递归终止条件,应输出问题的一个解。

    代码描述为:

    if (n == NofQueen) {//N个皇后已经摆好
        for (i = 0; i < NofQueen; ++i) {
            printf("%d ", PosOfQueen[i] + 1);//输出每一行皇后摆在哪一列
        }
        printf("\n");
        return;
    }
  2. 若本层递归不为第N行,则应处理第n行的皇后,即确定第n行皇后的摆放位置。所以应从0~NofQueen-1枚举所有可能的摆放位置。假设以i枚举时行递增变量

    枚举时,首先,与前0~n-1行已经确定位置的n个元素进行比较,判断是否同行、同列、同对角线

    • 同行判定:由于是按行遍历每行确定一个元素的位置,所以不可能有元素是同行。
    • 同列判定:PosOfQueen[j]数组的值表明第j行皇后摆放在第几列,所以同列判断较为简单,代码描述为:

      PosOfQueen[j] == i
    • 同对角线判定:

      j=1 j=2 j=3 j=4
      i=1 (1,1) (1,2) (1,3) (1,4)
      i=2 (2,1) (2,2) (2,3) (2,4)
      i=3 (3,1) (3,2) (3,3) (3,4)
      i=4 (4,1) (4,2) (4,3) (4,4)

      上表描述为4*4的棋盘,其中

      1. 主对角线

        • 主对角线1:(1,1)、(2,2)、(3,3)、(4,4)
        • 主对角线2:(1,2)、(2,3)、(3,4)
        • 主对角线3:(2,1)、(3,2)、(4,3)
        • 主对角线4:(1,3)、(2,4)
        • 主对角线x: ...、...

          观察发现,每一个主对角线上各个元素的行列下标差的绝对值均相等,即|i-j|均相等。

          如:主对角线2中,|1-2|=|2-3|=|3-4|=1

          ​ 主对角线3中,|2-1|=|3-2|=|4-3|=1

      2. 副对角线

        • 副对角线1:(1,4)、(2,3)、(3,2)、(4,1)
        • 副对角线2:(1,3)、(2,2)、(3,1)
        • 副对角线3:(2,4)、(3,3)、(4,2)
        • 副对角线4:(1,2)、(2,1)
        • 副对角线x: ...、...

          观察发现,每一个副对角线上各个元素的行列下标之和均相等。即i+j均相等。

          如:副对角线2中,1+3=2+2=3+1=4。

          ​ 副对角线3中,2+4=3+3=4+2=6。

    综上所述,可将同行(忽略)、同列、同主副对角线判定代码合并为:

    if (PosOfQueen[j] == i || abs(PosOfQueen[j] - i) == abs(n - j)) {
        //同行不必判断,判断是否同列、同主对角线、同副对角线。
        break;//规则冲突,测试下一可能位置,再通过剪枝来减少不必要的开销
    }

    其次,若与前0~n-1行判断是否同行、同列、同对角线完成后,与题目规则不冲突,则将第n行皇后摆放在当前枚举状态下的的可能位置i处,随后进行下一行皇后位置的确定,即进入下一层递归中。

    代码描述如下:

    if (j == n) {//当前轮次枚举中位置i与前0~n-1行合法性判断均通过,当前位置合法
        PosOfQueen[n] = i;//将第n个皇后摆放在位置i
        NQueen(n + 1);//递归调用函数,处理n+1行皇后位置摆放问题
    }
  3. 至此,递归函数已经完成,在递归函数中,第一步中的if语句为递归终止点,同时也是回溯法成功找到解时的判定条件。在第二步中,通过逐步尝试每一个可能位置的,并通过回溯保证本次递归是在上一层递归函数正确的条件下进行的枚举尝试,不断穷尽解集二叉树中的所有分支。

代码整合:

综上,代码可整合为:

void NQueen(int n) {//在0~n-1行的皇后已经摆好的情况下,摆第n行及其之后的皇后
    int i, j;
    if (n == NofQueen) {//N个皇后已经摆好
        for (i = 0; i < NofQueen; ++i) {
            printf("%d ", PosOfQueen[i] + 1);//输出每一行皇后摆在哪一列
        }
        printf("\n");
        return;
    }
    for (i = 0; i < NofQueen; ++i) {
        for (j = 0; j < n; ++j) {//每一轮for循环均回溯至i行处,因此可以穷尽所有可能解的二叉树的叶子结点
            if (PosOfQueen[j] == i || abs(PosOfQueen[j] - i) == abs(n - j)) {
                //同行不必判断,判断是否同列、同主对角线、同副对角线。
                break;//规则冲突,test next pos  再通过剪枝来减少不必要的开销
            }
        }
        if (j == n) {//与前0~n-1行合法性判断均通过,当前位置合法
            PosOfQueen[n] = i;//将第n个皇后摆放在位置i
            NQueen(n + 1);//递归调用函数,处理n+1行皇后位置摆放问题
        }
    }
}

int NofQueen;           //N皇后的N
int PosOfQueen[100];    //棋盘数组,下标表示行号,值表示列号

int main() {
    scanf("%d", &NofQueen);
    NQueen(0);//从棋盘第0层开始逐层递归解决
}
                          by Ss1Two 2023/01/12
目录
相关文章
|
2月前
|
存储 监控 JavaScript
基于布隆过滤器的 Node.js 算法在局域网电脑桌面监控设备快速校验中的应用研究
本文探讨了布隆过滤器在局域网电脑桌面监控中的应用,分析其高效空间利用率、快速查询性能及动态扩容优势,并设计了基于MAC地址的校验模型,提供Node.js实现代码,适用于设备准入控制与重复数据过滤场景。
92 0
|
22天前
|
运维 监控 JavaScript
基于 Node.js 图结构的局域网设备拓扑分析算法在局域网内监控软件中的应用研究
本文探讨图结构在局域网监控系统中的应用,通过Node.js实现设备拓扑建模、路径分析与故障定位,提升网络可视化、可追溯性与运维效率,结合模拟实验验证其高效性与准确性。
145 3
|
1月前
|
机器学习/深度学习 资源调度 算法
遗传算法模型深度解析与实战应用
摘要 遗传算法(GA)作为一种受生物进化启发的优化算法,在复杂问题求解中展现出独特优势。本文系统介绍了GA的核心理论、实现细节和应用经验。算法通过模拟自然选择机制,利用选择、交叉、变异三大操作在解空间中进行全局搜索。与梯度下降等传统方法相比,GA不依赖目标函数的连续性或可微性,特别适合处理离散优化、多目标优化等复杂问题。文中详细阐述了染色体编码、适应度函数设计、遗传操作实现等关键技术,并提供了Python代码实现示例。实践表明,GA的成功应用关键在于平衡探索与开发,通过精心调参维持种群多样性同时确保收敛效率
|
1月前
|
机器学习/深度学习 边缘计算 人工智能
粒子群算法模型深度解析与实战应用
蒋星熠Jaxonic是一位深耕智能优化算法领域多年的技术探索者,专注于粒子群优化(PSO)算法的研究与应用。他深入剖析了PSO的数学模型、核心公式及实现方法,并通过大量实践验证了其在神经网络优化、工程设计等复杂问题上的卓越性能。本文全面展示了PSO的理论基础、改进策略与前沿发展方向,为读者提供了一份详尽的技术指南。
粒子群算法模型深度解析与实战应用
|
1月前
|
机器学习/深度学习 算法 安全
小场景大市场:猫狗识别算法在宠物智能设备中的应用
将猫狗识别算法应用于宠物智能设备,是AIoT领域的重要垂直场景。本文从核心技术、应用场景、挑战与趋势四个方面,全面解析这一融合算法、硬件与用户体验的系统工程。
|
3月前
|
机器学习/深度学习 人工智能 算法
AI-Compass 强化学习模块:理论到实战完整RL技术生态,涵盖10+主流框架、多智能体算法、游戏AI与金融量化应用
AI-Compass 强化学习模块:理论到实战完整RL技术生态,涵盖10+主流框架、多智能体算法、游戏AI与金融量化应用
|
3月前
|
机器学习/深度学习 人工智能 自然语言处理
深度学习模型、算法与应用的全方位解析
深度学习,作为人工智能(AI)的一个重要分支,已经在多个领域产生了革命性的影响。从图像识别到自然语言处理,从语音识别到自动驾驶,深度学习无处不在。本篇博客将深入探讨深度学习的模型、算法及其在各个领域的应用。
579 3
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
88 1
|
2月前
|
算法 数据可视化
matlab版本粒子群算法(PSO)在路径规划中的应用
matlab版本粒子群算法(PSO)在路径规划中的应用
|
3月前
|
存储 监控 算法
公司员工泄密防护体系中跳表数据结构及其 Go 语言算法的应用研究
在数字化办公中,企业面临员工泄密风险。本文探讨使用跳表(Skip List)数据结构优化泄密防护系统,提升敏感数据监测效率。跳表以其高效的动态数据处理能力,为企业信息安全管理提供了可靠技术支持。
88 0

热门文章

最新文章