软件设计师_算法——下午题(第四题)

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

回溯法(N皇后问题)

19年上半

软件设计师_算法——下午题(第四题)

软件设计师_算法——下午题(第四题)

软件设计师_算法——下午题(第四题)

软件设计师_算法——下午题(第四题)

软件设计师_算法——下午题(第四题)

软件设计师_算法——下午题(第四题)

软件设计师_算法——下午题(第四题)

解析:分析题干:queen[i]表示第i个皇后的位置,表示第i个皇后放置在第i行的第queen[i]列

(1):queen[i]==queen[j];这里的需求是检查已摆放的皇后是否在同一列或者是同一斜线上,||后面的abs(queen[i]-queen[j]==(j-i))查看已摆放的皇后是否在同一斜线上,代码的意思是,第i个皇后的列与第j个皇后的列的绝对值是否等于第j个皇后的行与第i个皇后的行的差值,相等的话就是在同一斜线;
要查看是否在同一列只需要查看第i个皇后的列是否等于第j个皇后的列;

(2):1;注释上说检查当前列是否能放置皇后,不能放返回0,能放返回1;

(3):Place(j);要调用一下上面的plase方法来看当前位置是否可以摆放;

(4):Nqueen(j+1);摆放下一个皇后的话就要递归调用一下当前方法Nqueen,也就是回溯;

软件设计师_算法——下午题(第四题)

解析:(5):回溯法

软件设计师_算法——下午题(第四题)

解析:(6):2 ;(7):(2,4,1,3)(3,1,4,2)

分治法

20年上半

软件设计师_算法——下午题(第四题)

软件设计师_算法——下午题(第四题)

#include<stdio.h>

void shellsort(int data[],int n){
    int *delta,k,i,t,dk,j;
    k=n;
    delta=(int *)malloc(sizeof(int) * (n/2));
    
    i=0;
    do{
        --(1)--;
        delta[i++]=k;
	}while(--(2)--);
    
    i=0;
    while((dk=delta[i])>0){/*步长赋值给了dk*/
        for(k=delta[i];k<n;++k)
            if(--(3)--){/*data[k-dk]>data[k]*/
                t=data[k];
                for(j=k-dk;j>=0&&t<data[j];j-=dk)
                    data[j+dk]=data[j];
                --(4)--;/*data[j+dk]=t*/
            }
        ++i;
    }
}

软件设计师_算法——下午题(第四题)

解析:(1):k/=2或k=k/2;后一个增量是前一个增量的二分之一,每循环一次就让k除以2,再把k赋值给data[i];
(2):k>1;因为步长序列除到最后是1,所以while循环的条件就是k>1;

软件设计师_算法——下午题(第四题)

(3):data[k-dk]>data[k]
(4):data[j+dk]=t

软件设计师_算法——下午题(第四题)

解析:(5):小于;希尔排序时间复杂度平均O(n1.3),最好O(n),最坏O(n2);

(6):

软件设计师_算法——下午题(第四题)

软件设计师_算法——下午题(第四题)

解析:(7):(4,9,-1,8,20,7,15)

动态规划(背包问题)

21年下半

软件设计师_算法——下午题(第四题)

#include<stdio.h>
#define N 100

char A[N]="CTGA";
char B[N]="ACGCTA";
int d[N][N];

int min(int a,int b){
    	return a<b?a:b;
}

int editdistance(char *str1,int len1,char *str2,int len2){
    int i,j;
    int diff;
    int temp;
    
    for(i=0;i<=len1;i++){
        d[i][0]=i;
    }
    
    for(j=0;j<=len2;j++){
        --(1)--;
    }
    
    for(i=1;i<=len1;j++){
        for(j=1;j<=len2;j++){
            if(--(2)--){
                d[i][j]=d[i-1][j-1];
            }else{
                temp=min(d[i-1][j]+1,d[i][j-1]+1);
                d[i][j]=min(temp,--(3)--);
            }
        }
	}
    return --(4)--
}

软件设计师_算法——下午题(第四题)

软件设计师_算法——下午题(第四题)

软件设计师_算法——下午题(第四题)

答案:(1):data[0][j]==j
(2):str1[i-1]==str2[j-1]
(3):d[i-1][j-1]+1
(4):d[len1][len2](图中打错了)

软件设计师_算法——下午题(第四题)

软件设计师_算法——下午题(第四题)

解析:(5):动态规划;(6):O(m*n)

软件设计师_算法——下午题(第四题)

答案:(7):4文章来源地址https://www.toymoban.com/news/detail-477632.html

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

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

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

相关文章

  • 【中级软件设计师】—(针对上午题)算法分析与设计(三十八)

    1. 什么是回溯法? 相信\\\"迷宫\\\"是许多人儿时的回忆,大家小时候一定都玩过迷宫游戏。我们从不用别人教,都知道走迷宫的策略是: 当遇到一个岔路口,会有以下两种情况: 存在没走过的路。此时可以任意选一条没走过的路深入,只要记住我们所走过的路径即可。 倘若下次

    2024年02月02日
    浏览(43)
  • 【软件设计师06】数据结构与算法基础

    考点:数组与矩阵、 线性表 、广义表、 树与二叉树 、图、 排序与查找 、 算法基础与常见的算法 数组类型 存储地址计算 一维度数组a[n] a[i]的存储地址为a+i*len 二维数组a[m][n] a[i][j]的存储地址;按行存储:a+(i*n+j)*len;按列存储:a+(j*m+i)*len 采用上三角或者下三角的形式存储

    2023年04月11日
    浏览(38)
  • 软件设计师——软件工程(四)

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

    2024年01月24日
    浏览(50)
  • 系统架构设计师-软件架构设计(3)

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

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

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

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

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

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

    一、计算机系统 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日
    浏览(50)
  • 软件设计师笔记

    数据的表示、计算机结构、Flynn分类法、CISC与RISC、流水线技术、存储系统、总线系统、可靠性、校验码 1. 数据的表示 (一)进制转换 R进制转十进制使用按权展开法: 十进制转R进制使用短除法 二进制转八进制、16进制 原码、反码、补码、移码 正数的反码不变。负数的反码

    2024年02月02日
    浏览(47)
  • 软件设计师中级

    软件设计师中级考试 配套书地址 一、计算机组成原理 1、数据表示 2、校验码 3、计算机体系结构 4、指令系统 5、存储系统 6、总线系统 7、输入输出技术 8、可靠性 二、数据结构与算法 1、基本概念与三要素 2、算法 3、线性表 4、栈和队列 5、串、数组、矩阵和广义表 6、树和

    2024年02月07日
    浏览(45)
  • 【新版】系统架构设计师 - 软件架构设计<新版>

    个人总结,仅供参考,欢迎加好友一起讨论 软件架构的概念(★★★) 基于架构的软件开发(★★★★) 软件架构风格(★★★★★) 特定领域软件架构(★★★) 软件质量属性(★★★★★) 软件架构评估(★★★★★) 软件产品线(★★★) 构件与中间件技术(★

    2024年02月09日
    浏览(62)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包