计算思维的结构全套PPT课件.ppt

递归的定义功能定义集合例5.24现有文法G的生成式如下： S→A； S是文法G的开始符号 A→01； 递归基础 A→0A1； 递归步骤该文法的生成式采用了递归方法。其实际上定义了这样一个集合：L(G)={0n1n|n≥1}，表示由相同个数的“0”和“1”组成的字符串的集合。阿克曼函数由希尔伯特的学生、德国著名数学家威尔海姆·阿克曼于1928年发现的。阿克曼函数：解阿克曼函数的递归算法:Beginifm=0thenn+1elseifn=0thenA(m-1,1)elseA(m-1,A(m,n-1))End计算A(1,2)例：计算A(1,2)解:A(1,2)=A(0,A(1,1))=A(0,A(0,A(1,0))=A(0,A(0,A(0,1))=A(0,A(0,2))=A(0,3)=4迭代“迭”是屡次和反复的意思，“代”是替换的意思，合起来，“迭代”就是反复替换的意思。在程序设计中，为了处理重复性计算的问题，最常用的方法就是迭代方法，主要是循环迭代。迭代与递归的关系迭代程序都可以转换为与它等价的递归程序，反之则不然。就效率而言，递归程序的实现要比迭代程序的实现耗费更多的时间和空间。因此，在具体实现时，又希望尽可能将递归程序转化为等价的迭代程序。斐波那契数的求解算法可以使用迭代方法或递归方法来解决。随机数和蒙特卡洛方法前面介绍了递归和迭代，它们解决的是数列的有序问题；而在实际生活中，很多数列是无序的，这就需要引入“概率”这个数学概念。日常生活中无处不在的“概率”相关的问题：丢掷骰子抽奖商品优惠券：商家在每件商品中附有一张优惠券，每张券上只印一个字，商家要求消费者筹齐所有字即可享受优惠，通常这些字可拼成一句话或者一句广告语。……在计算机科学中，与“概率”相关的最基础的两个概念:随机数、蒙特卡洛（MonteCarlo）方法。什么是“随机数”？随机数是专门的随机试验的结果。特性：所生成的后面的那个数与前面的那个数毫无关系。无法预测没有规律不可重现随机数表：是统计工作者用计算机生成的随机数组成，并保证表中每个位置上出现哪一个数字是随机数表等概率的。随机数表随机数有什么用？在抽样统计时需要使用随机数；利用随机数表抽取样本保证了各个个体被抽取的概率相等。比如：考察某公司的牛奶产品质量，想从800袋牛奶中抽取60袋？可以在随机数表中选取一数，然后用向上、下、左、右不同的读法组成60个数，并按牛奶的标号进行检测。企业要调查消费者对某产品的需求量，如何从很多消费者中抽选一定数量的样本进行调查？进行科学实验时需要用到随机数；比如：如何将实验动物分配到不同的试验组？随机数有什么用？(续)在信息安全中经常需要使用随机数。比如：订票系统登录时的验证码，抵抗拒绝服务攻击(DoS)。银行的ID和密码非常脆弱；如果有随机数表，可以为每个客户指定各不相同的数字列表，申请时将该随机数表分配给客户，而不是按照一定的规律给出，这就安全很多。密码技术中的算法和协议都需要敌手不知道、也无法预测的数据，即随机数；其随机性如何，对信息系统的安全起着非常重要的作用。进行蒙特卡洛模拟法计算时必须使用如何生成随机数？真随机数：真正的随机数是使用物理现象生成的，比如掷钱币、骰子、转轮、使用电子元件的噪音、大气噪音、放射衰变、宇宙射线的触发时间、核裂变等等。这样的随机数发生器叫做物理性随机数发生器，它们的缺点是技术要求比较高。如何生成随机数？伪随机数：由计算机按递推公式大量产生。所得到的数列是“似乎”随机的数，但实际上是通过一个固定的、可以重复的计算方法生成的。虽然是可以计算出来的，但是它们具有类似于随机数的统计特征。线性同余法线性同余法：例：选m=9,a=7,c=4和x0=3，产生的伪随机数序列为？用线性同余法生成伪随机数线性同余法：例：选m=9,a=7,c=4和x0=3，产生的伪随机数序列为？这样的发生器叫做伪随机数发生器。随机数种子：(如：m=9,a=7,c=4和x0=3)局限：只要计算方法一定，随机数种子一定，那么产生的随机数就不会变！伪随机数序列看上去是随机的，但是反复执行程序会发现每次程序所产生的序列是重复的。用C语言产生伪随机数 #includestdio.h#includestdlib.hmain() {