软件设计师第4题

这篇具有很好参考价值的文章主要介绍了软件设计师第4题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

首先,我是备考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上半年 分治法--时间复杂度计算--算法结果推导

        其他博主总结的考点如下,参考看看就行了。

软件设计师第4题

二、动态规划法

2.1 算法介绍

2.2 题型1:

三、回溯法(n皇后问题)

3.1问题描述

八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是:在8×8的棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题,即在n×n的棋盘上摆放n个皇后,使任意两个皇后都不能处于同一行、同一列或同一斜线上。 

简而言之:n×n的棋盘上摆放n个皇后,不能同行,不能同列,也不能同斜线。

3.2回溯解法

首先这是一个排列组合问题,解空间的大小为:n!(n的阶乘)

如下图所示是解空间的构成树,又称排列树。

软件设计师第4题

 解法一:如果硬去罗列所有排列组合,然后进行判断。规模稍大就不行了,因为是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)

O(n*2)文章来源地址https://www.toymoban.com/news/detail-453831.html

O(m*n)

O(n*2)

到了这里,关于软件设计师第4题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 中级软件设计师备考---计算机组成与体系结构1

    对于n位二进制数,原码、反码和补码的表示范围如下: 原码:用最高位表示符号位,0表示正数,1表示负数。n位二进制数的原码表示范围为:-(2 n-1 -1) ~ 2 n-1 -1。 反码:正数的反码与原码相同,负数的反码是将原码中除符号位外的所有位取反。n位二进制数的反码表示范围

    2023年04月09日
    浏览(56)
  • 中级软件设计师备考---计算机组成与体系结构3

    计算题 概念题 计算可靠度 码距:是指两个码字之间的不同位数。例如,1010和1111之间的码距是2,因为它们在第二位和第三位上不同。在信息传输中,码距越大,就越容易检测和纠正错误。 在一个码组内为了检测e个误码,要求最小码距d应满足:d=e+1 在一个码组内为了纠正

    2023年04月15日
    浏览(42)
  • 2023年软件设计师上午试题及参考答案

    加粗为参考答案,不一定能全对 (考试时间9:00~11:30共150分钟) 请按下述要求正确填写答题卡 1.在答题卡的指定位置上正确填写你的姓名和准考证号,并粘贴考生条形码。 2.本试卷的试题中共有75个空格,需要全部解答,每个空格1分,满分75分。 3.每个空格对应一个序号,有

    2024年02月07日
    浏览(68)
  • 系统架构设计师考试备考精简版(23年)!

    2023 年系统架构设计师教材已经更新到第二版,新教材移除了 UML 和 设计模式章节,加入了架构设计理论与实践部分,对于大家来说好消息是 UML 和设计模式不用再去看了。坏消息是案例、论文难度应该会加大。这是因为新版本下篇加了很多实际场景的架构分析题,很适合在案

    2024年02月11日
    浏览(40)
  • 软件设计师——软件工程(四)

    本文主要是【软件工程】——软件设计师——软件工程的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是听风与他🥇 ☁️博客首页:CSDN主页听风与他 🌄每日一句:狠狠沉淀,顶峰相见 21.某开发小组欲为一公司开发一个产品控制软件,监控

    2024年01月24日
    浏览(48)
  • 【软考】2023系统架构设计师考试

    目录 1 软考资格设置❤️ 2 考试介绍❤️ 3 考试报名❤️ 4 考试准备❤️ 5 参加考试❤️ 6 考试感受❤️ 7 其他❤️ (1)考试科目和通过标准 注意:2023年下半年有变化。 高级 资格: 综合知识科目考试时长150分钟,最短作答时长120分钟,考试结束前30分钟可交卷离场。 案例

    2024年02月13日
    浏览(52)
  • 系统架构设计师-软件架构设计(7)

    目录 大型网站系统架构演化 一、第一阶段:单体架构 到 第二阶段:垂直架构 二、第三阶段:使用缓存改善网站性能         1、缓存与数据库的数据一致性问题         2、缓存技术对比【MemCache与Redis】         3、Redis分布式存储方案         4、Redis集群切片的

    2024年02月14日
    浏览(68)
  • 系统架构设计师-软件架构设计(3)

    目录 一、软件架构风格(其它分类)         1、闭环控制结构(过程控制)           2、C2风格         3、MDA(模型驱动架构 Model Driven Architecture)         4、特定领域软件架构(DSSA)                 4.1 DSSA基本活动及产出物:             

    2024年02月15日
    浏览(58)
  • 系统架构设计师-软件架构设计(6)

    目录 一、物联网分层架构 二、大数据分层架构 三、基于服务的架构(SOA)         1、SOA的特征         2、服务构件与传统构件的区别 四、Web Service(WEB服务)         1、Web Services 和 SOA的关系 五、REST(表述性状态转移) 六、ESB(企业服务总线) 七、微服务         1、微

    2024年02月14日
    浏览(248)
  • 软考-软件设计师

    一、计算机系统 1.1 CPU的功能有: 1.2 运算器的组成 1.3 控制器——不仅要保证程序的正确执行、还要能够处理异常事件 1.3.1 指令控制逻辑 1.4 计算机基本单位 1.5 进制的变换 1.5.1 进制加减法 1.6 原码、反码、补码、移码 1.7 浮点数 1.8 寻址 1.9 校验码 1.10 RISC、CISC 1.11 流水

    2024年02月05日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包