撒撒算法胡椒面儿调试程序做个伴儿

1、一、算法概述算法与过程过程与算法是解决问题的一种方法的逐步描述，(1)是由若干条指令组成的有穷序列；(2)每条指令的意义都是确定的；(3)具有零个或多个输入；(4)产生若干个输出；(5)算法要求其执行时间是有限的 (终止性) 。过程的执行时间可能是无限的。程序程序是某个算法或过程的在计算机上的一个具体的实现。程序是依赖于程序设计语言的，甚至依赖于计算机结构的。算法是脱离具体的计算机结构和程序设计语言的。算法的复杂性算法的复杂性是指算法运行时所需要的计算机资源的量多少，所需资源量越多则复杂性越高，反之所需资源量越少则复杂性越低。其中最为重要的是：时间复杂性：需要时间的资源量。空间复杂性：需要空间

2、的资源量。这里人们通常更为关注的是时间复杂性。决定算法复杂性的因素算法的复杂性取决于(1)求解问题的规模；(2)具体的输入数据；(3)算法本身的设计。二、递归与分治递归的概念简单地说，递归就是用自己来定义自己。一般地说，一个递归过程P可以表示为基语句S(不含P)和P自身的组合：P (S, P)这样的表示包含了过程不终止的可能，因此递归算法应更准确地表述为P if B then Q else (S, P) 其中Q也不包含P，B为递归终止条件。递归元递归算法的思想是将对较大规模的对象的操作归结为对较小规模的对象实施同样的操作。这种规模的变化就体现在递归算法的变元中的一类(一个或几个)变元上，这类变

3、元被称之为递归元。递归元的变化是在递归定义中确定的，它的变化应能导致递归算法的终止。在递归算法的设计中递归元是非常重要的。分治法分治法的基本做法是：(1)将规模为n的问题分解为k个规模较小的子问题。这些子问题相互独立且与原问题相同。(2)递归地解这些子问题。(3)然后将子问题合并得到原问题的解。分治法的时间复杂性：子问题的复杂性当然低于原问题。但是整体上能否降低复杂性还取决于合并。通过降低合并的复杂性可以降低原问题求解的复杂性。三、贪心算法贪心算法的特点贪心算法总是作出在当前来看是最好的选择。就是说，贪心算法并不从整体最优上来考虑，所作出的选择只是某种意义上的局部最优选择。当然希望贪心算法得到

4、的最终结果是最优的。可是贪心算法并不能保证最终结果是最优的。不过，在许多的情况下，应用贪心算法能够得到整体最优解；并且在一些情况下，即使得到的不是最优解，也是一个很好的近似解。贪心算法的一般框架初始化；重复执行以下的操作： 选择当前可以选择的(相容)最优解；将所选择的当前解加入到问题的解中；直至满足问题求解的结束条件。贪心算法的基本要素贪心算法的基本要素是：贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。贪心选择每次选取当前最优解，因此它依赖以往的选择，而不依赖于将来的选择。贪心算法通常以自顶向下的方式进行，每次贪心选择就将原问题转化为规

5、模更小的子问题。四、动态规划动态规划的基本思想将原问题分解为若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。这些子问题的解往往不是相互独立的。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。在算法中用表格来保存已经求解的子问题的解，无论它是否会被用到。当以后遇到该子问题时即可查表取出其解，避免了重复计算。动态规划的基本要素最优子结构：问题的最优解是由其子问题的最优解所构成的。重叠子问题：子问题之间并非相互独立的，而是彼此有重叠的。最优子结构性质使我们能够以自底向上的方式递归地从子结构的最优解构造出问题的最优解。因为子问

6、题重叠，所以存在着重复计算。这样就可以用填表保存子问题解的方法来提高效率。动态规划的基本方法动态规划通常可以按以下几个步骤进行：(1)找出最优解的性质，并刻画其结构特征；(2)递归地定义最优值；(3)以自底向上的方式计算出各子结构的最优值并添入表格中保存；(4)根据计算最优值时得到的信息，构造最优解。步骤13是动态规划算法的基本步骤。若需要最优解，则必须执行第4步，为此还需要在第3步中记录构造最优解所必需的信息。与分治法相比，相同之处是也将原问题分解为若干子问题，再递归求解；不同之处是所分解的子问题彼此并不独立，而是互有重叠。基本思想是造表记录已解的子问题，再次遇到时仅查表即可，避免了重复计算

