回溯法(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);
文章来源:https://www.toymoban.com/news/detail-477632.html
答案:(7):4;文章来源地址https://www.toymoban.com/news/detail-477632.html
到了这里,关于软件设计师_算法——下午题(第四题)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!