六种常用算法

六种常用算法有条不紊 递推法破解难题问：“我对数据结构有了一定了解，但还是不太懂程序。从经典公式“程序=算法+数据结构”得知，是因为不了解算法。能不能介绍几种简单的算法，当然从最容易懂的那种开始了？”答：“算法就是能够证明正确的解题步骤，算法有许多种，最简单的无非下面的六种：递推法、贪心法、列举法、递归法、分治法和模拟法。刚听名字挺吓人的，其实有好多程序我们平常都见过。这些算法当中，最最简单的莫过于递推算法了。下面举例说明。”什么是递推法递推法这种解题方法其实在我们编程的过程中用的很多，只不过没有将其上升到理论的高度罢了。所谓递推法，就是找出和时间先后相联系或和数的大小相联系的步骤，上一步和下一步和数字的增大或减小有一定的联系。我们要么从前向后（或从小到大）推导，也可从后向前（或从大到小）推导。由此得出两种推导方法：顺推法和倒推法。请看下面的示例。示例：猴子分食桃子五只猴子采得一堆桃子，猴子彼此约定隔天早起后再分食。不过，就在半夜里，一只猴子偷偷起来，把桃子均分成五堆后，发现还多一个，它吃掉这桃子，并拿走了其中一堆。第二只猴子醒来，又把桃子均分成五堆后，还是多了一个，它也吃掉这个桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。那么桃子数最少应该有几个呢？编程简析怎样编程呢？先要找一下第N只猴子和其面前桃子数的关系。如果从第1只开始往第5只找，不好找，但如果思路一变，从第N到第1去，可得出下面的推导式：第N只猴第N只猴前桃子数目5 s5=x4 s4=s5*5/4+13 s3=s4*5/4+12 s2=s3*5/4+11 s1=s2*5/4+1si即为所求。上面的规律中只要将s1-s5的下标去掉：s=xs=s*5/4+1s=s*5/4+1s=s*5/4+1s=s*5/4+1所以可以用循环语句加以解决。综观程序的整体结构，最外是一个循环，因为循环次数不定，可以使用While循环，其结束条件则是找到第一个符合条件的数。为了做出上面while循环的结束条件，还需进一步分析上述规律的特点，要符合题目中的要求，s1-s4四个数必须全部为整数，这个可作为条件。具体实现请参看源程序。语言、界面、源程序（1）语言程序中通过VirualBASIC6.0语言来实现。界面界面非常简单，建立一标准EXE工程，其caption设为“猴子分食桃子”，一切OK。我们将代码加给Form_Click()即窗体的单击事件，将来运行时，我们只要用鼠标单击一下窗体，程序就执行了。源程序OptionExplicitPrivateSubForm_Click()Dimx,s,k,iAsInteger'声明变量x=6k=0'整除标志Whilek<>4s=x'第5只猴子时总数k=0Fori=4To1Step-1'第4-1只时的数量s=s*5/4+1IfInt(s)=sThen'符合情况则将整除标志加1k=k+1EndIfNextix=x+5'第次增5WendPrints'输出EndSub（上程序在VB60Win2000下调试通过）小结上面应用的推导方法就是倒推法。生活中的更多问题采用顺推法就可得到，也即从1-N，但不论倒推还是顺推，能递推出并解出问题是我们的本意。稳扎稳打 贪心法破解难题问：“算法除了递推法，该轮到贪心法了吧，从字面上理解，这种方法有些贪得无厌还是…？”答：“基本算法中的递推法是我们最常使用的，贪心法是另一种有意思的算法。贪心法不仅仅是贪婪，而且是每一步都贪婪！下面举例说明。”什么是贪心法贪心法就是做一种目前最贪婪的行动，一步步解决问题。贪心法和递推法有相似之外，也是从问题的某一个初始解出发，向给定的目标递推，但不同的是每一步不是依据某一个固定的递推式，而是做一个当时看似最佳的贪心选择，不断地将问题归结为更小的相似的问题。示例：删数问题链盘输入一个高精度的数N,去掉任意S个数字后剩下的数字按原左右次序组成一个新的正整数，编程对于给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。为了便于操作，将N做为字符串的形式输入，可以使用尽可能逼近目标的贪心算法来完成，删数的过程中是一个一个进行删除的，为了保证最后得到的数最小，每一步总是要删除使剩下的数最小的数字。之所以做出这样贪心的选择，是因为删S个数字的最优解，包含了删除一个数字的子问题的最优解。为了实现上述目的，我们可以进行S次选择，每次都选择N中最大的数字，此数字选择后将不再参与下次的选择。具体实现请看源程序。语言、界面、源程序（1） 语言程序中通过VirualBASIC6.0语言来实现。（2） 界面界面非常简单，建立一标准EXE工程，其caption设为“删数问题”。放入三个文本框和两个按钮，文本框起到输入两个数和输出结果的作用，按钮用来控制执行，再放入三个标签起到说明的作用。（3） 源程序PrivateSubCmdDelnum_Click（）'开始删数按钮DimiAsIntegerDimjAsIntegerDimnAsString'原数DimsAsInteger'删数的个数DimnlengthAsInteger'N的长度Dima()AsInteger'放位数数组DimkAsInteger'记录最大值位置TxtOutput.Text=""n=TxtNum.Texts=Val(TxtS.Text)nlength=Len(n)ReDima(nlength-1)'将各位的值放入数组Fori=0Tonlength-1a(i)=Mid(n,i+1,1)Nexti'执行贪心算法s步Forj=1Tosk=0Fori=1Tonlength-jIfa(k)<a(i)Thenk=iEndIfNextid=a(k)Fori=kTonlength-1-ja(i)=a(i+1)Nextia(nlength-j)=dNextj'输出结果Fori=nlength-1Tonlength-sStep-1'删数过程TxtOutput.Text=TxtOutput.Text+"删除的第”+Str(nlength-i)+"个数”+Str(a(i))+vbCr+vbLfNexti'最后的数Fori=0Tonlength-s-1TxtOutput.Text=TxtOutput.Text+Str(a(i))NextiEndSub(上程序在VB60Win2000下调试通过)小结这就是有趣的贪心算法，说是贪得无厌可以，说是守住当前的既得利益，以此为基础，再稳扎稳打地进行下一步也行！滴水不漏一列举法破解难题问：“列举法是种什么样子的算法呢？”答：咧举法是比贪心法还要贪得多的算法，歹U举法也是一种比较笨但却很有效的算法，他想要的东东，一种情况他都不想落下，大有宁可错杀一千，不可放过一个的阵势。下面举例说明。”什么是列举法列举是针对问题所有的可能一一查看是不是符合条件，有些“宁肯错杀一千，不可放过一个”的作风。下面的老题最能说明这种情况。示例：百钱买百鸡公鸡3元每只，母鸡5元每只，小鸡1元3只，一百元钱买一百只鸡。请求出公鸡，母鸡和小鸡的数目。编程简析我们做最极端的假设，公鸡可能是0-100，母鸡也可能是0-100，小鸡还可能是0-100，将这三种情况用循环套起来，那就是1000000种情况。这就是列举法。为了将题目再简化一下，我们还可以对上述题目进行一下优化处理：假设公鸡数为x,母鸡数为y，则小鸡数是100-x-y，也就有了下面的方程式：3*x+5*y+(100-x-y)/3=100从这个方程式中，我们不难看出大体的情况：公鸡最多有33只，最少是没有，即x的范围是0-33；母鸡最多20只，最少0只，即母鸡的范围是0-20；有了公鸡母鸡，小鸡数自然就是100-x-y只。可能的方案一共有34*21种，在这么多的方案中，可能有一种或几种正好符合相等的条件。电脑怎样工作呢？计算机事实上就是将上述34*21种方案全部过滤一遍，找出符合百钱买百鸡条件的(也即上式)，只要符合，这就是我们要的输出结果。程序实现我们怎样将这34*21种方案罗列出呢？这么多的方案，最好的办法是还是用循环。可用循环和循环的嵌套，一个关于公鸡数和一个关于母鸡数的循环套起来，就能将所有的方案都遍历。后面的问题成了怎样判断哪一个方案是我们寻找的符合条件和方案呢？只能根据百钱买百鸡了，即3*x+5*y+(100-x-y)/3=100作为条件，在条件成立的一方输出x,y,和100-x-y的值就行了，这是分支要解决的问题，程序的整体结构有了，两个嵌套循环中套分支。界面源程序界面非常简单，建立一标准EXE工程，其caption设为“百钱买百鸡”，一切OK。我们将代码加给Form_Click()，即窗体的单击事件，将来运行时，我们只要用鼠标单击一下窗体，程序就执行了。源程序如下：OptionExplicitPrivateSubForm_Click()Dimx,yAsInteger'声明变量Forx=0To33Fory=0To20If3*x+5*y+(100-x-y)/3=100ThenPrint"公鸡，母鸡和小鸡数分别为：”;x,y,100-x-yEndIfNextyNextxEndSub(上程序在VB60Win2000下调试通过)题目的结果有多组，正和我们刚开始的所想相符。小结这就是列举法，将可能的情况一网打尽；不过在应用过程中，我们最好还是做些优化，不然，要浪费好多没必要浪费的时间。镜里照镜一递归法破解难题问：“前几种办法的确名如其法，比较笨。有没有比较潇洒一点的算法？递归属不属于些类算法呀？”答：“递归一种非常奇妙和美妙的算法形式，奇妙美妙的背后是比较难理解。但用起来却异常简洁。”什么是递归说白了递归就象我们讲的那个故事：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：山上有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：......也就是直接或间接地调用了其自身。就象上面的故事那样，故事中包含了故事本身。因为对自身进行调用，所以需对程序段进行包装，也就出现了函数。函数的利用是对数学上函数定义的推广，函数的正确运用有利于简化程序，也能使某些问题得到迅速实现。对于代码中功能性较强的、重复执行的或经常要用到的部分，将其功能加以集成，通过一个名称和相应的参数来完成，这就是函数或子程序，使用时只需对其名字进行简单调用就能来完成特定功能。函数又可分为自定义的和系统附带的，但不管是自定义的还是系统的，他们都对相应的功能进行了封装，以利于我们经常性地使用。例如我们的对一个小数取整数INT()函数，不论什么样的小数，往()中一放，将来得到的值就自动将小数去除了。函数执行完将返回一个值，当然这个值可以是各种类型的，子程序仅仅执行一个过程，不返回数值。函数和子程序是执行递归的干将。示例：小猴吃枣小猴第一天摘下若干枣子，当即吃掉了一半，不过瘾又多吃了一个；第二天吃了剩下的一半又多吃了一个；以后每一天都吃了前一天剩下的一半多一个。到第十天小猴再想吃时，见到只剩下一只枣子了。问第一天这堆枣子有多少？从上题中我们可看到一个令人欣喜的规律，第十天为1，第九到第一天中后一天与1的和的两倍与前一天相等。下面就对这一规律做了描述：PrivateFunctionmonkey(ByValxAsInteger)AsIntegerIfx>=10Thenmonkey=1Elsemonkey=2*(monkey(x+1)+1)EndIfEndFunction我们定义monkey()函数的时候通过monkey()自身来进行了定义，这就是递归。递归是个特殊的循环，是一个有着非常美妙的循环规则的循环。上题中我们只要将monkey(1)，即第一天打印出来，一切OK。而这中间究竟是怎么工作的，我们可以不管。正是有了monkey()函数，在对其自身调用的过程中实现了我们的所求，关于函数、子程序和他们之间发生的故事还有很多，仅仅列举了其中奇妙的几点，还有许多东东等着您的发现和利用。小结函数和子程序是程序瘦身计划的一部分，通过它们可以使程序中的代码适当减肥，长度维持在一个更合理的位置。这种作用和循环的瘦身作用一起，使一个执行很长的代码可以变得很简洁。这也更适合我们利用计算机作为工具的目的：人类做尽量少的工作，计算机仍能解决原先的问题。另一个奇妙之处是：他们创造了递归！各个击破一分治法破解难题问：“问题不能一下子解决，难道不能分开解决吗，有没有算法能实现各个击破以求解决问题呢？”答：“可以的，通过各个击破的方法解决问题的算法叫做分治法。下面我们通过示例来看一下。”什么是分治法为了解决一个问题，算法有时需不止一次地对自身进行调用，来解决相类似的子问题。这样的算法通常称为分治法：将原问题分成n个规模较小而结构与原问题相似的子问题。下面通过排序的一种方法来看一下。希尔排序即是采用分治法来进行排序的，又称做缩小增量排序，其思想是：把已经在数组中的数据按下标的一定增量分组，对分出的每一小组使用插入排序，随着增量逐渐减小，所分成的组包含的数据越来越多，直到减小到1时，整个数据合并成一组，构成一组有序数，则完成排序。示例：十个数，从大到小排序。数据放在一个数组a(10)中，假如原始数据如下：70.53.57.28.30.77.1.76.81.70，则排序过程如下：增量值5:77.53.76.81.70.70.1.57.28.30.2:77.81.76.70.70.57.28.53.1.30.1:81.77.76.70.70.57.53.30.28.1.其中上面三个增量值对应的都是以该增量完成本轮排序后的情况，看增量为5时要和原始数据比较，增量为2的情况要和5比较，1要和2比较，这样其中的规律就清楚了。子程序如下要用实现希尔排序，关键是把握好增量的变化情况和最终结束的控制，设置变量gap为增量，其值取要排序的所有数据的个数的二分之一(本例中为5)，比较时先将第1个数同第6个比，较大的放到前面，较小的放到后面，2同7,直至全部比较完成；下一次用现在的gap的二分之一作为增量，再进行增量大小转换；…；当其为0时结束。原无序序列排成了有序序列了。从上面分析中不难看出，通过和gap增量有关的两重嵌套循环就能将排序功能实现。详细源程序如下：Subshellsort(ByValnAsInteger)'希尔排序子程序Dimi,j,gapAsInteger喜tf申测，(乙/d诟)mi=d诟!1xqnPUQMJIPUH0=19813