7、，提高效率。通常用于求解具有最优性质的问题，而且其子问题也具有最优性质(最优子结构性质)。实现方法通常为自底向上的递归形式，但也可以采用自上而下的形式(备忘录方法)。五、回溯法回溯法是一种通用的算法，实为深度优先的搜索方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。八皇后问题就是回溯算法的典型，第一步按照顺序放一个皇后，然后第二步符合要求放第2个皇后，如果没有位置符合要求，那么就要改变第一个皇后的位置，重新放第2个皇后的位置，直到找到符合条件的位置就可以了。回溯在迷宫搜索中使用很常见，就是这条路走不通，然后返回前一个路口，继续下一条路。回溯算法说白了就是穷举

8、法。不过回溯算法使用剪枝函数，剪去一些不可能到达 最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。回溯法可以递归实现

9、，也可以迭代实现。回溯法通常求解三类问题：(1)求排列：时间复杂性为O(f(n)n!)；(2)求子集：时间复杂性为O(f(n)2n)；(3)求路径：时间复杂性为O(f(n)kn)。这里f(n)为处理一个结点的时间复杂性。六、分支限界法分支限界法是最佳优先搜索法分支限界法就是最佳优先(包括广度优先在内)的搜索法。分支限界法将要搜索的结点按评价函数的优劣排序，让好的结点优先搜索，将坏的结点剪去。所以准确说，此方法应称为界限剪支法。分支限界法中有两个要点：(1)评价函数的构造；(2)搜索路径的构造。七、概率算法概率计算概率计算就是在算法中可采用随机选择计算的步骤、元素或参数等。它的基本特征是计算具有

10、不确定性。它的解也不一定是最优解。它在很大程度上能降低算法的复杂度。在非标准算法中普遍了应用概率方法，主要有：(1)直接用概率进行数值计算；(2)用概率/随机进行选择；(3)利用概率加速搜索或避免陷于局部最优。进化算法达尔文的进化论：适者生存，优胜劣汰。1975年霍兰(Holland)提出了遗传算法，通过模拟生物进化的过程概率搜索最优解。遗传算法首先产生所谓的个体种群，每个个体是编码的二进制串(又称为染色体)。然后对个体进行随机的选择，再经过复制、交叉和变异产生下一代的种群。就这样经过一代一代的进化，最终获得满意的个体(即问题的解)。人工神经网络1943年McCulloch和Pitts提出神经

11、元的数学模型，即MP模型。1957年Rosenblatt设计制作了“感知机”。这是第一个多层的人工神经网络。第一个高潮期。1969年之后进入低潮。1980年以后重新进入高潮，并得到蓬勃的发展。目前人们普遍认为突破图林机模型的将是人工神经网络。这是下一代计算机的主体。人工神经网络人工神经网络就是人工神经元所构成的网络。主要有前馈网络和反馈网络两种形式。前馈网络有若干层神经元组成，第i层的神经元只接受第i1层输出的信息，而不接受同层或高层的输出信息。反馈网络中的神经元可以接受外加输入和其它神经元包括自身的反馈输入。人工神经网络的学习神经元的计算主要依赖于权重wi，而权重wi是通过学习获得的。所谓学

12、习(又称训练)是首先给权重赋予一个初值，然后将大量的训练样板(包括正例和反例)输入计算机，人工神经网络自己不断地调整相应的权重。学习的方式主要分为：有监督的学习和自适应的学习两种形式，以及它们的改进。八、调试代码的技巧 一、理解代码 二、休息休息 三、渐增式测试 先从单个模块开始测试，然后每次将测试后的一个模块添加到系统中并测试，系统像“滚雪球”一样越滚越大，直到把所有的模块都组装并测试完毕。四、务求简单 在调试的过程中你会把错误想得越来越复杂，所以这时务求简单。将代码按照功能和逻辑拆分会变得“务求简单”。 五、懂得放弃 不要舍不得代码修改代码原则寻找合适的代码记录每个修改通读源代码修改最少耦

