首先,我是备考2023年上半年的考试。
一、历年考试题
历年的考题如下,从表中分析可以看出,动态规划法、排序算法、回溯法、分治法是很大概率考察的算法,尤其是动态规划法,本身其理解难度较高,且可以出的题型很多。
我猜测,2023年上半年很有可能就是出动态规划法。其次就是回溯法和分治法。回溯法学习n皇后问题就行了。
年份 | 考点 |
2022下半年 | 堆排序算法--时间复杂度计算--排序结果推导 |
2022上半年 | 动态规划算法(矩阵乘法)--时间复杂度计算--算法结果推导 |
2021下半年 | 动态规划算法--时间复杂度计算--算法结果推导 |
2021上半年 | 动态规划算法--时间复杂度计算--空间复杂度计算 |
2020下半年 | 希尔排序--时间复杂度/是否稳定--算法结果推导 |
2020上半年 | (疫情原因取消) |
2019下半年 | 动态规划算法(0-1背包问题) --自底向上或自顶向下 --算法结果推导 |
2019上半年 | 回溯法(n皇后问题)--算法结果推导 |
2018下半年 | 动态规划算法--时间复杂度计算--算法结果推导 |
2018上半年 | 动态规划算法/递归算法--时间复杂度计算 |
2017下半年 | 回溯法 |
2017上半年 | 分治法--时间复杂度计算--算法结果推导 |
2016下半年 | KMP算法--时间复杂度计算--算法结果推导 |
2016上半年 | 动态规划算法--时间复杂度计算--算法结果推导 |
2015下半年 | 动态规划算法--时间复杂度计算--算法结果推导 |
2015上半年 | 回溯法(n皇后问题)--算法结果推导 |
2014下半年 | 动态规划算法--时间复杂度计算--算法结果推导 |
2014上半年 | 分治法--时间复杂度计算--算法结果推导 |
其他博主总结的考点如下,参考看看就行了。
二、动态规划法
2.1 算法介绍
2.2 题型1:
三、回溯法(n皇后问题)
3.1问题描述
八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是:在8×8的棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题,即在n×n的棋盘上摆放n个皇后,使任意两个皇后都不能处于同一行、同一列或同一斜线上。
简而言之:n×n的棋盘上摆放n个皇后,不能同行,不能同列,也不能同斜线。
3.2回溯解法
首先这是一个排列组合问题,解空间的大小为:n!(n的阶乘)
如下图所示是解空间的构成树,又称排列树。
解法一:如果硬去罗列所有排列组合,然后进行判断。规模稍大就不行了,因为是n!的问题规模。
解法二:采用回溯法,对排列树进行搜索,在中途就发现不行时,直接退出该路线,回溯到上一步,相当于在剪枝。
举个例子:
4皇后问题:
先将第一个皇后放在第一行的第一列上,符合题目要求
开始放置第二个皇后。放在第二行的第一个与第一行的皇后为同一列,不符合题意,继续向后搜素,放在第二列上面与第一个皇后在同一斜线上,不符合题意,继续向后搜素,发现放在第三列符合题意
开始放置第三个皇后。放在第三行的任意位置都会出现冲突,此时需要回溯,将第二个皇后放置在第四列,此时符合题意,继续放置第三个皇后,发现第三个皇后放置在第三行的第二列符合题意
继续放置第四个皇后。放在第四行的任意位置都会出现冲突,此时需要回溯,第三个皇后向后移动,发现依然不符合题意,继续回溯,第二行的皇后无法再向后移动,继续回溯,将第一个皇后向后移动到第二列,符合题意
移动第二个皇后,发现放在第四列符合题意
移动第三个皇后,发现放在第一列符合题意
移动第四个皇后,发现放在第三列符合题意
回溯结束
3.3源码
3.3.1 递归方法
重点是进行冲突检测:
1、摆当前棋子是在某行中选一个位置,行冲突是没有的。
2、列冲突:queenPos[j] == i;
3、斜线冲突:abs(queenPos[j] - i) == abs(k - j)。由于棋盘是方块,当前棋子与之前放置棋子的行差与列差相同说明在一条斜线上。
其中的变量:
i是当前行放置位置;
j是搜索queenPos数组已经放置的棋子(范围从第1个棋子到当前棋子k);
k是当前放第几个棋子。
#include<iostream>
using namespace std;
const int M = 100;
int N;
int queenPos[M];//存放皇后的摆放位置
int sum = 0;//记一共有多少种解决方案
void display()//《《不是必须的》》,用来图形化输出结果,@表示皇后
{
int i, j;
int k;
cout << endl;
sum++;
for (i = 0; i < N; i++)
{
cout << " ";
for (k = 0; k < N; k++)
{
cout << "---";
}
cout << endl;
for (j = 0; j < N; j++)
{
if (j == queenPos[i])
{
cout << "| ";
cout << "@";
}
else
{
cout << "| ";
cout << ".";
}
}
cout << " |"<<endl;
}
cout << " ";
for (i = 0; i < N; i++)
{
cout << "---";
}
cout << "\n"<<endl;
}
void NQueen(int k)
{
//跳出条件,已经搜索到N皇后的第N行了。
if (k == N)//N个皇后已经全部摆好
{
cout << N << "皇后的摆放位置是:";
for (int i = 0; i < N; i++)
{
cout << queenPos[i] + 1 << " ";
}
cout << endl;
cout << "图解如下:" << endl;
display();
return;
}
//主要搜索过程
for (int i = 0; i < N; i++)//在一行中逐个检测每个位置
{
int j;
for (j = 0; j < k; j++)//和语句摆好的前几个皇后进行冲突检测
{
if (queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j))
{
break;//发生冲突,则检测下一个位置
}
}
if (j == k)//搜到最后都没有break,说明该位置不与前面的皇后发生冲突,添加该位置
{
queenPos[k] = i;//将第k个皇后放在第i的位置上
NQueen(k + 1);//搜下一个皇后的摆放位置
}
}
}
int main()
{
cin >> N;
NQueen(0);//摆放第0个皇后
cout <<N<<" 皇后的解决方案有 "<< sum << " 种"<<endl;;
return 0;
}
3.3.2 非递归方法
3.4 时间复杂度
该算法中每个皇后都要试探n列,共n个皇后,其解空间是一棵子集树,每个结点可能有n棵子树,对应的算法时间复杂度为 O(n^n)
利用显示约束排除两个皇后在同一行或同一列的方法,解空间树就是一棵排列树,因此共有n ! n!n!个叶子结点,所以算法的时间复杂度可以降为O ( n ! )
常见算法 | 时间复杂度 | 空间复杂度 |
哈希搜索 | O(1) — 常数复杂度 | |
二分搜索 | O(log n) — 对数复杂度 |
|
回溯法--N皇后问题 | O(n*2^n) — 线性复杂度 | |
动态规划法--矩阵乘法 | O(n*3) | O(n*2) |
动态规划法--0-1背包问题 | O(m*n) | / |
动态规划法--跳台阶问题 | O(n) | O(n) |
动态规划法--最短路径问题 | O(n*2) | O(n) |
分治法 | O(n*log n) | O(n) |
贪心算法 | O(m*n)文章来源:https://www.toymoban.com/news/detail-453831.html O(n*2)文章来源地址https://www.toymoban.com/news/detail-453831.html |
O(m*n) O(n*2) |
到了这里,关于软件设计师第4题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!