分治法研究报告与应用

《分治法研究报告与应用》由会员分享，可在线阅读，更多相关《分治法研究报告与应用（12页珍藏版）》请在装配图网上搜索。

1、-分治法研究与应用学生：指导教师：淮南师范学院数学与计算科学系摘要：分治算法也叫分治策略，把输入分为若干个部分，递归的解每一个问题，最后将这些子问题合并成为一个全局解。如果子问题较大，可以再次使用分治策略。由此可以得到分治策略解决的问题特点：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。关键字：分治法、分治策略、javaPartition method to study and applicationStudent:songguo*ianInstructor :kongjunDep

2、artment of Mathematics and computational Science Huainan Normal UniversityAbstract：Partition algorithm also called partition strategies, put input into a number part, of the solution of the recursive every question, will ultimately these subproblems merged with a global solution if the son problem i

3、s bigger, can use again this can get partition strategies to solve the problem of partition strategies characteristics: the size of the problem down to a certain e*tent can easily resolve; This problem can be decomposed into some smaller the same problem; The separating the son of the solution of th

4、e problem of the original problem can merge solutions; The separating each subproblem is independent of each otherKey words:divide-and-conquer、Divide-Conquer algorithm、java前言在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序

5、算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)，任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。 n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，。 而当n较大时，问题就不则容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k

6、个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。 如果原问题可分割成k个子问题，1kn ，且这些子问题都可解并可利用这些子问题的解求出原问题的解，则这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。 分治法所能解决的问题一般具有以下几个

7、特征： 1) 该问题的规模缩小到一定的程度就可以容易地解决 2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 3) 利用该问题分解出的子问题的解可以合并为该问题的解； 4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划

8、法。第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。以及不存在有效算法的本质问题的惊人发现。这些结果点燃了计算机学者对算法研究的兴趣。算法设计与分析已成为一个受到广泛注意的领域。计算机的普及极大地改变了人们的生活。目前，各行业、各领域都广泛采用了计算机的信息技术,并由此产生出开发各种应用软件的需求。为了最少的成本，最快的速度,最好的 质量开发出适合各种应用需求的软件, 必须遵循软件工程的原则。 设计一个高效的程序不仅 需要编程小技巧, 更需要合理的数据组织和清晰高效的算法, 这正是计算机科学领域

9、数据结构与算法设计所研究的主要内容。 一些著名的计算机科学家在有关计算机科学教育的论述中认为, 计算机科学是一中创造性思维活动,其教育必须面向设计。计算机算法设计与分析正是一门面向设计,且处于计算 机学科核心地位的教育课程。 通过对计算机算法系统的学习与研究, 掌握算法设计的主要法 方法, 培养对算法的计算复杂性正确分析的能力, 为独立设计算法和对算法进行复杂性分析 奠定坚实的理论基础。 本程序主要采用分治法的思想, 在若干个数据中找出其中第 k 小的数。通过对实际问题 的分析,借鉴分治法的特点,并利用 java 语言编写具有合理的数据组织和清晰高效的算法的程序,从而达到解决实际的问题的目的。

10、正文2.1设计的目的和意义设计的目的随着科学技术的不断提高,计算机科学技术日渐成熟。我们应该要更多的学习计算机，并充分利用它为我们做出有用的事情。作为学信息与计算科学专业的我们更应该对它有着更深的学习，为了巩固自己学到的计算机知识、锻炼自己设计出一个具有合理的数据组织和清晰高效的算法、并将Java语言运用于实践，进一步巩固Java语言讲法规则和各种函数的使用。使自己能编写结构清晰、风格良好、逻辑严谨的java程序，从而具备解决综合性实际问题的编程能力。设计的意义通过对该问题的设计和解决，培养了自己运用经典算法的思想并综合利用Java语言编写程序解决实际问题的能力，通过分析实际问题再设计简单且可

11、行的算法去解决它的能力，加强算法的运用及对软件工程方法的初步认识，提高软件系统分析能力和程序文档建立、归纳总结的能力。2.2设计的目标与总体方案任何工程在创建之前总会有一个所需奋斗的目标，这样才能有追求的方向，还应有一个具体的方案，这样才可能着手进行实施。设计的目标通过设计要使程序在最后运行过程中达到理想的效果。首先，让用户统计要查找的元素的总数，并输入到系统中；其次，让用户依次输入预先准备好的数据；再次，让用户想要查找的第小的元素的值；最后，判断用户输入的值的大小是否符合要求，并告诉给用户，若符合要求，经过计算后，将查找的结果告诉给用户，结束该程序。设计的总体方案该程序主要运用分治法的思想。

