请在下方输入要搜索的题目：

字符串比较问题问题描述：对于长度相同的2个字符串A和B，其距离定义为相应位置字符距离之和。2个非空格字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0，空格与其它字符的距离为一定值k。在一般情况下，字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中，有一对距离最小的扩展，该距离称为字符串A和B的扩展距离。对于给定的字符串A和B，试设计一个算法，计算其扩展距离。编程任务：对于给定的字符串A和B，编程计算其扩展距离。数据输入：由文件input.txt给出输入数据。第1行是字符串A，第2行是字符串B，第3行是空格与其它字符的距离定值k。结果输出：将计算出的字符串A和B的扩展距离输出到文件output.txt。输入文件示例输出文件示例input.txt output.txtcmc 10snmn2

字符串比较问题问题描述：对于长度相同的2个字符串A和B，其距离定义为相应位置字符距离之和。2个非空格字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0，空格与其它字符的距离为一定值k。在一般情况下，字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A和B的所有长度相同的扩展中，有一对距离最小的扩展，该距离称为字符串A和B的扩展距离。对于给定的字符串A和B，试设计一个算法，计算其扩展距离。编程任务：对于给定的字符串A和B，编程计算其扩展距离。数据输入：由文件input.txt给出输入数据。第1行是字符串A，第2行是字符串B，第3行是空格与其它字符的距离定值k。结果输出：将计算出的字符串A和B的扩展距离输出到文件output.txt。输入文件示例输出文件示例input.txt output.txtcmc 10snmn2

发布时间：2025-03-27 23:49:17

推荐参考答案 ( 由快搜搜题库官方老师解答 )

联系客服

答案：设字符串A和B的字串A[1...i]和B[1...j]的扩展距离是val(i, j)；依题意，字符串A和B有三种可能的情况：1）A串最后一个字符是空格，B串最后一个字符是字母，则val(i, j) = val(i-1, j) k；2）A串最后一个字符时字母，B串最后一个字符时空格，则val(i, j) = val(i, j-1) k；3）A串和B串最后一个字符均是字母，则val(i, j) = val(i-1, j-1) dist(ai , bi)；由上可知，val(i, j)具有最优子结构性质，且满足如下递推式：val(i, j) = min{ val(i-1, j) k，val(i, j) k，val(i-1, j-1) dist(ai , bi) }（使用动态规划算法，自底向上的计算各个子问题并利用每次计算的结果，避免重复运算，从而降低算法复杂度。）从动态规划递归式可知，算法的时间复杂度为O（mn），m和n分别是字符串A和B的长度。代码如下：#include #include #define MAX 100000 //标识最大的可能整数int val[300][300];std::string stra; //字符串Astd::string strb; //字符串Bint k; //定值k//返回字符a与b的ASCII码的差的绝对值int dist(char a, char b){return abs(a-b);}int comp(){int len1, len2;int tmp;val[0][0] = 0;len1 = stra.length();len2 = strb.length();for(int i=0; i<=len1; i ) //字符串A和B的有效下标是º1~len,下标0表示空字符串{ //i或j是0表示A或B串为空串for(int j=0; j<=len2; j ){if(i j)//i和j至少一个大于0{val[i][j] = MAX;tmp = val[i-1][j] k;if(i && (tmp>stra>>strb>>k;stra = " " stra; //此处在字符串开头添加一个空格，是为了使字符串strastrb = " " strb; //的控制台输入的有效字符下标从1到stra.length()std::cout<

专业技术学习

相关试题

专业技术学习

搜搜题库系统

银行从业资格题库从业资格考试题库公务员考试常识题库普通话水平测试题库护士考试题库区域考试题库教师招聘考试题库题库资料常识题库及答案卫生职称考试题库无领导小组题库及答案教师资格证试题库军队文职题库时政题库事业单位综合知识题库小学教师资格证题库公务员考试题库及答案计算机题库及答案注册税务师题库体育理论考试题库