1、ACM程序設計程序設計n杭州電子科技大學 劉春英n 2022-4-62每周一星（每周一星（11）：）：杭電一名2022-4-63第十二講第十二講特殊的數特殊的數（Special Number）2022-4-64Fibonacci 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,. L

2、eonardo Fibonacci 1175-1250 2022-4-65Key Words:Key Words:1225; 1225; Pisa;Pisa;Fibonacci & Fibonacci & Frederick II;Frederick II;Math Math Competition.Competition.Where this came Where this came from? from? 2022-4-66JanuaryJanuary2022-4-67February2022-4-68MarchMarch2022-4-69AprilApril2022-4-610MayMa

3、y、JuneJune?2022-4-611The number series isThe number series is1 1、1 1、2 2、3 3、55This is fibonacci numberThis is fibonacci number！Some other pictures2022-4-6122022-4-6132022-4-6142022-4-6152022-4-616Fibonacci & Golden SectionFibonacci & Golden Section2022-4-617Fibonacci & plants2022-4-618Fibonacci & p

4、lants2022-4-619Fibonacci & plants2022-4-620Fibonacci & plants2022-4-621sunflowers （向日葵）2022-4-6222022-4-6232022-4-6242022-4-625Question:Question:編程實現這類遞編程實現這類遞歸問題時應該注歸問題時應該注意什么問題？意什么問題？空間空間 換換 時間！時間！2022-4-626Catalan Catalan numbernumber2022-4-627HDOJ_1134: Game of HDOJ_1134: Game of Connections Con

5、nections 634251782022-4-628Catalan numbers (1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, .)Catalan NumberCatalan Number(18141894 Belgium)(18141894 Belgium)2022-4-629CatalanCatalan數數有有哪哪些些應應用用? ?2022-4-6301. 1. 多邊形的三角剖分數目多邊形的三角剖分數目 4 sides, 2 ways2022-4-6315

6、sides, 5 ways2022-4-6326 sides, 14 ways2022-4-6337 sides, 42 ways:2022-4-6342. 2. 加括號的方式數目加括號的方式數目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)2022-4-635 (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

7、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) 2022-4-6363.the number of rooted, trivalent 3.the number of rooted, trivalent trees with n+1 nodes trees with n+1 nodes 3 nodes:2022-4-6375 nodes: 4 nodes:2022-4-6384. the number of p

8、aths of length 2n through an n-by-n grid that do not rise above the main diagonal 2 x 2 grid:2022-4-6393 x 3 grid: 4 x 4 grid: 2022-4-6405. 不同形態(tài)二叉樹的數目 There are 5 binary trees with 3 nodes.There are 5 binary trees with 3 nodes.2022-4-6416. 其它應用（1 1）The number of ways 2n people, The number of ways 2n

9、 people, seated round a table, can shake seated round a table, can shake hands in n pairs, without their arms hands in n pairs, without their arms crossing. crossing. （2 2）The self-convolving sequence, The self-convolving sequence, c0=1, cn+1 = c0cn + c1cn-1 c0=1, cn+1 = c0cn + c1cn-1 + . + cnc0 + .

10、 + cnc0 2022-4-642(3) The recurring sequence c0=1, (n+2)cn+1 = (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.2022-4-643HDOJ_1133 Buy the Ticket HDOJ_1133 Buy the Ticket 2022-4-644算法分析：算法分析：n首先假設人無區(qū)別n令f(m,n)表示有m個人手持￥50的鈔票，n個人手持￥100的鈔票時共有的方案總數。則可以分以下情況討論這個問題：n（1）當n=0時n N=0意味著排隊購票的所有人手中拿的都是 ￥50的鈔票，那么這m個人排隊方案總數為1。n（2）當m=n0m=n0）可以推出