12、首先，利用for循环的功能和数组的作用将用户输入的数据进行筛选，即将重复的元素去掉，留下没有重复数据的一组数组；再用while语句判断输入的k值是否符合要求；最后，将留下的数组以中位数为准，分成三个数组，并结合while语句的功能，实现循环，逐步将得到的新数组分成三个数组，直到符合用户的要求为止，并输出结果。总之通过实施整体方案，使可以工程运行，并且实现良好的运行效果，成为一个有利用价值的程序。 2.3设计的方法和内容该程序在住宿楼7A234的个人计算机上进行编写和调试，所用的软件。硬件环境要求CPU：Pentium III或更高级别，显卡：geforce 2及以上，内存：1G或更多，硬盘：1

13、00G或更多。软件环境需求操作系统：Windows*P，Windows7系统请在兼容模式下运行。必备的软件：eclipse;JDK1.6;my eclipse。设计的流程图图2-1为该程序的设计流程图，当用户进入运行界面后，按照提示先输入已准备好的数据的总数目，再依次输入各个元素；系统将数据进行整理后，等待用户输入k值的大小，并立即判断用户想要查找的数据是否存在；若存在，则用分治法的思想进行查找，找到后输出结果；最后，提示用户是否想继续查找另一个第k小的数，若用户想，则程序重复上述步骤，否则，结束程序。设计的方法及详细内容本程序可以分为四大模块：让用户输入信息、整理数据、查找数据并输出结果、询

14、问用户是否继续。.1让用户输入信息该部分可以让用户在运行程序的界面输入每个数据，用户可以根据实际需要，先输入预先准备查找的数据的总数目；再依次输入各个数据；最后输入k的具体数值，因需要考虑实际情况，对k的大小作了要求。代码如下：package com.song;import java.util.Scanner;publicclass ThesisDemo01 publicstaticvoid main(String args) Scanner input = new Scanner(System.in);System.out.println(请输入数据的长度);/提示用户输入int s = i

15、nput.ne*tInt();/输入数据int a;/建立数组a = newints;System.out.println(请依次输入数据);for(int i=0; i 0)System.out.println(请输入 K 的值！);/提示用户输入k的值int k = input.ne*tInt();/定义k的值为int类型/用if判断用户所输入的数字是否合理if(k s)System.out.println(对不起，你输入的数字太大！);/提示用户所输入的数字太大elsez-;开始让用户输入元素的总数依次输入所需的元素删除重复的数据让用户输入k的值否判断能否查到此数 能以中位数为准，将数组

16、分为三个数组 k=k-f-1e、f、g变为初值 e、f、g变为初值 小于中位数的元素的集合*iaof等于中位数的元素的集合Dengg大于中位数的元素的集合Daekk 大 小 于 于 f+1 f+1 k=f+1输出结果提示用户是否继续. 是 否结束图2-1 程序设计流程图.2数据整理此部分主要对用户依次输入的所有数据进行整理。即是将用户输入的每个数据元素依次存入到一个数组中，再对这个数组进行依次扫描，若没有发现了相同的元素，则将该元素存入到另一个数组中，否则，继续扫描，且不将该数存在另一个数组中。因为，这样可以方便地告诉用户他想要查找的第k小的数是否存在，也可以减小在后面用分治法查找数据时的时间

17、复杂度。其具体做法如下：序号： 1 2 3 4 5 6 7 8 9firsti 5 3 2 52 1 6 56a 5 原数组第1个数赋给a1 ，i+a 5 3原数组第2个数赋给a2 ，i+a 5 3 2 原数组第3个数赋给a3 ，i+a 5 3 2 first4=a1，a 5 3 2 first5=a3，i+a 5 3 2 1原数组第6个数赋给a4 ，i+a 5 3 2 16原数组第7个数赋给a5 ，i+a 5 3 2 16 first8=a1，i+a 5 3 2 16 first9=a7，i+ 结束经过整理后的数组a所存的元素分别为5、3、2、1、6，且将用户输入的元素的总数目变为5。其主要

18、代码是：a1= first1; /根据常规，可首先将数组first 中的第一个数赋给a for(i=1;I= s;i+)/依次取first 中的数与a 中数进行比较length+;/数组a的长度加1for(j=1;jlength;j+)if(aj= firsti) /若a中有与firsti相等的数，让a与firsti+1相比 length-;/因firsti不能存入a 中 break; else if(aj!= firsti)if(j=length) /判断a 中的数是否全部与firsti不相等 j+; else alength= firsti;/将first i存入a 中.3查找数据并输出结

