1. 实践题目 7-1 数字三角形 2. 问题描述 计算出从三角形的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。 3. 算法描述 for(int i=1; i<=n; i++)for(int j=1; j<=i; j++){cin >> a[i][j];m[i][j] = a[i][j];//设置两个数组，一个保留为原来的数据，另外一个用来记录数据}for(int i = n-1; i >0 ; i--){for(int j = 1; j <= i; j++){ //自底向上记录数据m[i][j] +=max(m[i+1][j],m[i+1]...
实践报告任选一题进行分析。内容包括：实践题目 问题描述 算法描述 算法时间及空间复杂度分析（要有分析过程） 心得体会（对本次实践收获及疑惑进行总结）1.实践题目 7-1 数字三角形 给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。 2.问题描述 刚开始的时候，知道每个数的最大路径与左右分支的路径有关，却没...
1.实践题目 7-3编辑距离问题 2.问题描述设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。 对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。 输入格式: 第一行是字符串A，文件的第二行是字符串B。 提示：字符串长度不超过2000个...
1、 实践题目：7-3 两个有序序列的中位数（二分法解法） 2、 问题描述：对于两个等长的非降序序列S1、S2，如何利用二分法的思想求出S1与S2并集的中位数，要求算法的时间复杂度为T(logn)。 3、 算法描述：总体思想：采用分治与递归策略，二分法每次将问题规模减半（约减半），然后对问题进行递归处理，在进行递归的过程中对可能出现特殊的情况，就特殊安排处理。 (1) 解法一： ① 先排除两个两个等长序列的元素个数（奇和偶）的影响...
一、实践题目 二分查找: 输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。二、问题描述 输入格式: 输入共三行： 第一行是n值； 第二行是n个整数； 第三行是x值。 输出格式: 输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。 输入输出 三、算法描述 通过二分查找思想不断缩小查找范围 通过左右两指针框定...
1.实践题目：两个有序序列的中位数 2.问题描述： 输入一个n（0<n<=100000），代表两个等长有序序列的长度，随后两行分别输入两个非降序序列，求出两个序列的合并后的中位数，中位数为合并后的有序序列中的第（n+1）/2个数，下标从0开始。 3.算法描述：本题可采用多种方法求解，最初我们选用的算法时间复杂度为O(n)，之后在老师的要求下，运用第二章所学知识（即分治法）进行改进，改进后时间复杂度为O(logN)。若采用分治法...
内容包括：实践题目 问题描述 算法描述 算法时间及空间复杂度分析（要有分析过程） 心得体会（对本次实践收获及疑惑进行总结）1.实践题目： 输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。 2.问题描述： 对于给定的n个非降序排列的整数，使用二分查找算法查找给定的x。如果能在这n个数中找到x，则输出它所在的下标及进行二...
算法作业：第二章上机实验报告 题目： 设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 输入格式: 第一行是n值和x值； 第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。 输出格式: 输出小于x的最大元素的最大下标i和大于x的最小元素的最小下标j。当搜索元素在数组中时，i和j相...
1 实践题目: 二分查找 2 问题描述： 输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。 3 算法描述 这道题是在原本二分查找的基础上加了一个比较次数，只需要定义一个计数器，在每次对数字进行二分的时候进行加加的操作。如果找到了要找的数，就输出所在下标和比较次数，如果没找到，就继续进行加加的操作，如果最后没有...
一. 实践题目 7-2 改写二分搜索算法 设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 输入格式: 输入有两行： 第一行是n值和x值； 第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。 输出格式: 输出小于x的最大元素的最大下标i和大于x的最小元素的最小下标j。当搜索元素在数组中...
实践题目 7-2 改写二分搜索算法 （20 分）题目来源：《计算机算法设计与分析》，王晓东 设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 问题描述 通过 算法描述 在二分搜索的基础上，输出搜索结束时的left 和 right即为题目中需要输出的i和j int Bisearch(int a[], int left, int rig...
实践题目：两个有序序列的中位数 问题描述： 已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列,的中位数指A?(N?1)/2??的值,即第?个数（A?0??为第1个数）。算法描述 输入两个非降序数列到两个长度相同的数组，再初始化一个新的数组，长度为两个数组的总和，将两个数列重新按照非降序排列，存入新数组中，再输出数组最中间的数字。算法时间及空间复杂度分析（要有分析过程） 两长度相同的数组，逐一比较...
1、实践题目 二分查找 2、问题描述 输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。 3、算法描述 定义search函数，递归的结束条件是(right < left)，输出-1； Search函数中，取数组a的第mid的值，将a[mid]与x比较； 当x<a[mid]，说明x在left-（mid-1）的范围内，然后继续运行search函数； 当x>a[mid]，说明x在（mid+1...
实践报告任选一题进行分析。内容包括：实践题目； 问题描述； 算法描述； 算法时间及空间复杂度分析（要有分析过程）； 心得体会（对本次实践收获及疑惑进行总结）。1.实践题目： 7-2 改写二分搜索算法 2.问题描述： 设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 3.算法描述：void search(i...
实践题目：改写二分搜索算法 问题描述：设a[0:n-1]是已排好序的数组，请改写二分搜索法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 算法描述： 如问题描述，如果输入的x存在于数组中，则i、j返回的是x在数组中的位置，否则返回小于x的最大数和大于x的最小数的位置。另外：如果输入的x小于或大于数组的所有数，则返回n和n-1；（n为数组中的整数...