棋盘覆盖问题
问题描述：
在一个2k ×2k （k ≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中出现的位置有4k 中情形，因而有4k 中不同的棋盘，图（a ）所示是k=2时16种棋盘中的一个。棋盘覆盖问题要求用图（b ）所示的4中不同形状的L 型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且热河亮哥L 型骨牌不得重复覆盖。
问题分析：
K>0时，可将2k ×2k 的棋盘划分为4个2k-1×2k-1的子棋盘。这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有1个子棋盘中有特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化成为特殊棋盘，以便采用递归方法求解，可以用一个L 型骨牌覆盖这3个较小的棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。 问题求解：
下面介绍棋盘覆盖问题中数据结构的设计。
（1） 棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中size=2k 。为了
在递归处理的过程中使用同一个棋盘，将数组board 设为全局变量。
（2） 子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘由棋盘左上
角的下标tr 、tc 和棋盘大小s 表示。
（3） 特殊方格：用board[dr][dc]表示特殊方格，dr 和dc 是该特殊方格在二维数组
board 中的下标。
（4） L 型骨牌：一个2k ×2k 的棋盘中有一个特殊方格，所以，用到L 型骨牌的个数
为（4k -1）/3，将所有L 型骨牌从1开始连续编号，用一个全局变量tile 表示。
图（b ） 图 （a ）
C语言源码：
/*author: 彭洪伟
*studentID:0950310006
*class:计科1班
*problem:分治法解决棋盘覆盖问题
*/
#include
#include
int tile=1; //记录骨牌的型号
int board[20][20]={0}; //存储棋盘被覆盖的情况
void ChessBoard(int tr,int tc,int dr,int dc,int size)
{ //tr和tc是棋盘左上角的下标,dr和dc是特殊方格的下标,size是棋盘的大小int t=0;
int s;
if (size==1)return;
t=tile++;
s=size/2; //划分棋盘
//覆盖左上角棋盘
if (dr ChessBoard(tr,tc,dr,dc,s); else { board[tr+s-1][tc+s-1]=t; ChessBoard(tr,tc,tr+s-1,tc+s-1,s); } //覆盖右上角棋盘 if (dr ChessBoard(tr,tc+s,dr,dc,s); else { board[tr+s-1][tc+s]=t; ChessBoard(tr,tc+s,tr+s-1,tc+s,s); } //覆盖左下角棋盘 if (dr>=tr+s&&dc ChessBoard(tr+s,tc,dr,dc,s); else { board[tr+s][tc+s-1]=t; ChessBoard(tr+s,tc,tr+s,tc+s-1,s); } //覆盖右下角棋盘 if (dr>=tr+s&&dc>=tc+s) //特殊方格在棋盘的右下角ChessBoard(tr+s,tc+s,dr,dc,s); else { board[tr+s][tc+s]=t; ChessBoard(tr+s,tc+s,tr+s,tc+s,s); } } int main() { int k,x,y; printf("请输入棋盘的规模K："); scanf("%d",&k); printf("请输入特殊方格的下标x,y："); scanf("%d %d",&x,&y); ChessBoard(0,0,x,y,pow(2,k)); for(int i=0; i { for (int j=0; j { printf("%-4d",board[i][j]); } printf("\n"); } return 0; } 运行结果截图： 问题场景：在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。 问题描述：给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。 1、一维最接近点对问题 算法思路： 这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n^2)的计算时间。在问题的计算复杂性中我们可以看到，该问题的计算时间下界为Ω(nlogn)。这个下界引导我们去找问题的一个θ(nlogn)算法。采用分治法思想，考虑将所给的n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S 的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n^2/4次计算和比较才能确定S的最接近点对。因此，依此思路，合并步骤耗时为O(n^2)。整个算法所需计算时间T(n)应满足:T(n)=2T(n/2)+O(n^2)。它的解为T(n)=O(n^2)，即与合并步骤的耗时同阶，这不比用穷举的方法好。从解递归方程的套用公式法，我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在合并步骤上。 设S中的n个点为x轴上的n个实数x1,x2,..,xn。最接近点对即为这n个实数中相差最小的2个实数。我们显然可以先将x1,x2,..,xn排好序，然后，用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上，在排序算法已经证明，时间复杂度为O(nlogn)。然而这种方法无法直接推广到二维的情形。因此，对这种一维的简单情形，我们还是尝试用分治法来求解，并希望能推广到二维的情形。假设我们用x轴上某个点m将S划分为2个子集S1和S2，使得S1={x∈S|x≤m}；S2={x∈S|x>m}。这样一来，对于所有p∈S1和q∈S2有p 伪代码 伪码（Pseudocode）是一种算法描述语言。使用伪码的目的是使被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java等）实现。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。介于自然语言与编程语言之间。以编程语言的书写形式指明算法职能。使用伪代码，不用拘泥于具体实现。相比程序语言（例如Java, C++,C, Dephi 等等）它更类似自然语言。它是半角式化、不标准的语言。可以将整个算法运行过程的结构用接近自然语言的形式（可以使用任何一种你熟悉的文字，关键是把程序的意思表达出来）描述出来。 1.简介 定义 人们在用不同的编程语言实现同一个算法时意识到，他们的实现（注意：这里是实现，不是功能）很不同。尤其是对于那些熟练于不同编程语言的程序员要理解一个（用其他编程语言编写的程序的）功能时可能很难，因为程序语言的形式限制了程序员对程序关键部分的理解。这样伪代码就应运而生了。伪代码提供了更多的设计信息，每一个模块的描述都必须与设计结构图一起出现。伪代码是一种非正式的，类似于英语结构的，用于描述模块结构图的语言。 应用领域 当考虑算法功能（而不是其语言实现）时，伪码常常得到应用。伪码中常被用于技术文档和科学出版物中来表示算法，也被用于在软件开发的实际编码过程之前表达程序的逻辑。伪代码不是用户和分析师的工具，而是设计师和程序员的工具。计算机科学在教学中通常使用虚拟码，以使得所有的程序员都能理解。综上，简单地说，让人便于理解的代码。不依赖于语言的，用来表示程序执行过程，而不一定能编译运行的代码。在数据结构讲算法的时候用的很多。伪代码用来表达程序员开始编码前的想法。 2.语法规则 例如，类Pascal语言的伪码的语法规则是：在伪码中，每一条指令占一行（else if，例外）。指令后不跟任何符号（Pascal和C中语句要以分号结尾）。书写上的“缩进”表示程序中的分支程序结构。这种缩进风格也适用于if-then-else语句。用缩进取代传统Pascal中的begin和end语句来表示程序 算法练习题-分章节-带答案 算法练习题---算法概述 一、选择题 1、下面关于算法的描述，正确的是（） A、一个算法只能有一个输入 B、算法只能用框图来表示 C、一个算法的执行步骤可以是无限的 D、一个完整的算法，不管用什么方法来表示，都至少有一个输出结果 2、一位爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，更恰当的是（） A、设计算法，编写程序，提出问题，运行程序，得到答案 B、分析问题，编写程序，设计算法，运行程序，得到答案 C、分析问题，设计算法，编写程序，运行程序，得到答案 D、设计算法，提出问题，编写程序，运行程序，得到答案 3、下面说法正确的是（） A、算法+数据结构=程序 B、算法就是程序 C、数据结构就是程序 D、算法包括数据结构 4、衡量一个算法好坏的标准是（）。 A、运行速度快 B、占用空间少 C、时间复杂度低 D、代码短 5、解决一个问题通常有多种方法。若说一个算法“有效”是指( )。 A、这个算法能在一定的时间和空间资源限制内将问题解决 B、这个算法能在人的反应时间内将问题解决 C、这个算法比其他已知算法都更快地将问题解决 D、A和C 6、算法分析中，记号O表示（），记号Ω表示（）。 A.渐进下界 B.渐进上界 C.非紧上界 D.非紧下界 7、以下关于渐进记号的性质是正确的有：（） A.f(n)(g(n)),g(n)(h(n))f(n)(h(n)) =Θ=Θ?=Θ B.f(n)O(g(n)),g(n)O(h(n))h(n)O(f(n)) ==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D.f(n)O(g(n))g(n)O(f(n)) =?= 昆明理工大学信息工程与自动化学院学生实验报告 （ 201 — 201 学年 第 1 学期 ） 课程名称：算法分析与设计 开课实验室： 年 月 日 一、上机目的及内容 1.上机内容 给定有n 个整数（可能有负整数）组成的序列（a 1,a 2,…,a n ），求改序列形如 ∑=j k k a 1 的子段和的 最大值，当所有整数均为负整数时，其最大子段和为0。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）分别用穷举法、分治法和动态规划法设计最大子段和问题的算法； （2）对所设计的算法采用大O 符号进行时间复杂性分析； （3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。 穷举法是用一个二维数组将从i 到j 的和都记录下来，再比较各元素的大小，时间复杂性为O （n 2），分治法的设计思想是不断将问题为子问题，然后求解子问题，最后对解进行合并，时间复杂性为O(nlog n )，动态规划法的设计思想是将问题划分为若干个子问题，时间复杂度为O(n)。 分治法流程图： 穷举法流程图： 动态规划法流程图： 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC 及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 程序代码： //穷举法 #include 实用文案 修订记录 目录 第一章概述 (5) 1.1.应用模块的目的 (5) 1.2.应用模块总体描述 (5) 1.3.应用模块接口描述 (5) 1.4.假设条件 (5) 第二章设计模式（Design pattern） (6) 第三章类设计 (7) 3.1.分块类图 (8) 3.1.1.<类图1> 8 3.1.2.<类图n> 8 3.2.整体继承关系 (8) 3.3.类描述 (9) 3.3.1.<类名1> Class Description 9 3.3.2.<类名n> Class Description 10 第四章交互图 (12) 4.1.<情景编号1: 情景名称> (12) 4.1.1.交互图 12 4.1.2.例外情况及条件 13 4.2.<情景编号n: 情景名称> (13) 第五章状态图 (14) 5.1.<状态图编号1:状态图名称> (14) 5.2.<状态图编号n:状态图名称> (15) 第六章时序流程图 (16) 第七章用户界面设计说明 (18) 7.1.用户界面关系 (18) 7.2.用户界面具体描述 (18) 7.2.1.<界面编号1:界面名称〉 18 7.2.2.<界面编号N:界面名称〉 19 第八章测试考虑 (20) 第九章附录 (21) 9.1.附录A 代码举例 (21) 9.2.附录B 设计问题 (21) 9.2.1.<设计问题1> 21 9.2.2.<设计问题n> 21 第一章概述 1.1.应用模块的目的 请明确客户建立应用模块的目的。 1.2.应用模块总体描述 描述应用模块的总体功能。 1.3.应用模块接口描述 简要描述本应用模块的公共接口，具体接口会在相应的类中进行具体描述。建议采用列表的方式。 1.4.假设条件 列出在问题领域，项目方案及其它影响系统设计的可能方面内，应当成立的假设条件。包括系统的约束条件和应遵循的标准。 宁波工程学院电信学院计算机系 实验报告 课程名称：算法设计与分析实验项目：用分治法算法解 最接近点对问题 指导教师：崔迪 实验位置：软件工程实验室姓名： 班级： 学号： 日期： 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/2412128573.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 最接近点对问题 一．实验目的： 1.理解算法设计的基本步骤及各步的主要内容、基本要求； 2.加深对分治设计方法基本思想的理解，并利用其解决现实生活中的问题； 3.通过本次实验初步掌握将算法转化为计算机上机程序的方法。 二．实验内容： 1.编写实现算法：给定n对点，在这n对点中找到距离最短的点对。 2.将输出数据存放到另一个文本文件中，包括结果和具体的运行时间。 3.对实验结果进行分析。 三．实验操作： 1.最接近点对查找的思想： 首先，将所有的点对按照x坐标排序，找到x坐标的中位数，将所有的点对分成三部分，横坐标小于x（S1）、等于x（S2）和大于x（S3）的点对，在求取每部分中的最短距离，利用分治法，一步步地分解为子问题，找到最短距离d。由于距离最近的两个点可能在不同的区域中，需要进一步判断。 选择S1中的一个点，由于与它相比较的点的距离不可能超过d，故其配对范围为d*2d的矩形，将这个矩形划分为6份2/d*3/d的小矩形，其对角线的长度为5/6d，小于d,故S1中的任意一个点只需和S2中的6个点比较即可，最终确定最短的距离。 2.取中位数： 为了减少算法的时间开销，需要将所有的点对进行分组，以中位数为基准，考虑到快速排序的不稳定性，本次排序使用了合并排序。 代码实现： template 实验名称： 最大子段和问题 实验目的： 了解最大子段和问题 实验环境： 操作系统：Windows XP Professional SP3 机器配置：Intel Pentium4 CPU 3.0GHz , 512MB 内存 开发工具：eclipse 实验内容： 1. 求数列的最大子段和(要求时间复杂为nlogn) (算法设计与分析 吕国英 清华大学出 版社 135页 4..3.3 二分法变异) （分治法） （也可用动态规划算法 参看递归王晓东计算机算法设计与分析第三版p61页） 算法的设计思想： 在对分治法德算法分析中注意到，若记???? ? ? <=<==∑=j i k k a n j i i b ][max ][，1<=j<=n,则所求的 最大子段和为： ][1max ][1max 1max ][1max j b n j k a j i n j k a n j i j i k j i k <=<== <=<=<=<==????? ?<=<=<=∑ ∑== 分为两种情况： （1）、当b[j-1]>0时，b[j]=b[j-1]+a[j]。 （2）、当b[j-1]<0时，b[j]=a[j]。 由此可得计算b[j]的动态规划递归式为： b[j]=max }{][],[]1[j a j a j b +-,1<=j<=n 由分析可知：次算法一共比较了n 次，故： T(n)=O(n) 据此可以写出如下程序： 实验步骤： 程序代码如下： package s; public class Po{ public static void main(String[] args) { int[] a=new int[10]; int[] b=new int[10]; int[] x=new int[10]; int start=0; int end = 0; System.out.print("数组为:");//随机赋值 for(int i =0;i<10;i++){ a[i]=(int)(Math.random()*100-50); System.out.print(a[i]+" "); } System.out.print("\n"); tem(a,x,b); int max=maxSum(a,b,end); System.out.print("最大子段和为:"); System.out.println(max); System.out.print("结束位置为:"); System.out.println(findend(a,b,end)); int begin=findStart(a,b,start,end); System.out.print("开始位置为："); System.out.println(begin); systemout(x,start,end,a,b); } public static void tem(int a[],int x[],int b[]) {int n=a.length-1; int sum=0; b[0]=x[0]; 一、算法分析 该算法的问题描述为：给定二维平面上的点集，求解距离最近的两个点，并计算出两点间的距离。 解决问题最初的思路为穷举法。对所有两点间的组合计算其距离。然后对其进行比较，找出最小值即可。不过这样做的缺点是时间复杂度和空间复杂度十分庞大，消耗巨量资源。如有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时，一共计算三次距离，并取其最小值。 项目编码规范 （一）命名规范 Java包、类的命名应尽量采用完整的英文描述符，一般采用小写英文字母，但类名、接口名以及任何非初始单词的第一个字母要大写，不能用完整英文描述的，应以该英文单词的前四个字母或能代表单词意思的缩写代替。具体如下： （1）尽量使用完整的英文描述符； （2）采用合适于相关领域的术语 （3）采用大小写混合使名字可读 （4）尽量少用缩写，确有需要的，要能表达其意义； （5）避免使用长的名字（小于15个字母） （6）避免使用类似的名字，或者是大小写不同的名字； （7）避免使用下划线（除静态常量等）； 举例如下： 包(packge) 采用完整的英文描述符，应该都是由小写字母组成。对于全局包，将你的internet域名反转并接上包名。如：com.boyi.eim,com.boyi.oa.web 类(Class) 采用完整的英文描述符，所有单词的第一个字母大写。如：User,StuManager 接口(interface) 采用完整的英文描述符说明接口封装,所有单词第一个字母大写。名字后面加上后缀Dao，实体类实现接口加上后缀Impl 类变量：采用完整的英文描述符，第一个字母小写，后所有单词的第一个字母大写。如：userName 参数：同上 获取成员函数:封装字段，被访问时调用get set方法 普通成员函数：采用完整的英文描述符，第一个字母小写，后所有单词的第一个字母大写。 静态常量字段：全部采用大写字母，单词之间用下划线分隔。 循环计数器：通常采用字母I,j,k…………….. 数组：采用完整的英文描述符，第一个字母小写，后所有单词的第一个字母大写 （二）代码注释 良好的注释习惯对于一支程序来说，是其易于解读的关键。也就是说，如果另一个编程人员从未见过这段代码，要在合理的时间内理解代码，需要知道哪些信息。并以此作为注释的依据。因此对于注释来说，需要注意以下几点： （1）注释应该增加代码的清晰度； （2）保持注释的简洁； （3）在写代码之前写注释 （4）注释出为什么做了一些事，而不仅仅是做了什么 使用代码注释的目的: （1）文字说明代码的作用(即为什么要用编写该代码,而不是如何编写); （2）确指出该代码的编写思路和逻辑方法; （3）人们注意到代码中的重要转折点; （4）使代码的阅读者不必在他们的头脑中仿真运行代码的执行方法. 代码注释原则： 1. 用文字说明代码的作用:简单的重复代码做写什么,这样的注释几乎不能给注释增加什么信息.如果你使用好的命名方法来创建直观明 了的代码那么这些类型的注释绝对增加不了什么信息. 2. 如果你想违背好的编程原则,请说明为什么：有的时候你可能需要违背好的编程原则，或者使用了某些不正规的方法，.遇到这种情况 时,请用内部注释来说明你在做什么和为什么要这样做。技巧性特别高的代码段，一定要加详细的注释，不要让其他开发人员花很长时间来研究一个高技巧但不易理解的程序段。 3. 用注释来说明何时可能出错和为什么出错 4. 在编写代码前进行注释：给代码加注释的方法之一是在编写一个方法前首先写上注释.如果你愿意,可以编写完整句子的注释或伪代码. 分治法求最大子段和问题 共有四种方法： 算法一； 算法二； 算法三、Divide and Conquer 算法四源代码、On-line Algorithm 算法一源代码： /*Given (possibly negative) integers A1, A2, …, AN, find the maximum value. 找最大子段和*/ #include 假设在一片金属上钻n 个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。 如果不用分治法，问题非常容易解决。也就是蛮力法。 代码如下： #include { 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/2412128573.html,/p-198711591.html?qq-pf-to=pcqq.c2c 代码如下： #include 分治法 【摘要】：分治法可以通俗的解释为：把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。本文主要叙述了分治法的设计思想及与之有关的递归思想，了解使用分治法解决问题的过程。 【关键词】：分治法分解算法递归二分搜索 Partition Method （Junna Wei） 【abstract 】: the partition method can explain to popular: decomposition, put a slice of territory is decomposed into several pieces of small, then pieces of land occupation of conquest, the decomposition can be different political factions or something, then let them each other alienation. This paper mainly describes the design idea of the partition method and recursive thinking, related to understand the process of solving the problem using the partition method. 【key words 】: partition method decomposition algorithm recursive Binary search 1.引论 1.1需求规格说明书 需求规格相当于软件开发的图纸，一般说，软件需求规格说明书的格式可以根 据项目的具体情况采用不同的格式，没有统一的标准。下面是一个可以参照的 软件需求规格说明书的模板。 1．导言 1.1目的 [说明编写这份项目需求规格的目的，指出预期的读者] 1.2背景 说明： a）待开发的产品名称； b）本项目的任务提出者、开发者、用户及实现该产品的单位； c）该系统同其他系统的相互来往关系。 1.3缩写说明 [缩写] [缩写说明] 列出本文件中用到的外文首字母组词的原词组。 1.4术语定义 [术语] [术语定义] 列出本文件中用到的专门术语的定义。 1.5参考资料 [编号]《参考资料》[版本号] 列出相关的参考资料。 1.6版本更新信息 具体版本更新记录如表所列。 表版本更新记录 2．任务概述 2.1 系统定义 本节描述内容包括： ●项目来源及背景； ●项目要达到的目标，如市场目标、技术目标等； ●系统整体结构，如系统框架、系统提供的主要功能，涉及的接口等； ●各组成部分结构，如果所定义的产品是一个更大的系统的一个组成部分， 则应说明本产品与该系统中其他各组成部分之间的关系，为此可使用一张 方框图来说明该系统的组成和本产品同其他各部分的联系和接口。 2.2 应用环境 本节应根据用户的要求对系统的运行环境进行定义，描述内容包括： ●设备环境； ●系统运行硬件环境； ●系统运行软件环境； ●系统运行网络环境； ●用户操作模式； ●当前应用环境。 2.3 假定和约束 列出进行本产品开发工作的假定和约束，例如经费限制、开发期限等。列出本产品的最终用户的特点，充分说明操作人员、维护人员的教育水平和技术专长以及本产品的预期使用频度等重要约束。 3．需求规定 1.1对功能的规定 本节依据合同中定义的系统组成部分分别描述其功能，描述应包括： ●功能编号； ●所属产品编号； ●优先级； ●功能定义； ●功能描述。 1.2对性能的规定 本节描述用户对系统的性能需求，可能的系统性能需求有： ●系统响应时间需求； ●系统开放性需求； ●系统可靠性需求； ●系统可移植性和可扩展性需求； ●系统安全性需求； ●现有资源利用性需求。 1.2.1精度 说明对该产品的输入、输出数据精度的要求，可能包括传输过程中的精度。 1.2.2时间特性要求 说明对于该产品的时间特性要求，如对： a）响应时间； b）更新处理时间； c）数据的转换和传送时间； d）计算时间等的要求。 1.2.3灵活性 说明对该产品的灵活性的要求，即当需求发生某些变化时，该产品对这些变化的适应能力，如： a）操作方式上的变化； b）运行环境的变化； c）同其他系统的接口的变化； d）精度和有效时限的变化； e）计划的变化或改进。 对于为了提供这些灵活性而进行的专门设计的部分应该加以标明。 1.3输入输出的要求 解释各输入输出的数据类型，并逐项说明其媒体、格式、数值范围、精度等。 对软件的数据输出及必须标明的控制输出量进行解释并举例，包括对硬拷贝报 最近点对问题 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 一、调试下面的程序，并回答问题。 .global _start .text _start: LDR SP, =src LDMFD SP!,{R0-R6} STMFD SP!,{R0-R6} LDMFD SP!,{R3} LDMFD SP!,{R4} LDMFD SP!,{R5} LDMFD SP!,{R6} LDMFD SP!,{R0} LDMFD SP!,{R1} LDMFD SP!,{R2} stop: b stop .ltorg src: .long 1,2,3,4,5,6,7 .end 问：该程序完成了什么功能？ 答： 该程序完成的功能：先把数据区堆栈中的1~7这七个数据送给R0~R0寄存器，然后又把寄存器列表中的R0~R7存入堆栈，然后又依次把堆栈中的1~7这七个数送给R3~R6,R0~R2,然后程序就结束了，在取数和存数的过程中。堆栈指针sp由0x0000变到0x8030再到0x804c，然后到0x8030，然后依次加4，最后到0x804c；程序计数器R15（PC）由0x8000地址依次加4 。 二、LDMFD,STMFD伪代码实现的原理。 答： 指令STMFD和LDMFD分析： 根据ATPCS规则，我们一般使用FD（Full Descending）类型的数据栈！所以经常使用的指令就有STMFD和LDMFD， 通过ARM对于栈操作和批量Load/Store指令寻址方式，可以知道指令STMFD和LDMFD 的地址计算方法： STMFD指令的寻址方式为事后递减方式(DB) 而DB寻址方式实际存地址为： start_address = Rn - (Number_Of_Set_Bits_In(register_list)*4) end_address = Rn - 4 STM指令操作的伪代码： if ConditionPassed(cond) then address = start_address for i = 0 to 15 if register_list[i] == 1 Memory[address] = Ri address = address + 4 有上面两个伪代码可以得出STMFD SP！，{R0-R7，LR} 的伪代码如下：SP ＝SP －9×4； address =SP; for i = 0 to 7 Memory[address] = Ri; address= address + 4; Memory[address] = LR; LDMFD指令的寻址方式为事后递增方式(IA) IA存的实际地址的伪代码 start_address = Rn end_address = Rn + (Number_of_set_bits_in(register_list)*4) - 4 LDM指令操作的伪代码(未考虑PC寄存器)： if ConditionPassed(cond) then address = start_address for i = 0 to 15 if register_list[i] == 1 Ri ＝Memory[address,4] address = address + 4 所以LDMFD SP！，{R0-R7，PC}^ （；恢复现场，异常处理返回）伪代码是: address = SP; for i = 0 to 7 Ri = Memory[address ,4] address = address + 4; SP = address; 作业2 一、用移位操作完成（R0）*10运算。 参考程序： .text .global _start 平均情况:设待查找的元素在数组中的概率为P，不在数组中的概率为1-P,若出现在数组中每个位置的概率是均等的为p/n T(n)=P1D1+P2D2+...+PiDi+(1-P)Dn+1 =p/2+n(1-p/2) 1.叙述分治算法和动态规划算法的基本思想，并比较两种算法的异同。答:分治法将待求解的问题划分成K个较小规模的子问题,对这K个子问题分别求解,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解. 动态规划将待求解的问题分解成若干的子问题，自底向上地通过求解子问题的解得到原问题的解。动态规划将每个子问题只求解一次并将其解保存在一个表格中,当需要再次求解此子问题时,只是简单的通过查表过的该子问题的解,避免了大量的重复计算. 异同：分治法求解的问题分解后的子问题都是独立的，而使用动态规划求解的问题分解后得到的子问题往往不是相互独立的。 分治法是自顶向下用递归的方法解决问题，而动态规划则是自底向上非递归解决问题。 1.简述分治算法求解过程的三个阶段。 答:（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。 （2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。 （3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。 2.叙述分治法的基本思想，并分析分治法与减治法二者的区别。 答：分治法将待求解的问题划分成K个较小规模的子问题,对这K个子问题分别求解,再将子问题的解合并为一个更大规模的问题的解,自底向上逐步求出原问题的解. 区别：分治法是把一个大问题划分成若干个子问题，分别求解各个子问题，然后把子问题的解进行合并并得到原问题的解。减治法同样是把一个大问题划分成若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，因而也无需对子问题的解进行合并。 3.设计分治算法求一个数组中最大元素的位置，建立该算法时间复杂性的 递推式并给出其复杂性的大O表示。 答：设数组a1,a2...an int maxpos(a[],i,j); {if(i==j) return i; mid=(i+j)/2; lmaxpos=maxpos(a,i,mid); rmaxpos=maxpos(a,mid+1,j); if(a[lmaxpos]>=a[rmoxpos]) return lmaxpos; else return rmaxpos;} T(1)=O(n) n=1; T(n)=2T(n/2)+O(1) n>1; 一、实验目的 1．理解分治法的方法； 2. 掌握使用分治法解决一般问题的步骤； 3. 掌握分治算法求解数组的最大值和最小值的方法。 二、实验原理 在一个给定数组中查找最大值和最小值是一类常见的问题，也是解决其他一些算法的基础。 假设给定数组为a，数组中含有n个元素，一般的算法是在数组中进行直接 循环的次数在算法第2行给出，为(n-2)+1=n-1次，因此，算法元素比较总次数为2(n-1)次。 现在采用分治的思想，假设数组的长度为2的整数幂，将数组分割成两半，分别为a[0…(n/2)-1]和a[n/2…n-1]，在每一半中分别查找最大值和最小值，并返回这两个最小值中的最小值以及两个最大值中的最大值。 假设给定数组为a，数组的下标上界和下界分别为low和high，则其算法伪 接比较数组的两个元素，选出最大值和最小值，此为函数的递归终止条件；代码第7行和第8行是两个递归调用，分别在数组的下标范围[low,mid]和 [mid+1,high]查找最小值和最大值，第9行比较两个最大值取其中较大者，第10行比较两个最小值取较大者。 代码的第2、9和10行涉及到元素的比较，第7、8行由于递归也产生元素比较，因此令算法总的元素比较次数为C(n)，则有 ???>+==2 2)2/(221)(n n C n n C 若若 对递推式进行求解 2 2/3 2 2)2/( 2)2(2 2 2...22)2/(2 ... 2 48)8/(824)2)8/(2(4 2 4)4/(42)2)4/(2(22)2/(2)(1 1122111-=-+=+=+++++==+++=+++=++=++=+=∑-=-----n n C n C n C n C n C n C n C n C k k j j k k k k k 得到minmax 算法的元素比较总次数为3n/2-2，优于直接比较的性能。 三、实验内容及要求 1. 编写程序使用分治算法MINMAX 求解数组的最小值和最大值，并用实际数组对算法进行测试。 2. 要求算法中元素比较的次数为3n/2-2，在程序中元素比较的地方进行记录，并在程序末尾输出数组最大值和最小值以及元素比较次数。 四、实验步骤 1. 定义结构体类型或类，用以在函数的返回值同时返回数组的最大值和最小值。0007算法笔记——【分治法】最接近点对问题
伪代码
算法练习题-分章节-带答案
算法分析与设计 实验三 最大子段和问题
项目开发详细设计说明书(超好用实用模板),完整版
分治法实验报告一
最接近点对问题实验报告
最大子段和动态规划法
算法实验四_空间最近点对算法
项目编码规范
分治法求最大子段和问题
最近点对分治法
分治法
软件开发过程文档规范
最近点对问题
嵌入式系统原理及应用题目要求+程序代码
算法(复习题)1
-实验1分治法
相关主题
文本预览