19、果这个部分是此程序的核心，因为该部分主要是为了减小查找的时间复杂度，用分治法的思想来完成，先在a中选出一个数（中位数）并赋给*，并以*为基准，将a分为三部分。第一部分元素都大于*，第二部分元素都小于*，第三部分元素等于*（即该部分中只有*）。设第二部分中的元素个数为f，若kf+1,则第k小的元素在第一部分中，继续用类似的方法对第三部分进行处理。它也是在编写程序时遇到的最大困难。具体的实例如下:分别定义三个数组da、*iao、deng存储数组a分成的三部分,用e、f、g分别记录这三个数组所存储的元素的个数，先令k=3。alength 5 3 2 1 6 *=a(length+1)/2=a3=2d

20、a 5 e+，i+da 5 3 e+，i+deng 2 g+，i+*iao 1 f+，i+da 5 3 6 e+，i+ 结束，e=3；f=1；g=1比较k与f+1的大小，则第k(k=3)小的数在da中，k=k-f-1=1，将da中的元素依次赋给a中，并使e=f=g=0。alength 5 3 6 *=a(length+1)/2=a2=3da 5 e+，i+deng 3 g+，i+da 5 6 e+，i+ 结束，e=2；f=0；g=1比较k与f+1的大小，显然k=f+1。所以第k小的数查找成功，输出结果3，即为用户想要在他输入的一组元素里(5 3 2 5 2 1 6 5 6)查找的第3小的数。该

21、部分的关键代码是：while(k0)*=a(s+1)/2;/将a的中位数赋给变量*dengg=*; for(i=1;i*)/将a分成三部分 e+; dae=ai; else if(ai*) f+; *iaof=ai; else g+; dengg=ai;if(kf+1) /判断第k小的数在哪个数组中s =f;/使a的长度变为该数组的长度e=f=0;g=1;/让变量变为初值，保证程序能正常运行for(i=1;i f+1) /与上类似k=k-f-1;ai=dai;else k=0;/改变条件，结束此循环，并输出结果System.out.println(“你所要查找的数据时：” + deng1);.

22、4询问用户是否继续该部分是此程序的尾声，表面上看起来不是特别的重要，但是，为了提高程序的可用性和可扩展性，能够推向市场进行使用，是作为一个程序的设计和开发者必须考虑的方向。在此为了锻炼自己的综合能力，随之进行了简单的设计。主要目的是为了给用户带来方便，让用户只进行一次数据输入，就可以查找出任意第k小的数，也可以随时退出程序。主要代码是：:System.out.println(“你想继续查找想要的数据吗.请输入Y或者N：”);/提示用户是否继续Scanner input = Scanner(System.in);String s = input.ne*t();/让用户输入他的选择信息System

23、.out.println(); while(null != s & “” != s)/判断用户输入的信息是否符合要求 System.out.println(“你想继续查找想要的数据吗.请输入Y或者N：”);/告诉用户输入的信息有误，并重新输入 if( s =0) /判断用户的选择z=1; elseSystem.out.println(“请按任意键继续”);根据最后调试好的程序，并假设用户在输入指令时有不符合要求的指令，并且在看到结果后还重复查看过其他第k小的数。运行的结果如图2-2、图2-3所示，图2-2 此程序运行的前部分结果图2-3 此程序运行的后部分结果2.4设计的创新与关键技术设计的特

24、点本程序设计的主要特点体现在：利用数组和for循环语句存储用户首次输入的需要查找的数据，再用for语句对该数组进行扫描，将重复的元素删除，即把没有重复的元素存在另一个数组。用分治法的思想将修改后的数组分成三部分，并判断第k小的数是否已经找出，若找出，则输出结果；否则，继续。用while语句合理地控制了循环，增强了程序的可读性，增强了程序的实用性。设计的难点本程序设计的难点主要是：要把用户输入数据进行处理，如果用户输入的元素里面有重复的数据，可能不会得到正确的结果，将数据进行处理后在后面还会减少用分治法处理数组的时间复杂度，但是在编写本部分的代码是总是出错，因为涉及的变量太多，并且要同时在两个数

