07递归

第7章递归recursion（华东）主要内容汉诺塔阶乘斐波那契数列黄金分割和优选法杨辉三角形分形几何（华东）汉诺塔法国数学家爱德华·卢卡斯讲述了一个故事：在古印度的某寺院有块黄铜板，上面固定了三根柱子，其中一根柱子上串有64个金盘子，盘子由下到上依次变小。僧人们根据预言，按规则将盘子从一根柱子移到另一根柱子：（1）每次只能移动一个盘子；（2）大盘不能叠在小盘上面。预言说，当这些盘子全部移完，世界就会灭亡。这就是梵天寺之塔问题(TowerofBrahmapuzzle）（华东）汉诺塔二十世纪福克斯公司拍摄的《猩球崛起》，由罗柏·韦斯导演，于2011年8月5日在北美上映，上译配音版于2011年10月28日在中国大陆上映。片中使用汉诺塔测试猩猩的智力。（华东）汉诺塔2层汉诺塔动手试一试：3层汉诺塔4层汉诺塔……n层汉诺塔（华东）汉诺塔2层汉诺塔要移动3次3层汉诺塔要移动7次……6层汉诺塔要移动63次……因此，n（n0)层汉诺塔的移动次数为2n-1证明（略）（华东）汉诺塔汉诺塔的移动规则①首先移动n层汉诺塔的上n-1层（整体）②移动最下面的第n层到目标位置③再将第一步移走的n-1层移到目标位置可见，汉诺塔为递归问题，即将n层汉诺塔转化为n-1层可以理解，只有1层的汉诺塔只需移动一次，而0层汉诺塔，无需移动（华东）汉诺塔汉诺塔的移动次数ℎ𝑛=01ℎ𝑛−1+1+ℎ(𝑛−1)𝑛=0时𝑛=1时𝑛1时问：ℎ𝑛=2𝑛−1吗?（华东）汉诺塔voidhanoi(intn,charx,chary,charz){if(n0){hanoi(n-1,x,z,y);//x-zprintf(%c-%c,x,y);//x-yhanoi(n-1,z,y,x);//z-y}}intmain(){intn;scanf(%d,&n);hanoi(n,'A','B','C');printf(\nEnd\n);}（华东）汉诺塔64层的汉诺塔的移动次数为264-1，若僧人搬动盘子的速度为1次/秒，那么搬动64层汉诺塔约需5845亿年，人类也许真的灭亡了。舍罕王打算奖赏国际象棋的发明人──宰相西萨·班·达依尔。国王问他想要什么，他对国王说：达依尔要的是填满棋盘上的格子的小麦（华东）阶乘定义1：n(n0)的阶乘为1到n所有自然数的连乘积，即𝑛!=1×2×3×⋯×𝑛=𝑖𝑛𝑖=1定义2：n(n0)的阶乘为𝑛!=1𝑛=0𝑛×𝑛−1!𝑛0定义2采用了“递归定义”（华东）阶乘问题1：请写出高斯求和问题的递归公式解：sum(n)=n+sum(n-1)等差、等比数列都可以用递归实现问题2：试编程用递归实现字符串的反转解：voidreverse(char*s,intleft,intright){if(rightleft){charc=s[left];s[left]=s[right];s[right]=c;reverse(*s,left+1,right-1);}}（华东）递归递归是一种程序调用自身的编程技巧。在程序设计中，递归广泛应用于将复杂问题转化为与之相似的简化问题。递归有3种应用形式：数据是按递归定义的，如Fibonacci数列问题解法按递归算法实现，如汉诺塔数据的结构形式是按递归定义的，如链表递归策略可以简化程序设计，但相对常用的算法如普通循环等，递归算法的执行效率不高。由于递归调用使用了系统中的栈，存在栈溢出。因此，应该尽量避免使用递归，而转化为非递归。（华东）斐波那契数列意大利数学家LeonardoFibonacci（1170~1240）是第一个研究了印度和阿拉伯数学理论的欧洲人，120年，他撰写出版了“LiberAbaci”，系统介绍记账、利息、汇率等计算问题。有人把该书翻译为《珠算原理》，可能觉得其中的大多数问题都来源于中国的珠算。（华东）斐波那契数列例：砖头的大小为1x2，要把砖头摆成1排，要求高度为2，长度为n（n≥1），请找出可能的排法解：这是一个斐波那契数列，其摆法如下n=1，需1块砖n=2，需2块砖n=3，需3块砖n=4，需4块砖n块砖的摆法等于n-1、n-2块砖的摆法之和（华东）斐波那契数列Leonardo在书中提出了一个在理想假设条件下兔子成长率的问题，求解此问题可形成一个数列，也就是斐波那契数列数学上，斐波那契数列定义为：𝐹𝑛=0𝑛=01𝑛=1𝐹𝑛−1+𝐹(𝑛−2)𝑛≥2且𝑛∈𝑁∗在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1960年代起出版了《斐波纳契数列》季刊，专门刊载这方面的研究成果。（华东）斐波那契数列斐波那契数的计算公式𝐹(𝑛)=151+52𝑛−1−52𝑛当n较大时，F(n-1)/F(n)≈0.618或者F(n)/F(n-1)≈1.618黄金分割黄金分割是指将整体一分为二，较大部分与整体部分的比值等于较小部分与较大部分的比值这个比值约为0.618，被称为黄金分割数（华东）黄金分割线段AB的长度为1若C为AB的黄金分割点，则AC的长度x满足：ABCx1-x𝑥1=1−𝑥𝑥𝑥=5−12≈0.618（华东）黄金分割试用尺规作图法标出线段AB的黄金分割点画法：①找到AB的中点C②以B为圆心、BC为半径画圆交AB的垂线于D点③以D为圆心、DB为半径画圆交AB于E点④以A为圆心、AE为半径画圆交AB于F点F点就是AB的黄金分割点因为，AF=AE=AD-DE=5BD-BD=5−12𝐴𝐵（华东）黄金矩形黄金矩形的长宽比为1.618例如，人脸轮廓、照片构图、电脑显示器（16:9、16:10）等黄金矩形（华东）黄金分割黄金分割具有严格的比例性、艺术性、和谐性，蕴藏着丰富的美学价值（华东）黄金分割（华东）优选法常说的优选法是指基于黄金分割法的单一因素优化方法优选法是美国数学家基弗于1953年提出的，1970年代传入我国，著名数学家华罗庚穷20年时间大力推广，为我国农业生产做出了巨大贡献x0x1x0x2（1）取黄金分割点x0和其对称点x1（2）去除点x1后，再取对称点x2（华东）优选法某公司要配制一种新型饮料，需要试验研究加入某种化学成分K的量。根据已往经验，估计每100kg饮料大约可加入K的量在1000～2000g之间。如果以每10g作一次试验，就要作100次试验，显然不划算用一条有刻度的纸带表示1000～2000g，在纸带的1618处划一条线，取1618g成分K加入100kg饮料中做一次试验。然后把纸带对折，在前一划线处（即1382）再划一线，再取1382g成分K加入100kg饮料中，再做一次试验。比较两次试验的效果。如果认为1382g的浓度较低，则在1382处把纸带的左边一段剪掉。反之，就在1618处剪掉右边的一段。把剩下的纸带再对折，再划线，再做试验，如此反复，直到满意为止。（华东）正交试验法正交试验法是在多因素优化试验中，利用数理统计学与正交性原理，从大量的试验点中挑选有代表性和典型性的试验点，应用“正交表”科学合理地安排试验，从而用尽量少的试验得到最优的试验结果的一种试验设计方法正交表L4(23)行数4表示4次试验列数3表示有3个因素水平2表示每个因素只有2个数字水平列号123试验号1111212232124221（华东）杨辉三角形杨辉，字谦光，汉族，钱塘人，生卒不详，著名数学家、教育家，与秦九韶、李治、朱世杰并称宋元数学四大家。杨辉的著名数学书有《详解九章算法》等共五种二十一卷，还有《算法通变本末》等教材。（华东）杨辉三角形杨辉三角形，又称贾宪三角形，帕斯卡三角形。北宋贾宪约1050年首先使用“贾宪三角”进行高次开方运算。南宋杨辉于1261年在《详解九章算法》中称之为“开方作法本源”图。16世纪，意大利塔塔利亚用“塔塔利亚三角形”求解一元三次方程。1623年，法国数学家帕斯卡13岁时发现了“帕斯卡三角”。（华东）杨辉三角形杨辉三角形中，某个节点的值是从顶点到达该结点的路径条数（华东）杨辉三角形问：杨辉三角形中第n（n≥1）层的第k个数（1≤k≤n）是什么？解：把连接两个相邻节点的连线称为边，可分为两种边：向左的L边和向右的R边。不难看出，从顶点到达第n层上的点需要经过n-1条边，如果L边有CL条，R边有CR条，则有n-1=CL+CR。若k=1，则CR=0，路径数为𝐶𝑛−10，所以顶点值为𝐶𝑛−10；若k=2，则CR=1，路径数为𝐶𝑛−11，所以顶点值为𝐶𝑛−11；若k=3，则CR=2，路径数为𝐶𝑛−12，所以顶点值为𝐶𝑛−12；以此类推，可得第n层的第k个数的值为𝐶𝑛−1𝑘−1请验证其正确性？特别的，当kn/2时，公式成立吗？为什么？（华东）杨辉三角形杨辉三角形中，如果把第n+1层的第k+1个数为𝐶𝑛𝑘，则其左上的数为𝐶𝑛−1𝑘−1，右上的数为𝐶𝑛−1𝑘，根据杨辉三角形的定义有𝐶𝑛𝑘=𝐶𝑛−1𝑘−1+𝐶𝑛−1𝑘（n1，1≤k≤n）杨辉三角形可定义为：𝐶𝑛𝑘=1𝑛=1,𝑘=1𝐶𝑛−1𝑘−1+𝐶𝑛−1𝑘𝑛1,1≤𝑘≤𝑛（华东）杨辉三角形定理：从n个数中选k个数的组合数等于从n-1个数中选k-1个数的组合数和从n-1个数中选k个数的组合数之和证明：（略）例如，从5个整数中选3个数的组合数为10，等于从4个数中选2个数的组合数6加上从4个数中选3个数的组合数4例如，如果这5个数是1、2、3、4、5，从中选3个数的组合数等于“不包括整数1，从其余4个数中选3个数的组合数”加上“包括整数1，从其余4个数中选2个数的组合数”（华东）杨辉三角形如果不考虑杨辉三角形的高度，那么：任何正整数都会出现只有1无限次出现，其他整数只出现有限次2只出现1次，而且只出现1次的数只有2出现2次的数很多，如3、4、5等出现3次的数也很多，如6、20、70等出现4次的数也很多，如10、15、21等120出现了6次第一个出现8次的数是3003出现5次的数呢？还没发现……（华东）杨辉三角形杨辉三角形中，取第n行的第1个数、沿30°方向向右上方画直线，将线上的数据求和，可得斐波那契数列的第n-1个数（华东）杨辉三角形杨辉三角形中，取第2n+1行的第1个数、第2n+2行的第3个数、第2n+3行的第5个数、…，将这些数求和将得到斐波那契数列的第4n+1个数（华东）分形几何分形（Fractal）通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状”，即具有自相似的性质。分形一词由法国数学家B.B.Mandelbrot于1975年创造，现在医学、土力学、地震学和技术分析中都有应用。（华东）分形几何17世纪，数学家莱布尼茨思考过递归的自相似，但他误认为只有直线会自相似1872年，卡尔·魏尔施特拉斯才给出一个具有处处连续但处处不可微的函数例子1904年，海里格·冯·科赫给出了一个类似的函数，并绘制了科赫雪花（华东）分形几何1915年瓦茨瓦夫·谢尔宾斯基造出了谢尔宾斯基三角形；隔年，又造出了谢尔宾斯基地毯。1960年代，Mandelbrot开始研究自相似，发表了论文《英国的海岸线有多长？统计自相似和分数维度》。1975年，Mandelbrot提出了“分形”一词。11112113311464115101051161520156117213535217118285670562881193684126126843691110451202102522101204510111155165330462462330165551111126622049579292479249522066121113782867151287171