dt?§-f=fX=(dB§+f)B(dB§+f)B=(f)B("xuaqi(d诟+贝0<[anWdB§-1=fUO【[+dB§=TIOJ0<d优anw»段黑，(乙/u)mi=dB§igSajujsyx'nuitqTxtList.Text=TxtList.Text+Str(gap)+":"Fork=1TonTxtList.Text=TxtList.Text+Str(a(k))+"."NextkTxtList.Text=TxtList.Text+vbCr+vbLfWendEndSub其他源程序希尔排序按钮对应的源程序如下：PrivateSubCmdShell_Click(),希尔排序DimiAsIntegerTxtList.Text=""Txtorigin.Text=""Fori=1To10'输入原始数据a(i)=Int(Rnd*100)Txtorigin.Text=Txtorigin.Text+Str(a(i))+Nexti'调用子程序排序并输出中间结果Callshellsort(10)EndSub小结在进行希尔排序时，需注意增量序列的取值方法，并且使这些序列中的值没有除1之外的公因子，且最后一个增量值必须为1。能解决问题的办法都是好办法，问题不一定整体解决才好。这就是分治的思想。乱打误撞一模拟法破解难题问：“电脑解决确定问题可做到手到擒来，对于电脑中实现一个不确定的问题，例如彩票或抽奖，怎样做呢？”答：“算法的美妙在于其准确和确定，而另有一种价值则在于其不确定，象我们的抽奖程序和彩票程序。确定的问题电脑可以处理，不确定的问题电脑也能处理，随机函数就是实现电脑中不确定事件的重要砝码。下面我们通过示例来看一下。”随机函数的出现通过语言编程一般来说对事物的认识是很确定的了，是一就是一，是二就是二，还有一个问题，有一些不那么确定的事情该如何处理，象我们的彩票抽奖，如果是确定的了，那也就不用抽了，恐怕也就没人玩了。对于这一类的事情，该怎么办呢？语言中为我们提供