六种常用算法

显示全部楼层 · 2009-8-22 11:24:03

有条不紊——递推法破解难题
问：“我对数据结构有了一定了解，但还是不太懂程序。从经典公式“程序=算法+数据结构”得知，是因为不了解算法。能不能介绍几种简单的算法，当然从最容易懂的那种开始了？”
答：“算法就是能够证明正确的解题步骤，算法有许多种，最简单的无非下面的六种：递推法、贪心法、列举法、递归法、分治法和模拟法。刚听名字挺吓人的，其实有好多程序我们平常都见过。这些算法当中，最最简单的莫过于递推算法了。下面举例说明。”
什么是递推法
递推法这种解题方法其实在我们编程的过程中用的很多，只不过没有将其上升到理论的高度罢了。所谓递推法，就是找出和时间先后相联系或和数的大小相联系的步骤，上一步和下一步和数字的增大或减小有一定的联系。我们要么从前向后（或从小到大）推导，也可从后向前（或从大到小）推导。由此得出两种推导方法：顺推法和倒推法。请看下面的示例。
示例：猴子分食桃子
五只猴子采得一堆桃子，猴子彼此约定隔天早起后再分食。不过，就在半夜里，一只猴子偷偷起来，把桃子均分成五堆后，发现还多一个，它吃掉这桃子，并拿走了其中一堆。第二只猴子醒来，又把桃子均分成五堆后，还是多了一个，它也吃掉这个桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。那么桃子数最少应该有几个呢？
编程简析
怎样编程呢？先要找一下第N只猴子和其面前桃子数的关系。如果从第1只开始往第5只找，不好找，但如果思路一变，从第N到第1去，可得出下面的推导式：
第N只猴第N只猴前桃子数目
5
s5=x
4
s4=s5*5/4+1
3
s3=s4*5/4+1
2
s2=s3*5/4+1
1
s1=s2*5/4+1
s1即为所求。上面的规律中只要将s1-s5的下标去掉：
s=x
s=s*5/4+1
s=s*5/4+1
s=s*5/4+1
s=s*5/4+1
所以可以用循环语句加以解决。
综观程序的整体结构，最外是一个循环，因为循环次数不定，可以使用While循环，其结束条件则是找到第一个符合条件的数。为了做出上面while循环的结束条件，还需进一步分析上述规律的特点，要符合题目中的要求，s1-s4四个数必须全部为整数，这个可作为条件。具体实现请参看源程序。

语言、界面、源程序
（1）语言
程序中通过Virual BASIC6.0语言来实现。
（2）界面
界面非常简单，建立一标准EXE工程，其caption设为“猴子分食桃子”,一切OK。我们将代码加给Form_Click()即窗体的单击事件，将来运行时，我们只要用鼠标单击一下窗体，程序就执行了。
（3）源程序
Option Explicit
Private Sub Form_Click()
Dim x, s, k, i As Integer '声明变量
x = 6
k = 0 '整除标志
While k4
s = x '第5只猴子时总数
k = 0
For i = 4 To 1 Step -1 '第4-1只时的数量
s = s * 5 / 4 + 1
If Int(s) = s Then '符合情况则将整除标志加1
k = k + 1
End If
Next i
x = x + 5 '第次增5
Wend
Print s '输出
End Sub
(上程序在VB60 Win2000下调试通过)
小结
上面应用的推导方法就是倒推法。生活中的更多问题采用顺推法就可得到，也即从1-N，但不论倒推还是顺推，能递推出并解出问题是我们的本意。

千问 · 2009-8-22 11:24:03

稳扎稳打——贪心法破解难题
问：“算法除了递推法，该轮到贪心法了吧，从字面上理解，这种方法有些贪得无厌还是…？”
答：“基本算法中的递推法是我们最常使用的，贪心法是另一种有意思的算法。贪心法不仅仅是贪婪，而且是每一步都贪婪！下面举例说明。”
什么是贪心法
贪心法就是做一种目前最贪婪的行动，一步步解决问题。贪心法和递推法有相似之外，也是从问题的某一个初始解出发，向给定的目标递推，但不同的是每一步不是依据某一个固定的递推式，而是做一个当时看似最佳的贪心选择，不断地将问题归结为更小的相似的问题。
示例：删数问题
链盘输入一个高精度的数N，去掉任意S个数字后剩下的数字按原左右次序组成一个新的正整数，编程对于给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。
为了便于操作，将N做为字符串的形式输入，可以使用尽可能逼近目标的贪心算法来完成，删数的过程中是一个一个进行删除的，为了保证最后得到的数最小，每一步总是要删除使剩下的数最小的数字。之所以做出这样贪心的选择，是因为删S个数字的最优解，包含了删除一个数字的子问题的最优解。
为了实现上述目的，我们可以进行S次选择，每次都选择N中最大的数字，此数字选择后将不再参与下次的选择。具体实现请看源程序。

