一、实践题目 工作分配问题 二、问题描述 设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。 设计一个算法，对于给定的工作费用，为每一个人都分配1 件不同的工作，并使总费用达到最小。 输入格式：输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示工作费用。 输出格式：将计算出的最小总费用输出到屏幕。 三、算法描述 问题的解空间如下： 剪枝方法：我们将当前最优解记...
TF-IDF是一种统计方法，这个算法在我们项目提取关键词的模块需要被用到，TF-IDF算法是用来估计一个词汇对于一个文件集中一份文件的重要程度。从算法的定义中就可以看到，这个算法的有效实现是依靠一定数据量的文件集作为基础的。字词的重要性随着他在文件中出现的次数呈正比例的关系增加，这一点很符合常识，就是这个词出现的次数越多，那个这个词越重要，词的出现频度和他的重要程度之间呈现正关系。为了抑制冠词等经常出现的无用...
1.实践题目名称： 找第k小的数2.问题描述： 设计一个平均时间为O(n)的算法，在n(1<=n<=1000)个无序的整数中找出第k小的数。3.算法描述： 定义一个分割函数，实现返回指定数组中的数在数组中是第k大的数值k，若该k值与题目所需不符，则传入另一查找函数，在该查找函数中实现在数组的[0,k)或(k,n]段中查找符合要求的k值。函数具体实现如下：//分割函数//选取数组中的第一个数作为基数，将数组分成两部分 int partition(int a[],in...
一、实践题目改写二分搜索算法二、问题描述设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。三、算法描述依然采用了二分搜索算法的大部分代码，然后进行了简单修改。当x不在数组中时分为三种情况，需要对这三种情况进行一一实现。#include <iostream>using namespace std;int main(){ int n,x; cin...
题目：二分查找输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。感想：其实这道题很简单的，只需要给二分查找的比较算法中添加一个简单的计数器就可以了，但要注意这个计数器必须放在二分查找左右比较的遍历代码中的第一行，才能完成正确的比较。但是由于函数只能return 一个数值，而原始的二分查找函数是用来返回下标的，一...
1. 实践题目 7-1数字三角形 给定一个由 n行数字组成的数字三角如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5输出 30 2. 问题描述 使用初始值-1的二位数组记录每个子问题的最大值，进而得到最大数字总和路径 3. 算法描述 递归方程： maxSum[i]...
本文索引目录：一、PTA实验报告题1 ： 二分查找 1.1 实践题目 1.2 问题描述 1.3 算法描述 1.4 算法时间及空间复杂度分析二、PTA实验报告题2 ： 改写二分搜索算法 2.1 实践题目 2.2 问题描述 2.3 算法描述 2.4 算法时间及空间复杂度分析三、PTA实验报告题3 ： 两个有序序列的中位数 3.1 实践题目 3.2 问题描述 3.3 算法描述 3.4 算法时间及空间复杂度分析...
1、实践题目：最大子段和2，问题描述： 给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。要求算法的时间复杂度为O(n)。3、算法描述：定义两个数组a,b，a表示要输入的序列,b表示序列的子段和(比如b[3]表示a[1],a[2],a[3]的最大子段和），然后进行判断，如果前面的最大子段和大于0，则加上改最大子段和，若前面的最大子段和小于...
1.实践题目7-1 数字三角形 (30 分) 给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。输入格式:输入有n+1行：第 1 行是数字三角形的行数 n，1<=n<=100。接下来 n行是数字三角形各行中的数字。所有数字在0..99 之间。输出格式:输出最大路径的值。输入样例:在这里给出一组输入。例如：5
7
3 8
8 1 0
2 7 4 4
...
1、实践题目：改写二分搜索算法2、问题描述：设a[0:n-1]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。输入格式:输入有两行：第一行是n值和x值； 第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。输出格式:输出小于x的最大元素的最大下标i和大于x的最小元素的最小下标j。当搜索元素在数...
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个字符。...
实践题目名称:找第k小的数问题描述:设计一个平均时间为O(n)的算法，在n(1<=n<=1000)个无序的整数中找出第k小的数。提示：函数int partition(int a[],int left,int right)的功能是根据a[left]~a[right]中的某个元素x（如a[left])对a[left]~a[right]进行划分，划分后的x所在位置的左段全小于等于x,右段全大于等于x,同时利用x所在的位置还可以计算出x是这批数据按升非降序排列的第几个数。因此可以编制int find(int a[],int left,int ...
一、程序存储问题1.实践题目设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li，1≤i≤n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案， 使得能够在磁带上存储尽可能多的程序。 对于给定的n个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数。输入格式:第一行是2 个正整数，分别表示文件个数n和磁带的长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。输出格式...
1.实践题目7-2 工作分配问题2.问题描述设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。 设计一个算法，对于给定的工作费用，为每一个人都分配1 件不同的工作，并使总费用达到最小。输入格式:输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示工作费用。输出格式:将计算出的最小总费用输出到屏幕。输入样例:在这里给出一组输入。例如：3
10 2 3
2 3 4
3 4 5
输出样例:在这里给出相应的输出...
1.实践题目数字三角形2.问题描述给定一个由 n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形 的顶至底的一条路径(每一步可沿左斜线向下或右斜线向下)，使该路径经过的数字总和最大。3.算法描述用动态规划的方式算出，由上往下算数字总和最大为递归方程式为（i是行数，j是列数，N为最大层数，a[i][j]是以这个数字为顶的数字总和最大,b[i][j]即为i行j列的值）a[i][j] = 0 （i = N）a[i][j] = b[i][j] + max(a[i+...
