论文分治法研究与应用

生活中用分治法解决问题的案例如下：

找出伪币

给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。

比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。

假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。

另外一种方法就是利用分而治之方法。假如把16个硬币的例子看成一个大的问题。

第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把16个硬币的问题分成两个8硬币的问题来解决。

第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。

最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。

假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。

这样16硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。

称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。

由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。

扩展资料：

解题步骤

分治法解题的一般步骤：

（1）分解，将要解决的问题划分成若干规模较小的同类问题；

（2）求解，当子问题划分得足够小时，用较简单的方法解决；

（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

参考资料来源：百度百科-分治算法

一、动态规划的基本思想在比较基本的算法设计思想里，动态规划是比较难于理解，难于抽象的一种，但是却又十分重要。动态规划的实质是分治思想和解决冗余，因此它与分治法和贪心法类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点。贪心法的当前选择可能要依赖于已经作出的选择，但不依赖于还未做出的选择和子问题，因此它的特征是由顶向下，一步一步地做出贪心选择，但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解。相比而言，动态规划则可以处理不具有贪心实质的问题。在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。比较感性的说，其实动态规划的思想是对贪心算法和分治法的一种折衷，它所解决的问题往往不具有可爱的贪心实质，但是各个子问题又不是完全零散的，这时候我们用一定的空间来换取时间，就可以提高解题的效率。二、动态规划的基本步骤动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可以按以下几个步骤进行：（1）找出最优解的性质，并刻画其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造一个最优解。其中（1）——（3）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省去。若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。三、典型的动态规划举例——矩阵连乘问题作为经典的动态规划算法举例，矩阵连乘问题很好地展现了动态规划的特点和实用价值。给定n个矩阵{A1,A2,...,An},其中Ai与Ai+1是可乘的，i=1,2,...n-1。现在要计算这n个矩阵的连乘积。由于矩阵的乘法满足结合律，所以通过加括号可以使得计算矩阵的连乘积有许多不同的计算次序。然而采用不同的加扩号方式，所需要的总计算量是不一样的。若A是一个p*q矩阵，B是一个q*r矩阵，则其乘积C=AB是一个p*r矩阵。如果用标准算法计算C，总共需要pqr次数乘。现在来看一个例子。A1，A2，A3分别是10*100,100*5和5*50的矩阵。如果按照((A1A2)A3)来计算，则计算所需的总数乘次数是10*100*5+10*5*50=7500。如果按照(A1(A2A3))来计算，则需要的数乘次数是100*5*50+10*100*50=75000,整整是前者的10倍。由此可见，在计算矩阵连乘积时，不同的加括号方式所导致的不同的计算对计算量有很大的影响。如何确定计算矩阵连乘积A1A2，...,An的一个计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少便成为一个问题。对于这个问题，穷举法虽然易于入手，但是经过计算，它所需要的计算次数是n的指数函数，因此在效率上显得过于低下。现在我们按照动态规划的基本步骤来分析解决这个问题，并比较它与穷举法在时间消耗上的差异。（1）分析最优解的结构。现在，将矩阵连乘积AiAi+1...Aj简记为A[i:j]。对于A[1:n]的一个最优次序，设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开(1<=k *max) *max= A; if(A < *min) *min= A; } } 上面这个算法需比较2(n-1)次。能否找到更好的算法呢？我们用分治策略来讨论。 把n个元素分成两组： A1={A[1],...,A[int(n/2)]}和A2={A[INT(N/2)+1],...,A[N]} 分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。 例如有下面一组元素：-13，13，9，-5，7，23，0，15。用分治策略比较的过程如下： 图中每个方框中，左边是最小值，右边是最大值。从图中看出，用这种方法一共比较了10次，比直接比较法的14次减少4次，即约减少了1/3。算法如下： void maxmin2(int A[],int i,int j,int *max,int *min) /*A存放输入的数据，i，j存放数据的范围，初值为0，n-1，*max,int *min 存放最大和最小值*/ { int mid,max1,max2,min1,min2; if (j==i) {最大和最小值为同一个数;return;} if (j-1==i) {将两个数直接比较，求得最大会最小值；return；} mid=(i+j)/2; 求i~mid之间的最大最小值分别为max1，min1; 求mid+1~j之间的最大最小值分别为max2，min2; 比较max1和max2，大的就是最大值; 比较min1和min2，小的就是最小值; } 利用分治策略求解时，所需时间取决于分解后子问题的个数、子问题的规模大小等因素，而二分法，由于其划分的简单和均匀的特点，是经常采用的一种有效的方法，例如二分法检索。运用分治策略解决的问题一般来说具有以下特点： 1、原问题可以分解为多个子问题，这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。 2、原问题在分解过程中，递归地求解子问题，由于递归都必须有一个终止条件，因此，当分解后的子问题规模足够小时，应能够直接求解。 3、在求解并得到各个子问题的解后，应能够采用某种方式、方法合并或构造出原问题的解。 不难发现，在分治策略中，由于子问题与原问题在结构和解法是的相似性，用分治方法解决的问题，大都采用了递归的形式。在各种排序方法中，如归并排序、堆排序、快速排序等，都存在有分治的思想。