语言、界面、源程序
（1）语言
程序中通过Virual BASIC6.0语言来实现。
（2）界面
界面非常简单，建立一标准EXE工程，其caption设为“删数问题”。放入三个文本框和两个按钮，文本框起到输入两个数和输出结果的作用，按钮用来控制执行，再放入三个标签起到说明的作用。
（3）源程序
Private Sub CmdDelnum_Click()'开始删数按钮
Dim i As Integer
Dim j As Integer
Dim n As String '原数
Dim s As Integer '删数的个数
Dim nlength As Integer 'N的长度
Dim a() As Integer '放位数数组
Dim k As Integer '记录最大值位置
TxtOutput.Text = ""
n = TxtNum.Text
s = Val(TxtS.Text)
nlength = Len(n)
ReDim a(nlength - 1)
'将各位的值放入数组
For i = 0 To nlength - 1
a(i) = Mid(n, i + 1, 1)
Next i
'执行贪心算法s步
For j = 1 To s
k = 0
For i = 1 To nlength - j

If a(k) = 10 Then
monkey = 1
Else
monkey = 2 * (monkey(x + 1) + 1)
End If
End Function
我们定义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增量有关的两重嵌套循环就能将排序功能实现。详细源程序如下：
Sub shellsort(ByVal n As Integer) '希尔排序子程序
Dim i, j, gap As Integer
Dim k,xAs Integer
gap = Int(n / 2) '置初值
While gap > 0
For i = gap + 1 To n
j = i - gap
While j > 0
If a(j) < a(j + gap) Then

x = a(j)

a(j) = a(j + gap)

a(j + gap) = x

j = j - gap
Else

j = 0
End If
Wend
Next i
gap = Int(gap / 2)’减小增量
‘输出结果
TxtList.Text = TxtList.Text + Str(gap) + ":"
For k = 1 To n
TxtList.Text = TxtList.Text + Str(a(k)) + "."
Next k
TxtList.Text = TxtList.Text + vbCr + vbLf
Wend
End Sub
其他源程序
希尔排序按钮对应的源程序如下：
Private Sub CmdShell_Click() '希尔排序
Dim i As Integer
TxtList.Text = ""
Txtorigin.Text = ""
For i = 1 To 10 '输入原始数据
a(i) = Int(Rnd * 100)
Txtorigin.Text = Txtorigin.Text + Str(a(i)) + "."
Next i
'调用子程序排序并输出中间结果
Call shellsort(10)
End Sub
小结
在进行希尔排序时，需注意增量序列的取值方法，并且使这些序列中的值没有除1之外的公因子，且最后一个增量值必须为1。
能解决问题的办法都是好办法，问题不一定整体解决才好。这就是分治的思想。

千问 · 2009-8-22 11:24:03

乱打误撞——模拟法破解难题
问：“电脑解决确定问题可做到手到擒来，对于电脑中实现一个不确定的问题，例如彩票或抽奖，怎样做呢？”
答：“算法的美妙在于其准确和确定，而另有一种价值则在于其不确定，象我们的抽奖程序和彩票程序。确定的问题电脑可以处理，不确定的问题电脑也能处理，随机函数就是实现电脑中不确定事件的重要砝码。下面我们通过示例来看一下。”
随机函数的出现
通过语言编程一般来说对事物的认识是很确定的了，是一就是一，是二就是二，还有一个问题，有一些不那么确定的事情该如何处理，象我们的彩票抽奖，如果是确定的了，那也就不用抽了，恐怕也就没人玩了。
对于这一类的事情，该怎么办呢？语言中为我们提供了随机函数，也就是说通过它得到的一个值将是不能确定的。
随机函数产生的秘密
计算机常常需要模拟随机选择的数目，有多种不同的方法可以产生具有随机性质的数，由于通过此种系统的方法产生的不是真正的随机数，所以一般称做伪随机数。最常用的产生伪随机数的方法称为线性同余法。公式如下，选择四个数：模数m，乘数a，增量c和种数x0，使 2≤a<m, 0≤c<m, 0≤x0<m,可以生成一个伪随机序列{xn}，使得对于所有的n，0≤x0<m。生成的办法是逐次同余：
xn+1=(axn+c)mod m
应用和变通
随机函数有一个范围，即Rnd 函数返回小于 1 但大于或等于 0 的小数值。但通常我们要解的问题不在这个范围内，如何解决呢？
示例：最简单的抽奖程序，做一个猜1-100之间数的游戏。
因为随机函数的范围是一个0-1之间的小数，和题目要求的范围相差很大。所以，当我们用到的值不在这个范围之内时，我们可以想点变通的办法。要想做到从1-100之间进行取数，必须扩大100倍才行。不难计算RND*100的范围却不是1-100，而是0-100,不包括0和100，怎样就是1-100了呢？加上一就有了,范围成了1-101，不包括1和101，只要对得到的数只取整数，这个数只要这样表达就出来了，正好INT()函数起到这样的作用：
INT(RND*100+1)
所以程序也非常简单：
Private Sub Form_Click()’单击窗体
Print INT(RND*100+1)
End Sub
其中中间的代码就完成了我们题目的要求。
所以针对上述不确定的问题时，要利用好随机函数，并适当地对其做某些变通，这样问题就得到解决了。
小结
随机函数是程序设计中一道亮丽的风景。这个函数是非常有用的，她可能是计算机语言中唯一没有理性的东东了。就好象我们人类所具有的现省心的想法，妙手偶得之的佳句。正因为这个唯一性，也就不难看出她在计算机语言中的地位了。
""

千问 · 2009-8-22 11:24:03

收藏好东西

千问 · 2009-8-22 11:24:03

谢谢lz分享