/目录1问题描述2解决方案2.1减治法原理叙述 2.28枚硬币规模解法 2.3n枚硬币规模解法     在8枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币。 1）深刻理解并掌握减治法的设计思想并理解它与分治法的区别； 2）提高应用减治法设计算法的技能。 3）理解这样一个观点：建立正确的模型对于问题的求解是非常重要的。 1）设计减治算法实现8枚硬币问题； 2）设计实验程序，考察用减治技术设计的算法是否高效； 3）扩展算法，使之能处理n枚硬币中有一枚假币的问题。   假设用一个数组B[n]表示硬币，元素B[i]中存放第i枚硬币的重量，其中n-1个元素的值都是相同的，只有一个元素与其他元素值不同，则当n=8时即代表8枚硬币问题。由于8枚硬币问题限制只允许使用天平比较轻重，所以，算法中只能出现元素相加和比较的语句。&...

/目录1问题描述 2解决方案 2.1 堆排序原理简介 2.2 变治法原理简介 2.3 具体编码 2.4 运行结果截图  （1）实验题目   用基于变治法的堆排序算法对任意一组给定的数据进行排序（2）实验目的   1）深刻理解并掌握变治法的设计思想；   2）掌握堆的概念以及如何用变治法把任意给定的一组数据改变成堆；   3）提高应用变治法设计算法的技能。（3）实验要求   1）设计与实现堆排序算法；   2）待排序的数据可以手工输入(通常规模比较小，10个数据左右），用以检测程序的正确性；也可以计算机随机生成（通常规模比较大，1500－3000个数据左右），用以检验(用计数法)堆排序算法的时间效率。 堆可以定义为一颗二叉树，树的节点中包含键（每个节点是一个键），并且满足下面两个条件：（1）树...

/目录1问题描述2解决方案2.1 动态规划法原理简介2.2 具体编码2.3 运行结果  （1）实验题目   给定一个加权连通图(无向的或有向的)，要求找出从每个定点到其他所有定点之间的最短路径以及最短路径的长度。（2）实验目的  1）深刻掌握动态规划法的设计思想并能熟练运用，理解它与分治法的区别；  2）掌握最优性原理和最优子结构性质；  3）理解这样一个观点：用动态规划方法求解问题的关键在于确定动态规划函数的递推式。（3）实验要求  1）实现Floyd算法；  2）算法的输入可以手动输入，也可以自动生成；(PS:此处对于有向图的权重矩阵手动输入有点麻烦，故本文只实现已给定的权重矩阵值，计算最终结果)  3）算法不仅要输出从每个顶点到其他所有顶点之间的最短路径，还有输出最短路径的长度；  4）设计一个权重为负的图或有向图的例子，对于它，Floyd算法不能输出正确的结果。...

/目录1问题描述2解决方案2.1贪婪法原理简介2.2哈夫曼树及编码简介2.3具体编码2.4运行结果  设计一种策略，使在下面的游戏中，期望提问的次数达到最小。有一副纸牌，是由1张A，2张2,3张3，...9张9组成的，一共包含45张牌。有人从这副牌洗过的牌中抽出一张牌，问一连串可以回答是或否的问题来确定这副牌的点数。  贪婪法的核心是，所做的每一步选择都必须满足以下条件：（1）可行的：即它必须满足问题的约束。（2）局部最优：它是当前步骤中所有可行选择中最佳的局部选择。（3）不可取消：即选择一旦做出，在算法的后面步骤中就无法改变了。这些条件即要求：在每一步中，它要求“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择，能够产生一个整个问题的（全局的）最优解。哈夫曼树，树中所有的左向边都标记为0，而所有的右向边都标记为1.可以通过记录从根到字符叶子的简单路径上的标记来获得一个字符的哈夫曼编码。示例：  要了解哈夫曼树，首先了解一下哈夫曼算法，哈夫曼算法满足以下两步：第一步：初始化n个单节点的树，并为它们标...

/目录1问题描述2解决方案2.1选择排序原理简介2.2具体编码（选择排序）2.3冒泡排序原理简介 2.4具体编码（冒泡排序）给定一个可排序的n元素序列（例如，数字、字符和字符串），将它们按照非降序方式重新排列。选择排序开始的时候，我们从第一个元素开始扫描整个列表，找到它的最小元素，然后和第一个元素交换，将最小元素和第一个元素交换位置；然后，我们从第二个元素开始扫描剩下的n-1个元素，找到这n-1个元素中的最小元素，将最小元素和第二个元素交换位置；然后从第三个元素开始扫描...一般来说，就是从第i个元素开始扫描，找到第n-i+1个元素中的最小元素，将最小元素与第i个元素交换位置。这样，在进行n-1次遍历后，该列表就排好序了。packagecom.liuzhen.chapterThree;publicclassSelectionSort{publicstaticvoidgetSelectionSort(int[]a){intmin=0;//用于存放n-i序列中最小元素序号inttemp=0;//交换数组元素值的中间变量//打印输出未排序前数组序列System.out.print(...

给定一个n个字符组成的串（称为文本），一个m（m<=n）的串（称为模式），从文本中寻找匹配模式的子串。 packagecom.liuzhen.chapterThree;publicclassBruteForceStringMatch{//根据文本串N，和模式串M，返回第一个匹配模式串的子串在N中的位置publicstaticintgetStringMatch(int[]N,int[]M){intn=N.length;//文本串的长度intm=M.length;//模式串的长度for(inti=0;i<n-m;i++){//最后一轮子串匹配的起始位置是n-m，如果大于n-m一定不会出现匹配子串intj=0;while(j<m&&M[j]==N[i+j])j=j+1;if(j==m)returni;}return-1;}publicstaticvoidmain(Stringargs[]){int[]N={1,2,3,2,4,5,6,7,8,9};int[]M={6,7,8};intposition=getStringMatch(N,M);Syst...

给定一组数据，使用插入排序得到这组数据的非降序排列。  引用自百度百科：有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。packagecom.liuzhen.chapterFour;publicclassInsertionSort{publicstaticvoidgetInsertionSort(int[]A){intlen=A...

给定一组数据，请使用希尔排序获取这组数据的非降序序列。 希尔排序的实质就是分组插入排序，该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小,即增量大小为1）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。我们来通过以下示意图，更深入的理解一下具体原理（PS：图中gap为增量）：packagecom.liuzhen.chapterFour;publicclassShellSort{publicstaticvoidgetShellSort(int[]A){intlen=A.length;intx=0;//定义进行希尔排序的次数for(intgap=len/2;gap>=1;gap=gap/2){//步长System.out.print("第"+x+"次...

ComputetheGreatestCommonDivisorofTwoIntegersusingSieveofEratosthenes.翻译：使用埃拉托色尼筛选法计算两个整数的最大公约数。（PS：最大公约数也称最大公因数，指两个或多个整数共有约数中最大的一个）  引用自百度百科：埃拉托色尼筛选法(theSieveofEratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes274B.C.～194B.C.)提出的一种筛选法。是针对自然数列中的自然数而实施的，用于求一定范围内的质数，它的容斥原理之完备性条件是p=H~。具体求取质数的思想：（1）先把1删除（现今数学界1既不是质数也不是合数）（2）读取队列中当前最小的数2，然后把2的倍数删去（3）读取队列中当前最小的数3，然后把3的倍数删去（4）读取队列中当前最小的数5，然后把5的倍数删去（5）如上所述直到需求的范围内所有的数均删除或读取下面看一下执行上述步骤求不大于100的所有质数的一个示意图：  本文求取两个数的最大公约数，采用质因数分解法：把每个数分别分解质因数，...

/目录1问题描述2解决方案 2.1递归法2.2非递归法  SimulatethemovementoftheTowersofHanoiPuzzle;Bonusispossibleforusinganimation.e.g.ifn=2;A→B;A→C;B→C;      ifn=3;A→C;A→B;C→B;A→C;B→A;B→C;A→C;翻译：模拟汉诺塔问题的移动规则；获得奖励的移动方法还是有可能的。 相关经典题目延伸：引用自百度百科：有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子一个一个移动到柱子C上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动，设移动次数为H(n）。 首先我们肯定是把上面n-1个盘子移动到柱子B上，然后把最大的一块放在C上，最后把B上的所有盘子移动到C上，由此我们得出表达式：H...

给定一组数据，使用合并排序得到这组数据的非降序排列。  引用自百度百科：合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（DivideandConquer）的一个非常典型的应用。合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。     下面看一下具体排序示例： 排序性能分析：  packagecom.liuzhen.chapterFive;publicclassMergesort{//使用合并排序，获取数组A的非降序排列publicstaticvoidgetMergesort(int[]A){intlenA=A.length;//数组A的长度if(lenA>1){int[]B=copyArray(A,0);//获...

/1问题描述2解决方案2.1快速排序原理简介2.2具体编码 给定一组数据，使用快速排序得到这组数据的非降序排列。  引用自百度百科：快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C.A.R.Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 具体排序过程：设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。 一趟快速排序的算法是：1）设置两个变量i、j，排序开始的时候：i=0，j=N-1（PS：即i从数组前开始向后遍历，j从数组后开始向前遍历）；2）以第一个数组...

/1问题描述2解决方案2.1蛮力法 给定一个平面上n个点的集合，它的凸包就是包含所有这些点的最小凸多边形，求取满足此条件的所有点。另外，形象生动的描述：（1）我们可以把这个问题看作如何用长度最短的栅栏把n头熟睡的老虎围起来。（2）也可以这样看：请把所讨论的点想象成钉在胶合板上的钉子，胶合板代表平面。撑开一根橡皮筋圈，把所有的钉子都围住，然后啪一声松开手。凸包就是以橡皮圈为边界的区域。具体示意如下图1所示：  图1 用橡皮筋来解释凸包  使用蛮力法解决此问题比较简单，具体思想：对于一个n个点集合中的两个点p1和p2，当且仅当该集合中的其它点都位于穿过这两点的直线的同一边时，它们的连线就是该集合凸包边界的一部分，简言之，p1和p2就是凸包问题中最小凸多边形的顶点。对每一对点都做一遍检验之后，满足条件的线段就构成了该凸包的边界。此时，根据上面的公式，我们只需要把每个点代入公式ax+by-c，判断公式计算结果的符号是否全部大于等于0或者小于等于0，如果是则是凸包边界上的点，否则就不是。该算法的时间效率为0（n^3）。具体代码如下：&n...

/目录1问题描述2解决方案2.1问题化简2.2定位输出测试2.3回顾总结  最近两天在思考如何使用蛮力法解决旅行商问题（此问题，说白了就是如何求解n个不同字母的所有不同排序的序列问题，即共有n!次不同排序）。为此，我认真看了一篇出自CSDN上的博客文章，其中有一段核心代码就是在for循环里面添加一句递归调用语句，来实现n!次排序。因此，我对文章中的那段核心代码苦苦不得其解——其执行顺序究竟是咋样的呢？附其简要代码：publicintcount=0;publicvoidArrange(int[]A,intstart,intstep,intn,intMax){if(step==2)System.out.println("第"+(++count)+"次走完一圈");if(count==Max)System.out.println("已完成！！！");else{for(inti=start;i<n;i++){swapArray(A,start,i);Arrange(A,start+1,step+1,n,Max);swapArray(A,i,st...

/目录1问题描述2解决方案2.1蛮力法2.2减治法2.2.1Johson-Trotter算法2.2.2基于字典序的算法 何为旅行商问题？按照非专业的说法，这个问题要求找出一条n个给定的城市间的最短路径，使我们在回到触发的城市之前，对每个城市都只访问一次。这样该问题就可以表述为求一个图的最短哈密顿回路的问题。（哈密顿回路：定义为一个对图的每个顶点都只穿越一次的回路） 很容易看出来，哈密顿回路也可以定义为n+1个相邻顶点v1,v2,v3,...,vn,v1的一个序列。其中，序列的第一个顶点和最后一个顶点是相同的，而其它n-1个顶点都是互不相同的。并且，在不失一般性的前提下，可以假设，所有的回路都开始和结束于相同的特定顶点。因此，可以通过生成n-1个中间城市的组合来得到所有的旅行线路，计算这些线路的长度，然后求取最短的线路。下图是该问题的一个小规模实例，并用该方法得到了它的解，具体如下： 图1使用蛮力法求解旅行商问题  此处使用蛮力法解决旅行商问题，取的是4个城市规模，并已经定义好各个城市之间的距离（PS：该距离使用二维数组初始化定义，此处的...