《（lecture_05）特殊的数 ACM课件》由会员分享，可在线阅读，更多相关《（lecture_05）特殊的数 ACM课件（46页珍藏版）》请在金锄头文库上搜索。
1、第十讲特殊的数 （Special Number）Date1Fibonacci NumbernThe series begins with 0 and 1. After that, use the simple rule: Add the last two numbers to get the next. n0 , 1 , 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,. Leonardo Fibonacci1175-1250 Date2古代谜题：如果一对兔 子每月能生一对小兔 ，而每对小兔在它出 生后的第三个月又能 生一对
2、小兔，假定在 兔子不死亡的情况下 ，由一对小兔开始， 50个月后会有多少对 兔子.Where this came from? Date3JanuaryDate4FebruaryDate5MarchDate6AprilDate7May、June?Date8The number series is1、1、2、3、5This is fibonacci number！Some other picturesDate9Fibonacci & Golden SectionDate10Fibonacci & plantsDate11Fibonacci & plantsDate12Fibonacci & pla
3、ntsDate13Fibonacci & plantsDate14sunflowers （向日葵）Date15Date16Date17Date18Question:编程实现这类递归问题 时应该注意什么问题？空间 换 时间！Date19相关例题n 1.楼梯有n阶台阶,上楼可以一步上1阶, 也可以一步上2阶,编一程序计算共有多 少种不同的走法?n 2.有一对雌雄兔,每两个月就繁殖雌 雄各一对兔子.问n个月后共有多少对兔 子?n 3.有n*2的一个长方形方格,用一个 1*2的骨牌铺满方格。求铺法总数？Date20Catalan numberDate21HDOJ_1134: Game of Conne
4、ctions 63425178Date22Catalan numbers (1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, .) f(n) = f(n-1) + f(n-2)f(1) + f(n-3)f(2) + f(n- 1) Catalan Number(18141894 Belgium)Date23Catalan数有哪些应用?Date241. 多边形的三角剖分数目 4 sides, 2 waysDate255 sides, 5 waysDate266 sides,
5、 14 waysDate277 sides, 42 ways:Date282. 加括号的方式数目3 numbers: (1 (2 3) (1 2) 3)4 numbers: (1 (2 (3 4) (1 (2 3) 4) (1 2) (3 4) (1 (2 3) 4)(1 2) 3) 4)Date29(1 (2 (3 (4 5) (1 (2 (3 4) 5)(1 (2 3) (4 5) (1 (2 (3 4) 5)(1 (2 3) 4) 5) (1 2) (3 (4 5)(1 2) (3 4) 5) (1 (2 3) (4 5)(1 (2 (3 4) 5) (1 (2 3) 4) 5)(1 2
6、) 3) (4 5) (1 2) (3 4) 5)(1 (2 3) 4) 5) (1 2) 3) 4) 5) Date303.the number of rooted, trivalent trees with n+1 nodes 3 nodes:Date315 nodes: 4 nodes:Date324. the number of paths of length 2n through an n-by-n grid that do not rise above the main diagonal 2 x 2 grid:Date333 x 3 grid: 4 x 4 grid: Date34
7、5. 不同形态二叉树的数目 There are 5 binary trees with 3 nodes.Date356. 其它应用（1）The number of ways 2n people, seated round a table, can shake hands in n pairs, without their arms crossing. （2）The self-convolving sequence, c0=1, cn+1 = c0cn + c1cn- 1 + . + cnc0 Date36(3) The recurring sequence c0=1, (n+2)cn+1 =
8、(4n+2)cn, (n=0). (4)Another disguise is the number of ways n votes can come in for each of two candidates A and B in an election, with A never behind B.Date37HDOJ_1133 Buy the Ticket Date38算法分析：n首先假设人无区别n令f(m,n)表示有m个人手持￥50的钞票，n个 人手持￥100的钞票时共有的方案总数。则可 以分以下情况讨论这个问题：n（1）当n=0时N=0意味着排队购票的所有人手中拿的都 是 ￥50的钞票，那么这m个人排队方案总数 为1。n（2）当m=n0）可以推出下面直接的公式： f(m,n)= C(m+n,n)- C(m+n,m+1)Date45相关练习n2018 母牛的故事 n2041 超级级楼梯 n2067 小兔的棋盘盘 n1130 How Many Trees? n1131 Count the Treesn1133 Buy the Ticket n1134 Game of Connections n1023 Train Problem II n1267 下沙的沙子有几粒？Date46
