软考软件设计师下午真题-算法分析与设计-动态规划法（2021年下半年试题四）C代码讲解说明C代码

说明

生物学上通常采用编辑距离来定义两个物种DNA序列的相似性，从而刻画物种之间的进化关系。
具体来说，编辑距离是指将一个字符串变换为另一个字符所需要的最小操作次数。操作有三种，分别为：插入一个字符、删除一个字符以及将一个字符修改为另一个字符。
用字符数组str1和str2分别表示长度为len1和len2的字符串，定义二维数组d记录求解编辑距离的子问题最优解，则该二维数组可以递归定义为：

C代码

（1）常量和变量说明
A，B：两个字符数组
d：二维数组
i，j：循环变量
temp：临时变量
（2）C程序

#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;	//返回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;	//对应第1个递归定义式
	}
	for (j = 0; j<=len2; j ++ ) {
		d[0][j]=j;	//对应第2个递归定义式
	}
	for (i=1; i<=len1; i ++ ) {
		for (j=1; j<=len2; j ++ ) {
			if (str1[i–1]==str2[j–1]) {	//str1的第i个和str2的第j个字符相等，但数组的下标从0开始，需要减1
				d[i][j]=d[i-1][j-1];	//第i个和第j个字符相等，不需要变换，只需要看前i-1个字符变换为前j-1个字符的编辑距离
			} else {	//str1的第i个和str2的第j个字符不相等
				temp=min(d[i-1][j]+1, d[i][j-1]+1);	//删除与插入两者取最小值
				d[i][j]=min(temp, d[i–1][j–1]+1);	//删除、插入与修改三者取最小值
			}
		}
	}
	return d[len1][len2];	//返回结果
}

最后

以上就是神勇唇彩为你收集整理的软考软件设计师下午真题-算法分析与设计-动态规划法（2021年下半年试题四）C代码讲解说明C代码的全部内容，希望文章能够帮你解决软考软件设计师下午真题-算法分析与设计-动态规划法（2021年下半年试题四）C代码讲解说明C代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。