13、合度最低寻找合适的代码修改代码不如自己重写代码，除非时间、人力方面不允许。 修改代码之前必须先读懂对方的源代码，这花的时间可能会比自己写花的时间更多。必须在这两者之间取得平衡。改变自身需求，使需求适应下载的代码，达到直接使用，无需修改。 比如你打算找一个实现某些功能的代码，可是找了很多代码，要不只能实现其中的某些功能，要不就是某些功能不完全符合你的要求，这时就必须改变自己最原始的想法，找一个最接近的代码。因为有时候你原先的需求就是错误的。寻找合适的代码代码必须架构合理，编码规范，这样的代码安全系数才比较高。源代码作者经常更新。 源代码公布后，如果有什么安全漏洞，整个系统就暴露在cracker面

14、前。只有源代码作者根据用户的建议不断修复Bug和增加功能，才是可信赖的系统。寻找合适的代码推荐网站 和 、 。 是网上最大的开放源代码聚合地。有大量的源代码，分类组织，便于查找。 内事不明问百度，外事不明问谷歌，这2个搜索引擎，基本上你可以找到任何东西，如果你使用了正确的关键字。记录每个修改使用文本文件记录下修改，以便快速恢复 因为开始我们只是试用一个系统，或者只是试着加入一些功能，如果加入功能失败，你又不知道加入了那些东西，这时你可以全部删除你刚才的修改，把原始文件重新解压，根据文本文件的记录恢复到某个版本。记录下打算增加或者修改的事情，记为todo，完成后放入done区。记录每个修改有了这

15、个记录，就可以在下次推出新版本后继续修改。每件事都有记录是一个好的习惯。在源代码里也可加上记录。通读源代码通读代码包括通读目录下的所有文件，特别是Readme，Manual，help，guide，doc，faq这种开头的文档。很多简单的安装出错其实在手册里面都已经告诉你了。修改别人的程序时一定要通读代码，这样才可以保证修改了不加入新的Bug，并且可以充分利用原先的代码。有时为了增加一个新功能，你可以写了一个下午的代码，过几天后发现源代码里面其实有这个功能函数，只需调用某个函数即可。这就是没有通读源代码的结果。通读源代码用文本文件记录下代码的函数功能，一些值得注意的地方。一定必须确保你知道这个软

16、件在干什么，管理员有几个入口，有几个内置帐号需要关闭等等。修改最少定位修改位置，可以使用Editplus的目录全文检索功能。根据用户界面的文字做关键字。Web的用户界面文字可能不准确，可以查看web源代码或者缩小文字单位。如果一个功能有多个修改方法，使用修改最少的那种。虽然这种可能破坏了代码的架构。耦合度最低增加进去的代码应该尽量跟原程序比较分离。总的原则是：源代码就像刺猬，能不碰就不碰。把增加的代码包装成一个过程或者函数，在正确的地方调用一下即可。这样是为了代码的美观。代码如果写得很乱，程序便不易被阅读与修改，所以，在编写代码时要注意以下几点：(1)注释：写注释虽然要占用一定的时间，但在阅读和修改代码时却会节省很多的时间。所以，建议大家在定义一个函数时，在函数的第一行写出函数的作用，再用一行解释函数的参数，并在每个变量的定义语句后注释出其作用。 (2)变量和函数的命名：每个程序都会使用很多的变量和函数，如果随意命名变量与函数，每次使用时还得在变量或函数的定义语句处查出它的数据类型及名称，而且随意命名还会造成变量与函数重复定义。建议大家使用匈牙利命名法，方法是：每个变量或函数的开头都以其数据类型的缩写命名，然后再加上代表这个变量或函数的作用的英文单词简写共同组成变量或函数的名称。