这次上机实验我和邓润明同学一起做了3个实践的代码。主要学习到的就是在写完代码后一定要检查。在写“7-3 两个有序序列的中位数”中，我们浪费了大量时间改写各个地方的条件判断，最后在一次重新看代码时，我才发现是i和j打错了造成的。原应该为“if(s1[i] < s2[j])”的判断语句，我们写成了“if(s1[i] < s2[i])”，再加上这个代码在pta中凑巧每次都能过5个中的3个，我们一直没有怀疑是代码写错，一直在为代码添加新的判断语句，或...
实践题目:二分查找 问题描述： 输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。 输入格式: 输入共三行： 第一行是n值； 第二行是n个整数； 第三行是x值。 输出格式: 输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。 输入样例: 4 1 2 3 4 1输出样例: 0 2 算法描述：设计一个二分查找的函数BinarySearch(...
1.实践题目 二分查找 2.问题描述 输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。 3.核心代码int BinarySearch(int a[],const int&x,int n){int left=0,right=n-1;while(left<=right){ l++;int middle=(left+right)/2;if(x==a[middle])return middle;if(x>a[middle])left=middle+1;else right=middle-1;}return -1; }4.时...
1.实践题目： 两个有序序列的中位数 2.问题描述：已知有两个等长的非降序序列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个非降序排列的整数。数字用空格间隔。 输出格式: 在一行中输出两个输入序列的并集序列的中位数。 3.算法描述...
实践报告任选一题进行分析。内容包括：实践题目 7-2 改写二分搜索算法 （20 分）题目来源：《计算机算法设计与分析》，王晓东 设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 输入格式: 输入有两行： 第一行是n值和x值； 第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。 输出...
1.7-1 二分查找 2.问题描述：输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。 3.算法描述：此题为基本的二分查找法并加上比较次数的输出。故在只需要在原来二分搜索的算法的基础上，设置一个全局变量num记录比较次数，在每一条比较的语句后，使num++。 4.算法时间及空间复杂度分析（要有分析过程）时间复杂度：二分搜索法充...
1、实践题目： 7-2 改写二分搜索算法 （20 分）题目来源：《计算机算法设计与分析》，王晓东 设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 2、问题描述： 二分搜索算法： 设a[0:n-1]是已排好序的数组,利用二分搜索法搜索x，当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。...
课堂笔记： 在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。很多贪心类型的题目都不是最朴素的贪心，而是需要做一些变化，对于我们，关键是找到贪心的本质！ 求解基本步骤： 1、从问题的某个初始解出发。 2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。 3、...