论文中研究方法的应用

论文是一个汉语词语，古典文学常见论文一词，谓交谈辞章或交流思想。当代，论文常用来指进行各个学术领域的研究和描述学术研究成果的文章，简称之为论文。下面是我收集的论文中研究方法的应用，欢迎大家参考。

【摘要】：

硕士毕业论文是一个硕士研究生论文水平的重要表现，考察其论文的研究方法对于我们研究论文的研究方法有重要的帮助，本论文以华东师范大学思想政治教育专业20xx年和20xx年硕士毕业生硕士学位论文为研究对象。通过统计分析发现：马克思主义理论学科研究生的研究方法意识逐渐增强，呈现出多样化趋势，同时存在述而不用、理解不准确、运用不到位等问题。造成这些问题的主要原因就是缺乏研究方法的理论学习与实践训练。因此，应注重从增强研究生方法自觉、严格学位论文写作规范等方面不断提升学位论文研究方法运用水平。

【关键词】：

研究方法；硕士论文；思想政治教育

研究方法是科学研究的首要问题，贯穿科学研究的全过程。它上与认识论、方法论相连，下与理论性质、研究问题紧密相关，是保证研究成果科学性的前提和保障。

一、学位论文与研究方法

（一）研究生学位论文

研究生学位论文是衡量研究生科研能力和培养质量的重要手段。研究生学位申请者根据学位授予要求而撰写的研究论文。它是评判学位申请人学术水平的重要依据和获得学位的必要条件之一。学位论文质量的高低是衡量研究生科研水平高低的一个重要标志。

（二）研究方法

研究方法，也就是正确地提出问题、解决问题，是研究事实所不可缺少的理论原则、程序、手段、方式和技巧。是保证观察可靠、判断、推理得以正确形成的原则、程序、手段、方式。我国哲学社会科学学者秦宗熙和穆怀中、谢圣明认为社会研究方法的体系由三个不同层次构成，即一般方法、具体研究方法和具体的研究程序和研究技术。

首先，一般方法包括马克思主义哲学方法论、社会学的学科方法论以及逻辑方法论。其次，具体的研究方法包括文献法、个案法、访问法、问卷法、观察法、实验法、抽样法、社会测量法、典型法等。具体的研究程序和研究技术。最后，研究程序包括四个阶段即选题阶段、计划阶段、实施阶段和总结阶段。一般情况下，学生在论文写作上采取定性和定量研究相结合，采取文献法、历史法、比较法、统计分析法、问卷法、测验法、经验总结法等多种方法相结合使用。

二、思想政治教育硕士学位论文研究方法分析

硕士学位论文是一个硕士研究生写作水平的展现，而方法的运用则体现了作者研究过程中方法原则程序是否科学合理，这也就直接影响论文的质量和水平。通过分析得出思政研究生硕士学位论文以传统的理论思辨研究方法为主，缺乏科学的研究方法意识，缺少相应的实证与量化分析

（一）研究方法自陈状况分析

