1.实践题目：编辑距离问题 2.问题描述：设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。 对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。 3.算法描述 填表法 for(int i=0;i<=m;i++) d[0][i]=i; for(int i=1;i<=n;i++) ...
1.实践题目 7-2 最大子段和 2.问题描述 给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。 要求算法的时间复杂度为O(n)。 3.算法描述 #include<iostream>using namespace std;int MaxSum(int n, int*a){ int sum = 0, b = 0, i; for(i=1; i <= n;i++){ if (b > 0) b = b + a[i]; else b = a[i]; if (b > sum) ...
1.实践题目： ?7-1 数字三角形 (30 分)?给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。输入格式: 输入有n+1行： 第 1 行是数字三角形的行数 n，1<=n<=100。 接下来 n行是数字三角形各行中的数字。所有数字在0..99 之间。 输出格式: 输出最大路径的值。 输入样例: 在这里给出一组输入。例如： 5 7 3 8 8 1...
实践题目 7-2 最大子段和 问题描述 给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。 要求算法的时间复杂度为O(n)。 算法描述 利用一维数组存储待求序列。首先定义MaxSum函数，用于返回求出的最大子段和。 MaxSum函数中定义了两个整型变量sum和count，sum作用是保存到a[k]位置为止的最大子段和，count作用是保存到a[k]位置...
实践题目： 最大子段和 给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。 要求算法的时间复杂度为O(n)。 输入格式: 输入有两行： 第一行是n值（1<=n<=10000)； 第二行是n个整数。 输出格式: 输出最大子段和。 输入样例: 6 -2 11 -4 13 -5 -2 输出样例: 20 ?问题描述：在给定的数段中找出和最大的子段，由于数段中存在负数，且...
实践题目最短编辑距离问题问题描述设A和B是2个字符串。将字符串A转换为字符串B所要用到的最少的字符操作（对单个字符进行插删改）的次数称为字符串A到 B的编辑距离，记为d(A,B)。 对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。算法描述从A字符串（fxpimu）只有0个字符开始，只有增加的操作满足其转换为B串（xwrs)。（同样的B串转换为A串也是同样的）那么此时就需要用到一个二维数组c[n][n](灰色的部分）来存储这些操作数：...
1.实践题目：数字三角形 ?2.问题描述：给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。输入格式: 输入有n+1行： 第 1 行是数字三角形的行数 n，1<=n<=100。 接下来 n行是数字三角形各行中的数字。所有数字在0..99 之间。 输出格式: 输出最大路径的值。 输入样例: 在这里给出一组输入。例如： 5 7 3 8 8 1 ...
1.实践题目 二分查找 2.问题描述 输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。 3.算法描述 运用普通的二分查找并且创建一个全局变量储存比较次数 4.算法时间及空间复杂度分析（要有分析过程） 在最坏情况下是在排除到只剩下最后一个值之后得到结果，所以为假使总共有n个元素，那么二分后每次查找的区间大小就是n，n/2，n...
1.代码规范（参考google的c++代码规范） 包含文件的名称及次序： 将包含次序标准化可增强可读性、避免隐藏依赖（hidden dependencies，注：隐藏依赖主要是指包含的文件编译），次序如下：C 库、C++库、其他库的.h、项目内的.h。 命名规范： 1、总体规则：不要随意缩写，如果说 ChangeLocalValue 写作ChgLocVal还有情可原的话，把ModifyPlayerName写作MdfPlyNm就太过分了，除函数名可适当为动词外，其他命名尽量...
改写二分搜索算法 思路与分析?题目来源：《计算机算法设计与分析》，王晓东 设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 输入格式: 输入有两行： 第一行是n值和x值； 第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。 输出格式: 输出小于x的最大元素的最大下标i和大于x的最...
1. 实践题目 已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列 ??的中位数指A_(N?1)/2的值,即第?(N+1)/2?个数（A_0为第1个数）。 输入格式: 输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。 输出格式: 在一行中输出两个输入序列的并集序列的中位数。 输入样例1: 5 1 3 5 7 9 2 3 4 5 6 输出样例1: 4 输入样例2: 6...
实践题目： 7-2 改写二分搜索算法 (20 分)?题目来源：《计算机算法设计与分析》，王晓东 设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 输入格式: 输入有两行： 第一行是n值和x值； 第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。 输出格式: 输出小于x的最大元素的最大下标...
题目： 两个有序序列的中位数 已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列,的中位数指A?(N?1)/2??的值,即第?个数（A?0??为第1个数）。 输入格式: 输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。 输出格式: 在一行中输出两个输入序列的并集序列的中位数。 题目需求：时间复杂度为 O（logN）解题思路：在考虑时间复杂...
题目： ? 7-3 两个有序序列的中位数 (20 分)?已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A?0??,A?1??,?,A?N?1??的中位数指A?(N?1)/2??的值,即第?(N+1)/2?个数（A?0??为第1个数）。 输入格式: 输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。 输出格式: 在一行中输出两个输入序列的并集序列的中位数。 输入样例1: 5 1...
1.实践题目：（第三题）两个有序序列的中位数： 2.问题描述：这道题要求在两个等长的非降序序列中求出其并集的中位数，老师还加了时间复杂度不超过logn的要求。 3.算法描述：开始时我和队友用的是排序法现将并集求出来，但是的时间复杂度就是O（N）了， 后来查找了资料看了其他的思路后，最后用的方法是比较两个序列的中位数的方法，也就是二分法； （1）两个数列中位数若一样，则该数就是所求中位数； （2）若某一个中位数大，...