实践报告任选一题进行分析。内容包括：实践题目 问题描述 算法描述 算法时间及空间复杂度分析（要有分析过程） 心得体会（对本次实践收获及疑惑进行总结）1.实践报告：已知有两个等长的非降序序列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），随后每行输入一个序列的信息...
开门见山，直接上题目。7-2?改写二分搜索算法?(20?分)?设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 输入格式: 输入有两行： 第一行是n值和x值； 第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。 输出格式: 输出小于x的最大元素的最大下标i和大于x的最小元素的最小下标j。...
实践题目： 二分查找 输入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问题描述：此题相比二分查找多了一个查找不到时要求输出-1，...
算法第二章上机实践报告 组员：高珞洋，何汶珊 实践题目 7-2 改写二分搜索算法 设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 输入有两行：第一行是n值和x值； 第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。 输出格式：输出小于x的最大元素的最大下标i和大于x的最小元素的...
一.实践题目7-2?改写二分搜索算法题目来源：《计算机算法设计与分析》，王晓东 设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。 输入格式: 输入有两行： 第一行是n值和x值； 第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。 输出格式: 输出小于x的最大元素的最大下标i和大于x...
实践题目 7-3 两个有序序列的中位数 问题描述 已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列,的中位数指A?(N?1)/2??的值,即第?个数（A?0??为第1个数）。 输入格式: 输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。 输出格式: 在一行中输出两个输入序列的并集序列的中位数。 输入样例1: 5 1 3 5 7 9 2 3 4 5 6输出样例...
目录 一.实验目的: 二.实验任务: 三.实验内容: 1.冒泡排序实验分析: 2.冒泡排序实验代码: 3.冒泡排序实验结果: 4.二维数组实验分析: 5.实验代码 6.运行结果: 四.实验总结: 一.实验目的: 掌握用指针及引用作参数编写程序的知识技能; 提高学习者面向对象程序开发工具的自学习能力； 掌握一维数组和二维数组的定义、赋值和输入输出的方法。 能正确使用数组的指针和指向数组的指针变量。 通过编写程序理解并熟练掌握指针的概念； 二...
维度降低有两个主要用例：数据探索和机器学习。它对于数据探索很有用，因为维数减少到几个维度（例如2或3维）允许可视化样本。然后可以使用这种可视化来从数据获得见解（例如，检测聚类并识别异常值）。对于机器学习，降维是有用的，因为在拟合过程中使用较少的特征时，模型通常会更好地概括。 在这篇文章中，我们将研究三维降维技术：主成分分析（PCA）：最流行的降维方法 内核PCA：PCA的一种变体，允许非线性 t-SNE t分布随机邻域...
1.实践题目：工作分配问题 2.问题描述 7-2 工作分配问题 （20 分） 设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。 设计一个算法，对于给定的工作费用，为每 一个人都分配1 件不同的工作，并使总费用达到最小。 3.算法描述本题思想可借鉴旅行售货员算法，采用回溯子空间树的方法回溯，并利用isVisited数组和最小值比较进行剪枝。 private static void backTrack(int depth) { if (depth >= n) { ...
第五章 | 上机实践报告 一、 实践题目：工作分配问题 二、 问题描述 设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为Cij。对于给定的所有工作费用，为每一个人都分配1件不同的工作，使总费用达到最小。 三、 算法描述 1．解题思路：以第一份工作为结点构造子集树，在Backtrack函数中进行深度搜索。如果sum > bestp，则该分支不满足条件，需要进行剪枝，而后回溯；如果满足sum < bestp，则继续深搜，直至叶节点；如果s...
1. 实践题目：卡了很久的”删数问题“ 2. 问题描述： 给定n位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个新 的正整数。对于给定的n位正整数a和正整数 k，设计一个算法找出剩下数字组成的新数最小的删数方案。 要求输出最小数。如：给定a = 178543，k = 4，则输出13。 3. 算法描述： 先上代码 1 # 进行删数操作2 def delete(my_list, times):3 while times > 0:4 for j in range(1, len(my_li...
1.实践内容 程序存储问题 2.问题描述 设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li，1≤i≤n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案， 使得能够在磁带上存储尽可能多的程序。 对于给定的n个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数。 输入格式: 第一行是2 个正整数，分别表示文件个数n和磁带的长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长...
1.实践题目 7-2 删数问题 2.问题描述 给定n位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数 k，设计一个算法找出剩下数字组成的新数最小的删数方案。 输入格式：第 1 行是1 个正整数 a。第 2 行是正整数k。 输出格式：输出最小数。 输入样例：在这里给出一组输入。例如： 178543 4 输出样例：在这里给出相应的输出。例如： 13 3.算法描述 运用贪心算法求解，从前...
1.实践题目 7-2 最大子段和 2.问题描述 给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。 要求算法的时间复杂度为O(n)。 3.算法描述 首先将数据保存到一个数组内，然后建立一个循环来遍历这些数组，定义一个sum来保存和，定义一个max来保存最大值，对于每次遍历的结果x，如果sum为负，则将sum的值更改为x，并与max做对比，若...
第三章上机实践报告 1. 实践题目 7-3 编辑距离问题 （30 分） 2. 问题描述 设A和B是2个字符串。要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作包括 (1)删除一个字符； (2)插入一个字符； (3)将一个字符改为另一个字符。 将字符串A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离，记为d(A,B)。 对于给定的字符串A和字符串B，计算其编辑距离 d(A,B)。 输入格式: 第一行是字符串A，文件的第...