算法分析实验报告--分治策略
《算法设计与分析》实验报告 分治策略 姓名:XXX 专业班级:XXX 学号:XXX 指导教师:XXX 完成日期:XXX
一、试验名称:分治策略 (1)写出源程序,并编译运行 (2)详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序,实现归并排序。 (2)编写一段程序,实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表:(1)每个选手必须与其它n-1个选手各赛一次(2)每个选手一天只能赛一场(3)循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序,实现归并排序。 将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行 排序,最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序,实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有 数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数 据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略,将所有的选手分为两组,n个选手的比赛日程表就可以通
过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割, 直到只剩下2个选手时,比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序,实现归并排序。 #include #include #define MAX 10 using namespace std; void merge(int array[],int p,int q,int r) { int i,k; int begin1,end1,begin2,end2; int* temp = new int[r-p+1]; begin1 = p; end1 = q; begin2 = q+1; end2 = r; k = 0; while((begin1 <= end1)&&(begin2 <= end2)) { if(array[begin1] < array[begin2]) { temp[k] = array[begin1]; begin1++; } else { temp[k] = array[begin2]; begin2++; } k++; } while(begin1 <= end1) {
分治法实验报告一
宁波工程学院电信学院计算机系 实验报告 课程名称:算法设计与分析实验项目:用分治法算法解 最接近点对问题 指导教师:崔迪 实验位置:软件工程实验室姓名: 班级: 学号: 日期: 2016/10/12 一、实验目的 通过上机实验,要求掌握分治法算法的问题描述、算法设计思想、程序设 计和算法复杂性分析等。 二、实验环境: Eclipse 三、实验内容:用分治法解最接近点对问题 (1)问题描述 给定平面S上n个点,找其中的一对点,使得在n(n-1)/2 个点对中,该 点对的距离最小。 (2)算法设计思想 1. n较小时直接求 (n=2). 2.将S上的n个点分成大致相等的2个子集S1和S2 3.分别求S1和S2中的最接近点对 4.求一点在S1、另一点在S2中的最近点对 5.从上述三对点中找距离最近的一对.
(3)程序设计(程序清单及说明) package closestpair; import java.util.Arrays; import https://www.doczj.com/doc/c72658455.html,parator; import java.util.Random; import java.util.Scanner; //定义坐标点 class Point { double x; double y; public Point(double x, double y) { this.x = x; this.y = y; } } // 根据x坐标排序 class MyComparatorX implements Comparator { @Override public int compare(Point p1, Point p2) { if (p1.x < p2.x) { return -1; } else if (p1.x > p2.x) { return 1; } else { return 0; } } } // 根据Y坐标排序 class MyComparatorY implements Comparator { @Override public int compare(Point p1, Point p2) { if (p1.y < p2.y) { return -1; } else if (p1.y > p2.y) { return 1; } else {
算法设计与分析:递归与分治法-实验报告
应用数学学院信息安全专业班学号姓名 实验题目递归与分治法 综合实验评分表
实验报告 一、实验目的与要求 1.掌握递归算法的设计思想 2.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 (1)源程序代码 #include #include using namespace std; int bin_search(int key[],int low, int high,int k) { int mid; if(low>high) return -1; else{ mid = (low+high) / 2; if(key[mid]==k) return mid; if(k>key[mid]) return bin_search(key,mid+1,high,k); else return bin_search(key,low,mid-1,k); } } int main() { int n , i , addr; int A[10] = {2,3,5,7,8,10,12,15,19,21}; cout << "在下面的10个整数中进行查找" << endl; for(i=0;i<10;i++){ cout << A[i] << " " ; } cout << endl << endl << "请输入一个要查找的整数" << endl; cin >> n; addr = bin_search(A,0,9,n);
if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } (2)运行界面 ①查找成功 ②查找失败
算法的时间复杂度
算法的时间复杂度 Prepared on 22 November 2020
时间复杂度:如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数,T(n)称为这一算法的“时间复杂度”。渐近时间复杂度:当输入量n逐渐加大时,时间复杂性的极限情形称为算法的“渐近时间复杂度”。 当我们评价一个算法的时间性能时,主要标准就是算法的渐近时间复杂度,因此,在算法分析时,往往对两者不予区分,经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度,其中的f(n)一般是算法中频度最大的语句频度。 此外,算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度,按数量级递增排列依次为:常数阶O(1)、对数阶 O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。 下面我们通过例子加以说明,让大家碰到问题时知道如何去解决。 1、设三个函数f,g,h分别为 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^+5000nlgn 请判断下列关系是否成立: (1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n^ (4) h(n)=O(nlgn)
这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n)),这里的"O"是数学符号,它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数,则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤Cf(n)。"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时,两者的比值是一个不等于0的常数。这么一来,就好计算了吧。 ◆ (1)成立。题中由于两个函数的最高次项都是n^3,因此当n→∞时,两个函数的比值是一个常数,所以这个关系式是成立的。 ◆(2)成立。与上同理。 ◆(3)成立。与上同理。 ◆(4)不成立。由于当n→∞时n^比nlgn递增的快,所以h(n)与nlgn的比值不是常数,故不成立。 2、设n为正整数,利用大"O"记号,将下列程序段的执行时间表示为n的函数。 (1) i=1; k=0 while(i算法实验四_空间最近点对算法
一、算法分析 该算法的问题描述为:给定二维平面上的点集,求解距离最近的两个点,并计算出两点间的距离。 解决问题最初的思路为穷举法。对所有两点间的组合计算其距离。然后对其进行比较,找出最小值即可。不过这样做的缺点是时间复杂度和空间复杂度十分庞大,消耗巨量资源。如有n个点的平面上,计算的复杂度能达到n*n。因此设计出一个高效的算法来代替穷举法是有现实意义的。 在思考问题的过程中,可以考虑使用分治法的思想,以x,y中x坐标作为划分区间的标准。将平面点集一分为二。求解其中的最小点对。由此产生的问题为划分点附近两个区间中两点的距离可能小于各自区间中的最小值,产生了纰漏。因此在在分治的过程中,加入分界线附近的点对最小值求解函数。分界线区域内区间的选取标准为d。其中d为左半区间和右半区间的最小值中的较小值。在具体实现中,首先建立一个空数组存放按y坐标排序的点集,判断两个相邻点之间的y坐标差值,若大于d,则两点间距离一定大于d,可以直接跳过,继续判断下一个点对。若小于d,则继续计算两点间的实际距离,若大于d,则跳过,小于d,将最小值更新为该点对距离。 二、算法实现 该算法的具体实现使用了两种求解方法,穷举法和分治法。其中,穷举法用于判断最近点对算法实现结果的正确性。 算法使用的数据结构为数组,其中为了简单起见,将x轴坐标与y轴坐标分别存入两个数组,并新建一个数组record[],记录数组y的元素下标,用于绑定x坐标对应的y坐标。 在设计过程中使用到了比较排序算法,用于对x及y坐标排序,这并不增加其时间复杂度。因此是可行的。 在分治算法中,设置划分区间的下限为3,即当区间内元素个数小于等于3时,不再使用分治。在该设定下分为三种情况,元素数为1时,Min设为无穷。元素数为2时,计算两点间距离并返回。元素数为3时,一共计算三次距离,并取其最小值。
反治法(以泻为补)
反治法(以泻为补) 发表时间:2011-11-16T16:51:06.060Z 来源:《中外健康文摘》2011年第28期供稿作者:魏大乐 [导读] 所以我说辩证论治(包括所谓的治病求本)在很多时候也不全对,必须加上一条治病素源才能达到最终完善 魏大乐(江西省新建县石埠乡西岗魏家江西南昌330100) 【中图分类号】R242【文献标识码】B【文章编号】1672-5085(2011)28-0231-01 我这里说的反治法,并不是教科书上说的反治法。教科书是这样说的:“反治法就是用于治疗疾病的症状与本质相反的疾病。是顺从疾病的假象而治的一种方法。”所谓的反治并不是真正的反治,实际上还是正治。而笔者所说的反治法,则是真正的反治法,与教科书上所说的反治法有着本质的不同。 例如患者徐某某年七旬,一九六七年—一九六八年贫血年余,无论从中医四诊的角度,还是西医化验、检测的角度,都是严重贫血和气虚,因而经诸多中医治疗,都是服用大量人参、阿胶、四君四物。经医院治疗,也是补血、补维生素、输液输血等。到后来竟成为口不含人参或隔日不输血便无法生存的人。遂慕名找我祖父治疗,凑巧祖父不在家,时过晌午,患者已支持不住,脸苍如土,闭目气微,呼多吸少,尺脉隐隐浮无根。于是我建议赶快上医院抢救,否则命在须臾。 家属认为,为时已晚,若上医院必死途中。遂苦苦央求要我下药,即使不救,也不至于后悔。无奈家中无药,仅找到一块大黄,约15克,于是我找来一块大柚子皮,再加一把烧菜用的自配香料(内含茴香、肉桂、砂仁、公丁等)共煎一锅,为从稳重,瞩患者徐徐少服。谁知患者不允,执意要多服,竟服下碗余。约20分钟后,放了一个响屁,臭气熏天,伸出大拇指表示服的舒服。不知不觉竟然一锅水全喝完。又过一小时,解下十余粒硬若铁石的大便(患者二十天没解大便)顿时气色渐见生气,精神转佳。口叫曰:仙药、仙药。至日已西沉,患者回家。拟方:大黄钱半,炒枳壳二钱,厚补二钱,砂仁一钱,肉桂一钱,白芍两钱,三剂后获得痊愈。大黄是泻药,枳壳、厚补是下气行气之药。此乃小承气汤加减。在通常情况下,只能用于治疗气血旺盛的患者。何况徐老严重气虚血虚。竟用泻下之法并真能起效。这是什么原因呢?其实这个答案在军事故事中都可以找得到。比如前方作战,粮尽弹绝。就象人体严重贫血和气虚一样十分危险。指挥员便会赶紧增派汽车,运送粮食和弹药。结果是汽车派多了,堵塞了道路,粮食和弹药送不上去。这时候如果继续增派汽车运送,只能是越堵越厉害,使粮食和弹药根本送不上去。只有明智的指挥官才会果断命令,将运送粮食和弹药的汽车推下山崖销毁,打通道路,才有可能让后面的粮、弹送到前方。这种方法实际上就是反治法。 表面上看,急待解决的问题是前方粮尽弹绝,这的确是矛盾的本质。但本质不等于根源。真正的根源不是汽车派少了,而是派多了,堵了道路,这才是矛盾的根源所在。今徐老先生患病的本质虽然是贫血,但造成贫血的根本原因不是摄入不足,而是补品吃得太多,滞塞了脾胃和体内的气血运行,致使新陈代谢迟钝,饮食物不能化生气血津液。虽然其证是严重贫血。但根本原因却是壅滞,只有用泻法,泻去积食、积滞,清除垃圾,才能恢复新陈代谢,恢复脾胃功能,打通全身气血运行的通道,使纳入的食物自然生血,产生气血津液,故一泻而不治自愈。 所以我说辩证论治(包括所谓的治病求本)在很多时候也不全对,必须加上一条治病素源才能达到最终完善。这是很值得医学同道深省的。
算法实验报告
实验一分治与递归算法的应用 一、实验目的 1.掌握分治算法的基本思想(分-治-合)、技巧和效率分析方法。 2.熟练掌握用递归设计分治算法的基本步骤(基准与递归方程)。 3.学会利用分治算法解决实际问题。 二 . 实验内容 金块问题 老板有一袋金块(共n块,n是2的幂(n≥2)),最优秀的雇员得到其中最重的一块,最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器,希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。 三.问题分析: 一般思路:假设袋中有n 个金块。可以用函数M a x(程序 1 - 3 1)通过n-1次比较找到最重的金块。找到最重的金块后, 可以从余下的n-1个金块中用类似法通过n-2次比较找出最轻的金块。这样,比较的总次数为2n-3。
分治法:当n很小时,比如说,n≤2,识别出最重和最轻的金块,一次比较就足够了。当n 较大时(n>2),第一步,把这袋金块平分成两个小袋A和B。第二步,分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA 与LA,以此类推,B中最重和最轻的金块分别为HB 和LB。第三步,通过比较HA 和HB,可以找到所有金块中最重的;通过比较LA 和LB,可以找到所有金块中最轻的。在第二步中,若n>2,则递归地应用分而治之方法 程序设计 据上述步骤,可以得出程序1 4 - 1的非递归代码。该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数,若n < 1,则程序返回f a l s e,否则返回t r u e。 当n≥1时,程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量,w [ M a x ]为最大的重量。 首先处理n≤1的情况。若n>1且为奇数,第一个重量w [ 0 ]将成为最小值和最大值的候选值,因此将有偶,数个重量值w [ 1 : n - 1 ]参与f o r循环。当n 是偶数时,首先将两个重量值放在for 循环外进行比较,较小和较大的重量值分别置为Min和Max,因此也有偶数个重量值w[2:n-1]参与for循环。 在for 循环中,外层if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。此工作与前面提到的分而治之算法步骤中的2) 相对应,而内层的i f负责找出较小重量值和较大重量值中的最小值和最大值,
最近点对分治法
假设在一片金属上钻n 个大小一样的洞,如果洞太近,金属可能会断。若知道任意两个洞的最小距离,可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。 如果不用分治法,问题非常容易解决。也就是蛮力法。 代码如下: #include #include typedef struct TYPE { double x, y; } Point; float dist(Point a,Point b) { return (float)sqrt((float)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } float nearest(Point* points, int n) { float temp,near1=10000; int i,j; if(n==1) { printf("不可能"); return 0; } else{ for(i=0; itemp)?temp:near1; } } return near1; } } int main()
{ int n, i; double d; printf("输入点的个数:"); scanf("%d", &n); Point a[10000]; while (n) { for (i = 0; i < n; i++) scanf("%lf%lf", &(a[i].x), &(a[i].y)); d = nearest(a,n); printf("%.2lf\n", d); scanf("%d", &n); } return 0; } 但是本题是用分治法,我也参考了网上很多资料,他们要求对纵坐标进行排序,可能是为了对求右边的问题的点扫描用for 循环,但我发现那算法就不对,但愿是我的还没有完全明白按纵坐标排序的原因, 我参考的资料: https://www.doczj.com/doc/c72658455.html,/p-198711591.html?qq-pf-to=pcqq.c2c 代码如下: #include #include #include
分治算法实验(用分治法实现快速排序算法)
算法分析与设计实验报告第四次附加实验
while (a[--j]>x); if (i>=j) { break; } Swap(a[i],a[j]); } a[p] = a[j]; //将基准元素放在合适的位置 a[j] = x; return j; } //通过RandomizedPartition函数来产生随机的划分 template vclass Type> int RandomizedPartition(Type a[], int p, int r) { int i = Random(p,r); Swap(a[i],a[p]); return Partition(a,p,r); } 较小个数排序序列的结果: 测试结果 较大个数排序序列的结果:
实验心得 快速排序在之前的数据结构中也是学过的,在几大排序算法中,快速排序和归并排序尤其是 重中之重,之前的快速排序都是给定确定的轴值,所以存在一些极端的情况使得时间复杂度 很高,排序的效果并不是很好,现在学习的一种利用随机化的快速排序算法,通过随机的确 定轴值,从而可以期望划分是较对称 的,减少了出现极端情况的次数,使得排序的效率挺高了很多, 化算法想呼应,而且关键的是对于随机生成函数,通过这一次的 学习终于弄明白是怎么回事了,不错。 与后面的随机实 验和自己的 实验得分助教签名 附录: 完整代码(分治法) //随机后标记元素后的快速排序 #i nclude #in elude #inelude #include using namespacestd; template < class Type> void S &x,Type &y); // 声明swap函数 inline int Random(int x, int y); // 声明内联函数 template < class Type> int Partition(Type a[], int p, int r); // 声明 Partition 函数template int RandomizedPartition(Type a[], int p, int r); // 声明 RandomizedPartition 函数 int a[1000000]; //定义全局变量用来存放要查找的数组 更大个数排序序列的结果:
递归与分治实验报告
递归与分治实验报告 班级:计科1102 姓名:赵春晓学号:2011310200631 实验目的:进一步掌握递归与分治算法的设计思想,通过实际问题来应用递归与分治设计算法。 实际问题:1集合划分问题,2输油管道问题,3邮局选址问题,4整数因子分解问题,5众数问题。 问题1:集合划分 算法思想:对于n个元素的集合,可以划分为由m个子集构成的集合,例如{{1,2}{3,4}}就是由2个子集构成的非空子集。假设f(n,m)表示将n个元素划分成由m个子集构成的集合的个数。那么1)若m == 1 ,则f(n,m)= 1 ;2)若n == m ,则f(n,m)= 1 ;3)若不是上面两种情况则有下面两种情况构成:3.1)向n-1个元素划分成的m个集合里面添加一个新的元素,则有m*f(n-1,m)种方法;3.2)向n-1个元素划分成的m-1个集合里添加一个由一个元素形成的独立的集合,则有f(n-1,m-1)种方法。 实验代码: #include #include using namespace std ; int jihehuafen( int n , int m ) { if( m == 1 || n == m ) return 1 ; else return jihehuafen( n - 1 , m - 1 ) + m*jihehuafen( n - 1 , m ) ; } int main() { ifstream fin("C:/input.txt") ; ofstream fout("C:/output.txt") ; int N , M , num ; fin >> N >> M ; num = jihehuafen( N , M) ; fout << num << endl ; return 0 ; } 问题2:输油管道 算法思想:由于主管道由东向西铺设。故主管道的铺设位置只和各油井的y坐标有关。要使主管道的y坐标最小,主管道的位置y坐标应是各个油井y坐标的中位数。先用快速排序法把各个油井的y坐标排序,然后取其中位数再计算各个油
给出以下算法的时间复杂度
第1章绪论 1、填空题 1.常见的数据结构有_________结构,_________结构,_________结构等三种。 2.常见的存储结构有_________结构,_________结构等两种。 3.数据的基本单位是_________,它在计算机中是作为一个整体来处理的。 4.数据结构中的结构是指数据间的逻辑关系,常见的结构可分为两大类,_________和_________。 2、应用题 1、给出以下算法的时间复杂度. void fun(int n) { int i=1,k=100; while(iwhile(inext=p->next; p->next=s; (B)p->next=s; s->next=p->next;
最近点对问题
最近点对问题 I.一维问题: 一、问题描述和分析 最近点对问题的提法是:给定平面上n个点,找其中的一对点,使得在n个点组成的所有点对中,该点对间的距离最小。 严格的讲,最接近点对可能多于1对,为简单起见,只找其中的1对作为问题的解。简单的说,只要将每一点与其它n-1个点的距离算出,找出达到最小距离的2点即可。但这样效率太低,故想到分治法来解决这个问题。也就是说,将所给的平面上n个点的集合S 分成2个子集S1和S2,每个子集中约有n/2个点。然后在每个子集中递归的求其最接近的点对。这里,关键问题是如何实现分治法中的合并步骤,即由S1和S2的最接近点对,如何求得原集合S中的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中,则问题很容易解决,但如果这2个点分别在S1和S2中,问题就不那么简单了。下面的基本算法中,将对其作具体分析。 二、基本算法 假设用x轴上某个点m将S划分为2个集合S1和S2,使得S1={x∈S|x<=m};S2={x ∈S|x>m}。因此,对于所有p∈S1和q∈S2有p算法时间复杂度计算示例
基本计算步骤 示例一: (1) int num1, num2; (2) for(int i=0; i