在抽样的华东师范大学2014、2015年30篇思想政治教育硕士学位论文中分析发现，从整体上而言，有90.1%的学位论文明确交代论文研究方法。能清晰单列“研究方法”部分并作“详细说明”和“简要说明”的学位论文的比例比较大，这说明，思想政治教育学科硕士论文的研究方法意识在已经比较高，研究的科学性从总体而言呈比较好的状态。当然，如果把自陈水平为详细说明和简要说明的论文判为“合格”的话，那么合格的比例仅仅有37%。

（二）研究方法的主要类别及其运用情况

总体分析后发现，马克思主义理论学科硕士学位论文运用的研究方法主要包括文献研究法、经验总结法、理论思辨法、比较研究法、历史研究法、调查研究法等。在30篇硕士学位论文中，以文献研究法为主要研究方法的占60%，排名第一；以思辨抽象法为主要研究方法的硕士论26%，排名第二；比较研究法为主占23%；其余还包括历史研究法、跨学科研究、调查研究等等占有一定比例。此外，100%的硕士论文的是融合两种方法以上的综合方法，融合的方式较为多样。

从以上可以看出，研究方法依然以经验研究和思辨研究等传统研究方法为主。文献研究法、思辨抽象法、历史研究法、比较研究法等传统研究方法备受青睐，其中文献研究法的使用率100%。新的实证研究方法，如调查研究、访谈法等开始进入马克思主义理论学科领域，使得研究方法更为丰富和多样化。

三、结论

（一）优点。通过分析30篇抽样可以得出思想政治教育专业硕士研究生在学位论文的写作中方法意识逐渐增强，通过本研究的调查分析发现过去单一的研究方法有所下降，对研究具有实际指导价值的学科层面方法论和原则层面方法论急剧增加，这表明高等教育研究的方法论出现了多元化趋向。从某种意义上可以说，研究方法论趋向多元化意味着研究者对研究方法论认识更加深人，这也意味着思想政治教育专业研究方法的多元化。

同时，具体研究方法和研究技术种类多样性，尽管定量与实证研究方法的整体运用中占比例不大，但从调查结果可以说明研究生们已经意识到定量与实证研究方法在研究中的重要性，通过定量与实证研究分析更能确定的各影响因素与结果之间的关系，从而得出科学的结论。研究技术的`这一层次是研究方法结构体系中与研究成果联系最为密切的层面。一定的研究方法论和研究方式最终必然要通过具体方法与技术才能展现出来。

（二）存在的不足。通过对样本的分析，可以得出，虽然在毕业论文中很多人都陈述了研究方法，但是研究方法陈述不够明确，甚至对研究方法本身并不是非常清楚，部分论文对研究方法敷衍了事，有的研究生将实证研究、思辨研究、定性研究、定量研究、定性与定量相结合、规范研究及跨学科研究、多学科研究当作研究方法。事实上，从哲学和科学方法的角度看，实证研究、定性研究、定量研究、定性与定量相结合及跨学科研究、多学科研究都是开展科学研究的一种指导思想，是方法论。如实证研究与之对应的有实验法、调查法等。

定性与思辩研究多，定量与实证研究少。定量研究与实证研究在研究科学性能够起到很重要的作用，从调查结果显示，虽然定量和实证研究有所增加，但从总体上而言，定量和实证研究还是很少。通过案例、实验、非实验、实地研究，用事实情况及真实数据更能有力地证实研究者的观点的文章少。调查数据显示，在研究生学位论文研究方法中以文献法、历史法、比较法这些以叙事性的定性研究为主导，从个人经验出发的感悟性、思辨性研究较多，说明定性研究仍是主要研究方法。虽然随着研究的深入及对研究的科学性的重视，定量与实证的方法逐步受到重视，但比较而言，运用的仍然较少。调查结果显示，在研究生学位论文中最常用的定量与实证的研究方法是调查法，最常用的统计分析方法是描述统计。方差分析、差异检验及显著性分析等定量方法在论文中少有出现。

综合上述分析，在培养学生论文写作方法上，我们应该更加注重方法意识，培养学生方法自觉，注重开设方法论课程的质量，提高研究质量，重视定量与实证研究，优化定性与思辨研究的结构，规范研究方法，树立科学研究意识，促进思想政教育学科理论发展。

《论算法设计中的分治与增量》