25、组里面进行扫描。在使用分治法的思想处理数组时，偶尔出现不符合逻辑的错误，输出的结果与设计者的要求甚远。用for语句实现循环，容易造成死循环。软硬件调试及结果分析在程序的编写和调试过程中，由于有重复的语句和多次用到if 语句和数组以及for语句，给调试造成了一定的困难，但由于程序结合紧密,逻辑性较强，流程清晰，最后还是顺利完成了调试；在硬件方面由于该工程要求硬件环境较低，所以对于硬件的调试非常顺利，没有出现任何问题。由于该程序的代码主要采用了教材中比较常见的结构和语句，无特殊或较难的超纲知识点，因此在编写整个程序的过程中比较顺利，代码也符合逻辑。程序运行结果较令人满意，程序的每条代码都起到了其相

26、应的作用。2.5结论经过两个星期的实践，使我对是我对java语言，算法分析和设计有了更进一步的了解，并且认识到了运用经典算法的思想解决一些实际问题是非常有意义的，最主要的是可以减小时间复杂度，所以我认为我们必须加强这方面的学习。经过这次设计是我对java语言有了更进一步熟悉，也巩固了数据结构和Java开发过程中的知识点,更明白了学好java语言重在实践，将理论联系实际才有利于更好地学习和掌握各个重点。经过这一段时间的实践，我对自己有以下认识：要运用自如地使用一个java算法，必须先弄清楚它的完整思想以好解决实际问题的过程，这样才可以让算法在自己的程序中发挥出最大的作用和优势，就可以编写出具有合

27、理的数据组织和清晰高效的算法的完美程序我在实践的时候发现自己有很多的不足之处，特别是有时候缺乏耐心。因为每一个程序在初步编写完成的时候经常是语法或者是运行时错误，不一定就能运行，以至于接下来就是要花大量的精力去仔细地调试，力争达到自己想要达到的目的。我认为在实践过程中仔细和严谨的态度是成功的关键，它锻炼了我们的能力，可以说将理论用于实践是我们今后走向工作岗位的一个很好的锻炼平台，我们应该紧紧地抓住这个机会，好好地锻炼。此工程完全达到了预期的目标，但是还有些地方欠妥，例如：对算法的理解还不够透彻，然而在解决实际问题时，显得不够水平，运用了一个很好的算法的思想，但解决的问题比较简单，这需要自己进一

28、步完善，力争让自己加深对各个算法的理解程度。从编写代码的角度来看还有点不够精练，总觉得有点累赘，但也不知道该怎么改。我觉得这就是我的缺陷，在以后的学习中应该要更加努力学习。致谢首先感谢我敬爱的老师孔军老师. 我之所以能顺利地完成这次实践操作是因为他在本学期给我们不辞辛劳地授课而让我获得了课程设计中必要的基础知识. 在做次项目之前也帮我出了很多的宝贵的意见,使我的程序变得具有更多的更好的功能,让程序的时间复杂度到最小.还给我讲解如何去解决在完成本次项目中遇到的实际困难.最后,感谢我的室友和同学,他们在*些地方给了我极大的帮助和支持。在此,我再次衷心地感谢帮助过我的老师和同学.参考文献：. 1 J

29、AVA核心技术卷II：高级特性（原书第8版）（美）霍斯特曼等著，陈昊鹏等译机械工业出版社.2Java编程思想（中文版第4版）美）埃克尔 著/2007-04-01/机械工业出版社.3算法设计与分析导论/李家同(Lee,R.C.T)等著;王卫东译.-北京:机械工业出版社.4数据结构与算法/齐德显编著.-北京:清华大学出版社,2003 .5Java语言程序设计基础篇（原书第6版）（美）梁著，万波 译/2008-06-01/机械工业出版社.6傅清祥,王晓东.算法与数据结构.北京:电子工业出版社,1998 2003.6 109-142 .7数据结构Java语言描述（美）缅因 著，孔芳 等译/2007-0

30、7-01/机械工业出版社.8殷人昆,陶永雷,谢若阳,盛绚华.数据结构.北京:电子工业出版社,2001 210-239.9 计算机算法的设计与分析/(美)阿霍(Aho,A.V.),(美)霍普克劳夫特(Hopcroft,J.E.), (美)乌尔曼(Ullman,J.D.)著; 黄林鹏, 王德俊, 张仕译.-北京: 机械工业出版社, 2007.7.10Java JDK6学习笔记（台湾）林信良 著/2011-05-01/清华大学出版社.11算法导论（原书第2版）（美）科曼（Cormen,T.H.） 等著，潘金贵 等译/2006-09-01/机械工业出版社.13数据结构与算法分析Java语言描述 第2版（美）韦斯（Weiss，M.A.）著，冯舜玺译/2009-01-01/机械工业出版社.14 java编程技术谭浩强 主编/2003-04-01/人民邮电出版社. z.