常用算法设计
概括地说，“算法”是指解题方案的准确而完整的描述。
对于一个问题，如果可以通过一个计算机程序，在有限的存储空间内进行有限长的时间而得到正确的结果，则称该问题是算法可解的。但算法不等于程序，也不等于计算方法。程序可以作为算法的一种描述，但程序通常还需考虑很多与方法和分析无关的细节问题，这是因为在编写程序时要受到计算机系统运行环境的限制。通常，程序设计的质量不可能优于算法的设计。
通常求解一个问题可能会有多种算法可供选择，选择的主要标准是算法的正确性和可靠性，简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。
算法设计是一件非常困难的工作，经常采用的算法设计技术主要有列举法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外，为了更简洁的形式设计和藐视算法，在算法设计时又常常采用递归技术，用递归描述算法。
1.列举法(穷举)
列举法的基本思想是根据提出的问题，列举所有可能情况，并用问题中提出的条件检验哪些是需要的，哪些是不需要的。因此，列举法常用于解决“是否存在”或“有多少种可能”等类型的问题。例如，求解不定方程
的问题可以采用列举法。
列举法的特点是算法比较简单，但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，应该重点注意使方案优化，尽量减少运算工作量。通常，只要对实际问题作详细的分析，将与问题有关的知识条理化、完备化、系统化，从中出规律，或对所有可能的情况进行分类，引出一些有用的信息，列举量是可以减少的。
先介绍“列举法”在易语言中实现的方法。易语言字符串转数组
列举法，顾名思义是列举出所有可能的情况，并用问题的条件来一一检验，并从中出符合要求的解。特点比较简单，但是在写列举算法时尽量过滤掉一些不必要的情况，优化算法。下面举一个例子，在易语言中编写代码实现，来说明列举法的基本思想，以及如何减少列举量。
大家都知道百鸡的问题吧！母鸡每只3元，公鸡每只2元，小鸡每只0.5元，计算一下如何100块钱买100只鸡。
计算中，只有以下两个条件成立，才输出结果。
母鸡数量+公鸡数量+小鸡数量=100只
3×母鸡数量+2×公鸡数量+0.5×小鸡数量=100元
列举所有可能的条件的代码如下：
可以看到，各层循环均需循环101次，因此总循环次数为1013，列举量太大。但只对问题稍加分析，很容易发现这个算法还可以改进，减少不必要的循环次数。
首先，考虑到母鸡为3元一只，因此，最多只能买33只母鸡，即算法中的外循环只需要从0到33就可以了，没有必要从0 到100。
其次，考虑到公鸡为2 元一只，因此，最多只能买50只公鸡。又考虑到对公鸡的列举是在算法的第二层循环中，因此，在第一层循环中已确定买母鸡数量的情况下，公鸡最多只能买50-母鸡数量，即第二层中对“公鸡”只需要从0到50-母鸡数量就可以了。
最后，考虑到总共买100只鸡，因此，在第一层循环中已确定买母鸡的数量，且第二层已确定买公鸡的情况下，买小鸡的数量只能是100-母鸡数量-公鸡数量，即第三层的循环已没有必要了。并且，在这种情况下，条件：母鸡数量+公鸡数量+小鸡数量=100只自然已经满足。
优化后的代码如下：
列举（穷举）所有可能情形，最直观的是联系循环的算法。但，循环层数的改变，就影响了这一问题的解，即没有一般性。例如：有多种鸡，而每种鸡的价格又不同，每次根据一个固定的金额购买某几种鸡。
程序名称：1列举法-百鸡.e
2. 递推法
所谓递推，是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。递推本质上也属于归纳法。许多递推公式，实际上是通过对实际问题的分析与归纳而得到的，因此，递推是归纳的结果。
也就是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N 的解，当N=1时，解或者已知，或者能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出问题规模为I的解。这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。
递推法中最具代表的就是阶乘法，下面采用分段乘法进行大数求阶乘。
在计算阶乘的时候，随着数字的增加，计算的结果会以极快的速度激增。当使用整数型数据储存结果时，当超过12时，计算结果将溢出；当使用长整数型数据储存结果时，当超过20时，计算结果将溢出。
为了能够计算较大的整数的阶乘并得到准确的结果，必须考虑适当的算法，分段乘法是其中的一种，将
每一步的中间结果使用数组分段储存，数组的一个成员储存一段数据，由于我们经常使用的是10进制，因此以10的n次方为标准进行分段是可行的。同时需要考虑分组相乘时，每组是否会出现溢出，因此数组的类型采用长整数型。
这里采用该算法写了一个模块，循环和数组配合，虽然能计算出正确的结果，但速度较慢，计算10000的阶乘需要50秒（最快的在1秒左右，大家可以使用Windows的计算器试试），计算50000的阶乘，耗时24分钟，估计不会有人尝试计算更大的数值。
分段相乘完毕后还要考虑每组的数值是否超过分段的标准，如果超过要进位。代码参见例程。
例程名称：2递推阶乘.e
3.递归算法
描述递归定义的函数或求解递归问题的过程称为递归算法。一个递归算法，本质上是将较复杂的处理归结为较简单的处理，直到最简单的处理。因此，递归的基础也是归纳。
下面学习易语言中递归算法的运用。
在易语言中许多地方可以用到递归算法，典型特征是自己调用自己。逐步到达条件边界，直到目的完成，如：“寻文件（）”等，递归算法结构比较简练，清晰易读，但，缺点是执行效率比较抵。
下面来练习寻的的写法。
首先需要作一个单独的寻子程序，如：名字取为“寻”，参数为“寻路径”文本型。
由于“寻文件（）”命令很特殊，好多初学者不好理解，因为寻文件每次只返回一个匹配对象，所以一定要用循环才可以到所有的匹配条件者，而第一次使用寻到一个匹配条件者，再继续寻其他文件就不需要指定寻文件条件了。
代码可分为三部分，代码如下：
第一部分，判断指定“寻路径”参数右边是否带“\”，如果不带，就自动加上。
第二部分是关键代码，首先调用
文件名＝寻文件 (寻路径＋“*.tmp”, )
因为只返回一个文本，所以用一个判断循环，判断“文件名”是否为空，如果不空继续寻，否者……
这部分只寻一个目录里所有匹配者，不会寻里面文件夹里的匹配者，当然不能放过它们，下面的代码就是：
第三部分是递归算法，等于子程序调用自己
寻(寻路径＋文件名)
就是这句，你也许会问
如果真 (取文本左边 (文件名, 1) ≠“.”)
是什么意思，其实就是判断文件名是不是文件夹，再XP命令提示符输入“dir”，一看就知道了。“.”是本级目录，“..”是上一级目录。
一定不要忘了在这个子程序里面加上
处理事件 ()
否则运行后机器会假死。
下面是另一个运用递归算法求最大公约数的例程，核心部分只用了6行代码，代码如下：
注意：％是求余数的运算符，不是除号，也不是百分号。
此例中求最大公约数，没有使用常用的短除算法，使用辗转相除法更便于编程。
程序名称：3.1递归算法.e
3.2递归算法.e
4.归纳法
了解算法的目的是提高大家的编程思路，优化编写代码的质量。
前面讲解过列举算法，它具有结构简单的优点，但是又有2个缺点：一是数据量大时效率低，二是当列举量无限时，列举算法就无效了。
下面学习一下归纳法。简单的说，就是列举少量的特殊情况，分析出一般的关系，但是实际问题中不是件容易的事。归纳即为抽象，对结果只是一种猜测（即归纳假象），所以必须严格的证明结果。
下面介绍一个典型的归纳法例子。
求n个自然数的平方之和。
Sn=12+22+32+…+n2
分析：
S1=12=1
S2=12+22=5
S3=12+22+32=14
S4=12+22+32+42=30
S5=12+22+32+42+52=55
S6=12+22+32+42+52+62=91
通过上速几个值，分析得出Sn与n之间的关系，
12/1=（2*1+1）/3 //1=1
（12+22）/（1+2）=（2*2+1）/3 //5/3=5/3
（12+22+32）/（1+2+3）=（2*3+1）/3 //14/6=7/3
（12+22+32+42）/（1+2+3+4）=（2*4+1）/3 //30/10=9/3
……
(12+22+32+...+n2)/(1+2+3+...+n)=(2n+1)/3

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。