下载文档原格式
算法分析与设计作业参考答案《算法分析与设计》作业参考答案作业⼀⼀、名词解释：1.递归算法：直接或间接地调⽤⾃⾝的算法称为递归算法。
2.程序：程序是算法⽤某种程序设计语⾔的具体实现。
⼆、简答题：1.算法需要满⾜哪些性质？简述之。
答：算法是若⼲指令的有穷序列，满⾜性质：（1）输⼊：有零个或多个外部量作为算法的输⼊。
（2）输出：算法产⽣⾄少⼀个量作为输出。
（3）确定性：组成算法的每条指令清晰、⽆歧义。
（4）有限性：算法中每条指令的执⾏次数有限，执⾏每条指令的时间也有限。
2.简要分析分治法能解决的问题具有的特征。
答：分析分治法能解决的问题主要具有如下特征：（1）该问题的规模缩⼩到⼀定的程度就可以容易地解决；（2）该问题可以分解为若⼲个规模较⼩的相同问题，即该问题具有最优⼦结构性质；（3）利⽤该问题分解出的⼦问题的解可以合并为该问题的解；（4）该问题所分解出的各个⼦问题是相互独⽴的，即⼦问题之间不包含公共的⼦问题。
3.简要分析在递归算法中消除递归调⽤，将递归算法转化为⾮递归算法的⽅法。
答：将递归算法转化为⾮递归算法的⽅法主要有：（1）采⽤⼀个⽤户定义的栈来模拟系统的递归调⽤⼯作栈。
该⽅法通⽤性强，但本质上还是递归，只不过⼈⼯做了本来由编译器做的事情，优化效果不明显。
（2）⽤递推来实现递归函数。
（3）通过Cooper 变换、反演变换能将⼀些递归转化为尾递归，从⽽迭代求出结果。
后两种⽅法在时空复杂度上均有较⼤改善，但其适⽤范围有限。
三、算法编写及算法应⽤分析题： 1.冒泡排序算法的基本运算如下： for i ←1 to n-1 dofor j ←1 to n-i do if a[j]交换a[j]、a[j+1]；分析该算法的时间复杂性。
答：排序算法的基本运算步为元素⽐较，冒泡排序算法的时间复杂性就是求⽐较次数与n 的关系。
（1）设⽐较⼀次花时间1；（2）内循环次数为：n-i 次,（i=1,…n ），花时间为：∑-=-=in j i n 1)(1（3）外循环次数为：n-1，花时间为：2.设计⼀个分治算法计算⼀棵⼆叉树的⾼度。
算法分析作业 IMB standardization office【IMB 5AB- IMBK 08- IMB 2C】算法分析练习题（一）一、选择题1、二分搜索算法是利用（A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（A ）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3．下列算法中通常以自底向上的方式求解最优解的是（B ）。
A、备忘录法B、动态规划法C、贪心法D、回溯法4、衡量一个算法好坏的标准是（C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短5、以下不可以使用分治法求解的是（D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题6. 实现循环赛日程表利用的算法是（A ）。
A、分治策略B、动态规划法C、贪心法D、回溯法7.备忘录方法是那种算法的变形。
（ B ）A、分治法B、动态规划法C、贪心法D、回溯法8．最长公共子序列算法利用的算法是（B ）。
A、分支界限法B、动态规划法C、贪心法D、回溯法9．实现棋盘覆盖算法利用的算法是（A ）。
A、分治法B、动态规划法C、贪心法D、回溯法10. 矩阵连乘问题的算法可由（B）设计实现。
A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法11、Strassen矩阵乘法是利用（A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法12、使用分治法求解不需要满足的条件是（A ）。
A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解13、下列算法中不能解决0/1背包问题的是（A ）A 贪心法B 动态规划C 回溯法D 分支限界法14．实现合并排序利用的算法是（A ）。
A、分治策略B、动态规划法C、贪心法D、回溯法15．下列是动态规划算法基本要素的是（D ）。
A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质16．下列算法中通常以自底向下的方式求解最优解的是（B ）。
算法理论、教改类题目学习大量相关算法（程序），总结出对应方法的一些特点，将其写成论文形式，并以足够的例子作为佐证。
24.论分治法、动态规划、贪心法的区别 25.论递归程序向非递归程序的转换 26.论应用型本科院校算法课程的教学目标和教学方法 27.论二叉树在计算机科学与技术中的应用 28.数据库索引的算法解释 29.论贪心法的适用范围 30.解空间搜索方法的选择依据 31.分治法算法分析综述
算法应用、算法研究类题目查阅大量相关资料，对相关内容给出初步的结果。
31.基于UCCI的中国象棋对弈引擎开发技术研究 32.五子棋对弈关键技术研究33.黑白棋对弈关键技术研究 34.数独初始局面生成算法研究 35.支持按文件名搜索的索引构造技术研究 36.通用回溯算法演示系统设计 37.通用分支限界算法演示系统设计 38.通用排序算法演示系统设计 39.通用动态规划算法演示系统设计
40.论文阅读和翻译类题目• 给出一个英文文献，用准确的语言将其翻译为中文，不需要逐字逐句翻译，但主要观点、算法思想和算法过程表述清楚、准确、充分。
格式要求• 论文正文中不得出现大段代码（超过10行）• 标题样式需规范• 参考文献不低于10篇，参考文献格式和标注位置须规范。
1.3 算法案例一、选择题1．关于进位制说法错误的是()A．进位制是人们为了计数和运算方便而约定的记数系统B．二进制就是满二进一，十进制就是满十进一C．满几进一，就是几进制，几进制的基数就是几D．为了区分不同的进位制，必须在数的右下角标注基数2．下列四个数中，数值最小的是()A．25(10)B．54(4)C．10 110(2)D．10 111(2)3．用更相减损术求1 515和600的最大公约数时，需要做减法次数是()A．15B．14C．13D．124．计算机中常用的十六进制是逢16进1的计数制，采用数字0～9和字母A～F共16个计数符号，这些符号与十进制数的对应关系如下表：十六0123456789A B C D E F 进制十进0123456789101112131415制例如，用十六进制表示：E＋D＝1B，则A×B等于()A．6E B．72C．5F D．B05．以下各数有可能是五进制数的是()A．15B．106C．731D．21 340二、填空题6．用更相减损术求36与134的最大公约数，第一步应为________．7．用秦九韶算法求f(x)＝2x3＋x－3当x＝3时的值v2＝________．8．将八进制数127(8)化成二进制数为________．三、解答题9．用更相减损术求288与153的最大公约数．10．用秦九韶算法计算多项式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64，当x＝2时的值．11．用秦九韶算法求多项式f(x)＝8x7＋5x6＋3x4＋2x＋1，当x＝2时的值．参考答案1.【解析】一般情况下，不同的进位制须在数的右下角标注基数，但十进制可以不用标注，所以不是必须在数的右下角标注基数，所以D 错误．【答案】D2.【解析】统一成十进制，B中54(4)＝5×41＋4＝24，C中10 110(2)＝1×24＋1×22＋2＝22，D中，10 111(2)＝23.【答案】C3.【解析】1 515－600＝915，915－600＝315，600－315＝285，315－285＝30，285－30＝255，255－30＝225，225－30＝195，195－30＝165，165－30＝135，135－30＝105，105－30＝75，75－30＝45，45－30＝15，30－15＝15.∴1 515与600的最大公约数是15.则共做14次减法．【答案】B4.【解析】A×B用十进制表示10×11＝110，而110＝6×16＋14，所以用16进制表示6E.【答案】A5.【解析】五进制数中各个数字均是小于5的自然数，故选D.【答案】D6.【解析】∵36与134都是偶数，∴第一步应为：先除以2，得到18与67.【答案】先除以2，得到18与677.【解析】f(x)＝((2x＋0)x＋1)x－3，v0＝2；v1＝2×3＋0＝6；v2＝6×3＋1＝19.【答案】198.【解析】先将八进制数127(8)化为十进制数：127(8)＝1×82＋2×81＋7×80＝64＋16＋7＝87，再将十进制数87化成二进制数：∴87＝1010111(2)，∴127(8)＝1010111(2)．【答案】1010111(2)9.解：288－153＝135，153－135＝18，135－18＝117，117－18＝99，99－18＝81，81－18＝63，63－18＝45，45－18＝27，27－18＝9，18－9＝9.因此288与153的最大公约数为9.10.解：将f(x)改写为f(x)＝(((((x－12)x＋60)x－160)x＋240)x－192)x＋64，由内向外依次计算一次多项式当x＝2时的值，v0＝1，v1＝1×2－12＝－10，v2＝－10×2＋60＝40，v3＝40×2－160＝－80，v4＝－80×2＋240＝80，v5＝80×2－192＝－32，v6＝－32×2＋64＝0.所以f(2)＝0，即x＝2时，原多项式的值为0. 11.解：根据秦九韶算法，把多项式改写成如下形式：f(x)＝8x7＋5x6＋0·x5＋3·x4＋0·x3＋0·x2＋2x＋1＝((((((8x＋5)x＋0)x＋3)x＋0)x＋0)x＋2)x＋1.而x＝2，所以有v0＝8，v1＝8×2＋5＝21，v2＝21×2＋0＝42，v3＝42×2＋3＝87，v4＝87×2＋0＝174，v5＝174×2＋0＝348，v6＝348×2＋2＝698，v7＝698×2＋1＝1 397.所以当x＝2时，多项式的值为1 397.。
第二章递归习题导论4.1-17(/?) = 27(b / 2)+ 1=> M = 2T5 /2) + 1%)习题导论4.1-6Tin) = 2T(0) + 1做代换：m=log2n另 S(m)=T(2m )则有： S(/z?) = 2S(zz? / 2) + 1 化简有:S(m)=O(m) 所以 T(n)=O(logn)习题4.2-27(/7)= T(n / 3) + 7(2/7 / 3) + 劲 注意最长分支 2n/3-*(2n/3)2 -*(2n/3)3...-*(2n^)log3/2n 习题4.3-1a) T(n) = 4T(n/2) + nb) T(n) = 4T(n/2) + n 2c 取大于1/2小于1的数即可,如珈习题4.3-4f(n )/nlogba = n 2log n/n'°g"二 log nvn所以不满足规则3直接化简即可，T(n)=O(n 2log 2n)c) T(n) = 4T(n/2) + n 3情况 3, ◎ (r?). 验证 4f(n/2)=4(n/2)3=n 3/2^cn 3,这里7X2")27(2"/彳)+情况4 0(n 2)情况 2, © (n 2logn)第三章习题4.5注意三分Z—和三分Z二分割点的计算ml = (2low+high)^m2 = (low+2high)/3习题4.20主要是验证T(n/r) + T(0)＞|« n/r+O的数量级是否小于n的1次方(线性) 利用关系式：\n / r」n (/7 - r - 1) / /进行化简r=3：\r / 2~|~|_/2 / /_] / 2~| ＞ 2 z? / r / 2 = n / r」＞ (/? 一2) / 3则，刀一卜/2北刀 / 厂」/ 2] ＜ /? - (/? - 2) / 3 = 2/7 / 3 + 2 / 3 则，n〃 +羊n +厉超线性了r=7：\r / 2]\n / r\/ 2〕＞/ 7」/2 = 2山 / 7」＞ 2(刀一6) / 7则，n - \r / i\\n / /」/ 2〕v 刀一2(刀一6) / 7 = 5刀 / 7 + 12 / 7可证,当n＞48的时候，上式小于3伙则，n/7+3nA = 25n/28 ＜n 成立r=9：\r / 2][n / 厂」/ 2〕＞ 5[刀 / 9」/ 2 = (5 / 2)^/9」＞ 5(刀-8)/18n一\r / 2\[n / /」/ 2〕＜ 13/?/18 + 40/18可证，当n>20的时候，上式小于7n/8 则，n/9+7n/8 = 71n/72 <n 成立r=ll习题4.25肓接带入验证即可棋盘覆盖问题角上用一个骨牌覆盖，认为构造有特殊方格的区域，然后在四个区域上递归求解即可第四章中位数中位数习题导论9-2A）比较明显。
计算机编程算法作业题参考答案1. 第一题答案：题目要求实现一个排序算法，可以选择任意一种排序算法进行实现。
以下给出一种可能的解答：def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]return arrarr = [64, 34, 25, 12, 22, 11, 90]sorted_arr = bubble_sort(arr)print("Sorted array:", sorted_arr)以上代码使用冒泡排序算法对给定的数组进行排序。
2. 第二题答案：题目要求实现一个查找算法，可以选择任意一种查找算法进行实现。
以下给出一种可能的解答：def binary_search(arr, target):low = 0high = len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return midelif arr[mid] < target:low = mid + 1else:high = mid - 1return -1arr = [11, 22, 25, 34, 64, 90]target = 25index = binary_search(arr, target)if index != -1:print("Target found at index:", index)else:print("Target not found in the array.")以上代码使用二分查找算法在有序数组中查找给定的目标值。
3. 第三题答案：题目要求实现一个递归算法，可以选择任意一种递归算法进行实现。
《算法分析与设计》作业（一）本课程作业由两部分组成。
第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。
第二部分为“主观题部分”，由简答题和论述题组成，共15分。
作业总分30分，将作为平时成绩记入课程总成绩。
客观题部分：一、选择题（每题1分，共15题）1、递归算法：（C ）A、直接调用自身B、间接调用自身C、直接或间接调用自身D、不调用自身2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同3、备忘录方法的递归方式是：（C ）A、自顶向下B、自底向上C、和动态规划算法相同D、非递归的4、回溯法的求解目标是找出解空间中满足约束条件的：（A ）A、所有解B、一些解C、极大解D、极小解5、贪心算法和动态规划算法共有特点是：（ A ）A、最优子结构B、重叠子问题C、贪心选择D、形函数6、哈夫曼编码是：（B）A、定长编码B、变长编码C、随机编码D、定长或变长编码7、多机调度的贪心策略是：（A）A、最长处理时间作业优先B、最短处理时间作业优先C、随机调度D、最优调度8、程序可以不满足如下性质：（D ）A、零个或多个外部输入B、至少一个输出C、指令的确定性D、指令的有限性9、用分治法设计出的程序一般是：（A ）A、递归算法B、动态规划算法C、贪心算法D、回溯法10、采用动态规划算法分解得到的子问题：（ C ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同11、回溯法搜索解空间的方法是：（A ）A、深度优先B、广度优先C、最小耗费优先D、随机搜索12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ）A、所需时间变化B、一定找到解C、找不到所需的解D、性能变差13、贪心算法能得到：（C ）A、全局最优解B、0-1背包问题的解C、背包问题的解D、无解14、能求解单源最短路径问题的算法是：（A ）A、分支限界法B、动态规划C、线形规划D、蒙特卡罗算法15、快速排序算法和线性时间选择算法的随机化版本是：（ A ）A、舍伍德算法B、蒙特卡罗算法C、拉斯维加斯算法D、数值随机化算法主观题部分：二、写出下列程序的答案（每题2.5分，共2题）1、请写出批处理作业调度的回溯算法。
1．下列四个有关算法的说法中，正确的是 ( 要求只填写序号 ) (1) 算法的某些步骤可以不明确或有歧义，以便使算法能解决更多问题； (2) 正确的算法执行后一定得到确定的结果； (3) 解决某类问题的算法不一定是唯一的； (4) 正确的算法一定能在有限步之内结束。
2．程序框图中表示计算的是( )．A ．B C D3．学了算法你的收获有两点，一方面了解我国古代数学家的杰出成就，另一方面，数学的机械化，能做许多我们用笔和纸不敢做的有很大计算量的问题，这主要归功于算法语句的：A ．输出语句B ．赋值语句C ．条件语句D ．循环语句 4．下列给出的赋值语句中正确的是：A 、3=AB 、M=—MC 、B=A=2D 、x+y=0 5．A=15,A=-A+5,最后A 的值为：A ．-10B ．20C ．15D ．无意义1.阅读下面的程序框图，该程序输出的结果是________.2.如图所示的程序框图输出的结果是 .3. (07-海南宁夏-5)如果执行下面的程序框图，那么输出的S =4.在如图所示的程序框图中输入3，结果会输出________.5.(08-山东-13)执行下边的程序框图，若0.8p =，则输出的n = 6．按如图所示的框图运算：若输入x =8,则输出k = ；若输出k =2，则输入的x 的取值范围是第3题第2题第4题第5题1．(09天津文)阅读下面的程序框图，则输出的S=A．14B．20C．30D．552．(09福建)阅读图2所示的程序框图，运行相应的程序，输出的结果是A．1 B. 2 C. 3 D. 43．(09福建)阅读右图所示的程序框图，运行相应的程序，输出的结果是A．2B．4C．8D4．(09浙江)某程序框图如图所示，该程序运行后输出的k的值是A．4B．5C．6D．75．执行右面的程序框图，输出的S是A．378-B．378C．418-D．4186．如图的程序框图表示的算法的功能是A．计算小于100的奇数的连乘积B．计算从1开始的连续奇数的连乘积C．从1开始的连续奇数的连乘积，当乘积大于100时，计算奇数的个数D．计算100531≥⨯⋅⋅⋅⨯⨯⨯n时的最小的n值.第4题第5题第6题1、编写程序，使任意输入的3个整数按从大到小的顺序输出.2、设计算法求S=2×4×6×8×…×2010的值。
全排列问题：设计思想：假设N个数的全排列是recuersive(list, 1, N)，即从第1个开始到第N个数的全排列，那么它的解可以划分为子问题：当第一位确定是某个数的时候，其余数的全排列。
假设第一位确定是数组中第i个数的时候，将数组第1个数与第i个数交换位置，则需求recuersive(list, 2, N)，即调整位置后的数组第2个至第N个的全排列。
逐渐划分子问题，到数组最后一个数时，它的全排列就是它本身，递归到底，这样就可以将前方排列好的输出了程序swap(int *a, int *b)交换两个数字不解释，recuersive(int list[], int k, int m)将数组list从k位到m位进行全排列。
首先确定首位是数组中的哪个数字，将其换至第一位，然后递归求交换过的数组剩下的数字的全排列，递归完成再把那两个数换回来，再用另一个数字当作首位，以此类推#include"stdafx.h"#include<iostream>#include<string>using namespace std;void recuersive(int a[],int,int);void swap(int& ,int&);int main(){int n;cout<<"输入你要排列的个数n"<<endl;cin>>n;int list[10];for(int i=0; i<=n1; i++)list[i]=i+1;recuersive(list,0, n1);system("pause");}inline void recuersive(int list[], int k, int m){if(k==m){for(int i=0; i<=m; i++)cout << list[i];cout << endl;}elsefor(int j=k; j<=m; j++){swap(list[k],list[j]);recuersive(list, k+1, m);swap(list[k],list[j]);}}inline void swap(int &a, int &b){int temp=a;a=b;b=temp;}运行结果：棋盘覆盖算法：设计思想：在2k x 2k个方格组成的棋盘中用到的L型骨牌恰有（4k-1）/3个。
从分治的思想易得到需将问题小型化，于是我们将棋盘平均分成四个相似的棋盘。
若特殊方格恰在图示的第一块区域，为了符合分治的思想我们需要将其他三部分转化成同样具有特殊方格的棋盘，依次递归知道棋盘为1x1的规模即可解决问题。
我的理解：倘若特殊方格在第一象限的区域内。
按照算法的思想将其余三块也转化成类似问题后一次递归，最终将会把2、3、4这三个格子留下来其余的格子会被全部覆盖掉。
而2、3、4着三个位置也恰好可以防止一个骨牌上去，最终就会完成整个问题的求解。
#include<iostream>using namespace std;const int BOARD_SIZE =4;int board[BOARD_SIZE][BOARD_SIZE];// c1, r1: 棋盘左上角的行号和列号// c2, r2: 特殊方格的行号和列号// size = 2 ^ kvoid chessboard(int r1, int c1, int r2, int c2, int size){if(1 == size) return;int half_size;static int domino_num = 1;int d = domino_num++;half_size = size / 2;if(r2 < r1 + half_size && c2 < c1 + half_size) //特殊方格在左上角棋盘{chessboard(r1, c1, r2, c2, half_size);}else// 不在此棋盘，将此棋盘右下角设为相应的骨牌号{board[r1 + half_size 1][c1 + half_size 1] = d;chessboard(r1, c1, r1 + half_size 1, c1 + half_size 1, half_size);}if(r2 < r1 + half_size && c2 >= c1 + half_size) //特殊方格在右上角棋盘{chessboard(r1, c1 + half_size, r2, c2, half_size);}else// 不在此棋盘，将此棋盘左下角设为相应的骨牌号{board[r1 + half_size 1][c1 + half_size] = d;chessboard(r1, c1 + half_size, r1 + half_size 1, c1 + half_size, half_size);}if(r2 >= r1 + half_size && c2 < c1 + half_size) //特殊方格在左下角棋盘{chessboard(r1 + half_size, c1, r2, c2, half_size);}else// 不在此棋盘，将此棋盘右上角设为相应的骨牌号{board[r1 + half_size][c1 + half_size 1] = d;chessboard(r1 + half_size, c1, r1 + half_size, c1 + half_size 1, half_size);}if(r2 >= r1 + half_size && c2 >= c1 + half_size) //特殊方格在左上角棋盘{chessboard(r1 + half_size, c1 + half_size, r2, c2, half_size);}else// 不在此棋盘，将此棋盘左上角设为相应的骨牌号{board[r1 + half_size][c1 + half_size] = d;chessboard(r1 + half_size, c1 + half_size, r1 + half_size, c1 + half_size, half_size); }}int main(){int i, j;board[2][2] = 0;chessboard(0, 0, 2, 2, BOARD_SIZE);for(i = 0; i < BOARD_SIZE; i++){for(j = 0; j < BOARD_SIZE; j++){cout<<board[i][j];}cout<<endl;}}运行结果：最接近点对算法：设计思想：将所给的平面上n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。
S1和S2的最接近点对未必就是S的最接近点对，如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。
但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n2/4次计算和比较才能确定S的最接近点对。
因此，依此思路，合并步骤耗时为O(n2)。
整个算法所需计算时间T(n)应满足: T(n)=2T(n/2)+O(n2) 它的解为T (n)=O(n2)#include<fstream>#include<iostream>using namespace std;const int L=1000;//点对结构体struct Pair{float d;//点对距离float d1,d2;//点对坐标};float Random();int input(float s[]);//构造Sfloat Max(float s[],int p,int q);float Min(float s[],int p,int q);template <class Type>void Swap(Type &x,Type &y);template <class Type>int Partition(Type s[],Type x,int l,int r);Pair Cpair(float s[],int l,int r);int main(){int m;float s[L];Pair d;m=input(s);d=Cpair(s,0,m-1);cout<<endl<<"最近点对坐标括为：(d1:"<<d.d1<<",d2:"<<d.d2<<")"; cout<<endl<<"这a两点距离为a："<<d.d<<endl;system("pause");return 0;}int input(float s[]){ifstream fin("D://data.txt");int static count=0;while(!fin.eof()){fin>>s[count];count++;}fin.close();for(int i=0;i<count;i++){cout<<s[i]<<" ";}return count;}float Max(float s[],int l,int r)//返回s[]中D的最大值{float s_max=s[l];for(int i=l+1;i<=r;i++)if(s_max<s[i])s_max=s[i];return s_max;}float Min(float s[],int l,int r)//返回s[]中的最小值{float s_min=s[l];for(int i=l+1;i<=r;i++)if(s_min>s[i])s_min=s[i];return s_min;}template <class Type>void Swap(Type &x,Type &y){Type temp = x;x = y;y = temp;}template <class Type>int Partition(Type s[],Type x,int l,int r) //将点集中的各元素按与m的大小关系分组{int i = l - 1,j = r + 1;while(true){while(s[++i]<x && i<r);while(s[--j]>x);if(i>=j){break;}Swap(s[i],s[j]);}return j;}//返回s[]中的具有最近距离的点对及其距离Pair Cpair(float s[],int l,int r){Pair min_d={999,0,0};//最短距离if(r-l<1) return min_d;float m1=Max(s,l,r),m2=Min(s,l,r);float m=(m1+m2)/2;//找出点集中的中位数//将点集中的各元素按与m的大小关系分组int j = Partition(s,m,l,r);Pair d1=Cpair(s,l,j),d2=Cpair(s,j+1,r);//递归float p=Max(s,l,j),q=Min(s,j+1,r);//返回s[]中的具有最近距离的点对及其距离if(d1.d<d2.d){if((q-p)<d1.d){min_d.d=(q-p);min_d.d1=q;min_d.d2=p;return min_d;}else return d1;}else{if((q-p)<d2.d){min_d.d=(q-p);min_d.d1=q;min_d.d2=p;return min_d;}else return d2;}}运行结果：。
