《迭代分治穷举回等溯算法概念的引入》由会员分享，可在线阅读，更多相关《迭代分治穷举回等溯算法概念的引入（42页珍藏版）》请在金锄头文库上搜索。
1、递归与迭代的区别Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.关于递归的回顾一般定义程序调用自身的编程思想称为递归（ recursion）。 一个过程或函数在其定义或说明中有直接或间接调
2、用自 身的一种方法，它通常把一个大型复杂的问题层层转化 为一个与原问题相似的规模较小的问题来求解，递归策 略只需少量的程序就可描述出解题过程所需要的多次重 复计算，大大地减少了程序的代码量。递归的能力在于 用有限的语句来定义对象的无限集合。一般来说，递归 需要有边界条件、递归前进段和递归返回段。当边界条 件不满足时，递归前进；当边界条件满足时，递归返回 。 注意：(1) 递归就是在过程或函数里调用自身； (2) 在使用递归策略时，必须有一个明确的递归结束条 件，称为递归出口。Evaluation only.Evaluation only. Created with Aspose.Slides
3、for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.什么是迭代迭代法是一种常用的算法设计方法,迭代是 一个不断用新值取代变量的旧值,或由旧值 递推出变量的新值的过程.Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5
4、Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.当一个问题的求解过程能够由一个初值使用一个 迭代表达式进行反复迭代的时候,便可以用效率极 高的重复程序描述迭代也是用循环结构实现的.只不过重复的操作是不断的从一个变量的旧值出 发计算它的新值.其基本格式如下;迭代变量赋予初值;循环语句计算迭代式;新值取代旧值Evaluation onl
5、y.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.例子:斐波那契序列;以兔子繁殖为例用月份n作为参数,表示计算第几个月后兔子 的总数,i循环变量,迭代条件为:3n) 输出当前布局；Else for(j=1;j0,1=i
6、=n.这个问题称为背包问（Knapsack problem）。 Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.其他动态规划 随机化思想 概率分析 摊销分析 竞争分析还有很多愿意深入了解的
7、同 学可以看一些算法方面的书籍。但是需要注意，常用的算法了解即可，先把编程语言和高级编程等基 础学好，算法暂时不可深入钻研。Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.有穷状态机（有限
8、状态机）有穷状态机很简单，在生活中可以找出很多这样的 例子。但是教科书里讲得太复杂了，一会儿证明确 定性有穷状态机和非确定性有穷状态机的等价性， 一会儿 证明正则表达式的这些理论的证明于编程没有太大用处，不过状态机 本身却是文本处理利器，由于程序员在很多场合下 都是在与文本数据 打交道，所以状态机是程序员必 备的工具之一。教科书上是这样定义有穷自动机的（略去可以百度 ）这个形式定义精确的描述了有穷状态机的含义。 但是大部分人 第一次看到它时，反复的读上几遍， 仍然不知道它在说什么。幸好通过一些实例，我们 可以很容易明白有穷状态机的原理。Evaluation only.Evaluation on
9、ly. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.自动门刚安装好的时候，我们可以认为它是关上的，所以关闭状态是自动门 的初始状态。在理想情况下，自动门会一直运行，所以它没有接受状态，接受状态集F是空 集。Evaluation only.Evalua
10、tion only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.例子密码锁：以四位密码校验作为状态机的例子，连续输入 2479就可以通过密码测试Evaluation only.Evaluation only. Created with Aspose
11、.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.统计一篇英文文章里的单词个数。有多种方法可以解这道题，这里我们选择用有穷状态机来解，做法如下：先把这篇英文文章读入到一个缓冲区里，让一个指针从缓冲区的头部一直移到缓冲区的尾部，指针 会处于两种状态：“单词内”或“单词外”，加上后面提到的初始状态
12、和接受状态，就是有穷状态机的状 态集。缓冲区中的字符集合就是有穷状态机的字母表。如果当前状态为“单词内”，移到指针时，指针指向的字符是非单词字符(如标点和空格)，那状态会从 “单词内”转换到“单词外”。如果当前状态为“单 词外”， 移到指针时，指针指向的字符是单词字符(如 字母)，那状态会从“单词外”转换到“单词内”。这些转换规则就是状态转换函数。指针指向缓冲区的头部时是初始状态。指针指向缓冲区的尾部时是接受状态。每次当状态从“单词内”转换到“单词外”时，单词计数增加一。这个有穷状态机的图形表示如下：Evaluation only.Evaluation only. Created with A
13、spose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.Hash table 简介哈希查找 基本思想：在记录的存储地址和它的关键字 之间建立一个确定的对应关系；这样，不经 过比较，一次存取就能得到所查元素的查找 方法Evaluation only.Evaluation only. Crea
14、ted with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被 更快地定位。 实际工作中需视不同的情况采用不同的哈希函数，通常考虑的因素有： 计算哈希函数所需时间 关键字的长度 哈希表的大小 关键字的
15、分布情况 记录的查找频率 1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。 即H(key)=key或H(key) = akey + b，其中a和b为常数（这种散列函数叫做自身函数）。若 其中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。 2. 数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前 几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位 表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率 会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造
16、冲突几率 较低的散列地址。 3. 平方取中法：取关键字平方后的中间几位作为散列地址。 4. 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分 的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移 位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分 割界来回折叠，然后对齐相加。 5. 随机数法：选择一随机函数，取关键字的随机值作 为散列地址，通常用于关键字长度不同的场合。 6. 除留余数法：取关键字被某个不大 于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p,p=m。不仅 可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般 取素数或m，若p选的不好，容易产生同义词。Evaluation only.Evaluation only. Created with Asp
