lecture特殊的数.ppt

2020 1 12 1 ACM程序设计 计算机学院刘春英 2020 1 12 2 今天 你了吗 AC 2020 1 12 3 每周一星 8 天外来客 2020 1 12 4 第九讲 特殊的数 SpecialNumber 2020 1 12 5 主要内容 FibonacciNumberLucasnumberCatalanNumberApplicationtoSpecialNumber 2020 1 12 6 FibonacciNumber Fibonacciisperhapsbestknownforasimpleseriesofnumbers introducedinLiberabaciandlaternamedtheFibonaccinumbersinhishonour Theseriesbeginswith0and1 Afterthat usethesimplerule Addthelasttwonumberstogetthenext 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 2020 1 12 7 LeonardoFibonacci1175 1250 2020 1 12 8 Youmightaskwherethiscamefrom 2020 1 12 9 InFibonacci sday mathematicalcompetitionsandchallengeswerecommon In1225FibonaccitookpartinatournamentatPisaorderedbytheemperorhimself FrederickII Itwasinjustthistypeofcompetitionthatthefollowingproblemarose 2020 1 12 10 Beginningwithasinglepairofrabbits ifeverymontheachproductivepairbearsanewpair whichbecomesproductivewhentheyare1monthold howmanyrabbitswilltherebeafternmonths 2020 1 12 11 January 2020 1 12 12 February 2020 1 12 13 March 2020 1 12 14 April 2020 1 12 15 May June 2020 1 12 16 Thenumberseriesis 1 1 2 3 5 Thisiffibonacci 2020 1 12 17 Someotherpictures 2020 1 12 18 2020 1 12 19 2020 1 12 20 2020 1 12 21 2020 1 12 22 Fibonaccinumber GoldenSection Aspecialvalue closelyrelatedtotheFibonacciseries iscalledthegoldensection ThisvalueisobtainedbytakingtheratioofsuccessivetermsintheFibonacciseries 2020 1 12 23 FibonacciNumbersinNature 2020 1 12 24 whitecallalily 白色马蹄莲 2020 1 12 25 Euphorbia 一种非洲植物 不常见 2020 1 12 26 trillium 延龄草 2020 1 12 27 Columbine 耧斗菜 2020 1 12 28 Bloodroot 一种罂粟科植物 2020 1 12 29 black eyedsusan 2020 1 12 30 shastadaisy 大滨菊 with21petals 2020 1 12 31 Ordinaryfielddaisies 雏菊 have34petals 2020 1 12 32 TheassociationofFibonaccinumbersandplantsisnotrestrictedtonumbersofpetals 2020 1 12 33 Ifwedrawhorizontallinesthroughtheaxils wecandetectobviousstagesofdevelopmentintheplant 2020 1 12 34 ThenumberofbranchesatanystageofdevelopmentisaFibonaccinumber 2020 1 12 35 Furthermore thenumberofleavesinanystagewillalsobeaFibonaccinumber 2020 1 12 36 sunflowers 向日葵 2020 1 12 37 2020 1 12 38 2020 1 12 39 2020 1 12 40 Fibonacciingeometricalstyle 2020 1 12 41 LucasNumber LucasNumbersarethecompanionstotheFibonaccinumbersandsatisfythesamerecurrence L n L n 1 L n 2 WhereL 1 1 L 2 3 Thefirstfeware1 3 4 7 11 18 29 47 76 123 2020 1 12 42 EdouardLucas 1842 1891 2020 1 12 43 Question 编程实现这类递归问题时应该注意什么问题 2020 1 12 44 空间换时间 2020 1 12 45 Catalannumber 2020 1 12 46 先看一道题目 HDOJ 1134 GameofConnections 2020 1 12 47 示意图 2020 1 12 48 Easyornot 2020 1 12 49 TheCatalannumbers 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 namedafterEug neCharlesCatalan ariseinanumberofproblemsincombinatorics Theycanbecomputedusingthisformula CatalanNumber 2020 1 12 50 Eug neCharlesCatalan 1814 1894Belgium 2020 1 12 51 WhatcantheCatalannumbersdescribe 2020 1 12 52 1 Thenumberofwaysapolygonwithn 2sidescanbecutintontriangles 4sides 2ways 2020 1 12 53 5sides 5ways 6sides 14ways 2020 1 12 54 7sides 42ways 2020 1 12 55 2 thenumberofwaysinwhichparenthesescanbeplacedinasequenceofnumberstobemultiplied twoatatime 2020 1 12 56 5numbers 1 2 3 45 1 2 34 5 1 23 45 1 2 34 5 1 23 4 5 12 3 45 12 34 5 1 23 45 1 2 34 5 1 23 4 5 12 3 45 12 34 5 1 23 4 5 12 3 4 5 2020 1 12 57 3 thenumberofrooted trivalenttreeswithn 1nodes 3nodes 2020 1 12 58 5nodes 4nodes 2020 1 12 59 4 thenumberofpathsoflength2nthroughann by ngridthatdonotriseabovethemaindiagonal 2x2grid 2020 1 12 60 3x3grid 4x4grid 2020 1 12 61 5 Thenumberofbinarytreeswithnnodes Thereare5binarytreeswith3nodes 2020 1 12 62 6 Someotherapplications 1 Thenumberofways2npeople seatedroundatable canshakehandsinnpairs withouttheirarmscrossing 2 Theself convolvingsequence c 0 1 c n 1 c 0 c n c 1 c n 1 c n c 0 2020 1 12 63 3 Therecurringsequencec 0 1 n 2 c n 1 4n 2 c n n 0 4 AnotherdisguiseisthenumberofwaysnvotescancomeinforeachoftwocandidatesAandBinanelection withAneverbehindB 2020 1 12 64 思考 1 2020 1 12 65 算法分析 令f m n 表示有m个人手持 50的钞票 n个人手持 100的钞票时共有的方案总数 则可以分以下情况讨论这个问题 1 当n 0时N 0意味着排队购票的所有人手中拿的都是 50的钞票 那么这m个人排队方案总数为1 2 当m n时显然 f m n 0 2020 1 12 66 3 其他情况 考虑 m n 个人排队购票的情景 第 m n 人站在第 m n 1 个人的后面 则第 m n 个人的排队方式可以由下列两种情况获得 1 第 m n 个人手持 100的钞票 则在他之前的 m n 1 个人中有m个人手持 50的钞票 有 n 1 个人手持 100的钞票 此种情况共有f m n 1 2 第 m n 个人手持 50的钞票 则在他之前的 m n 1 个人中有m 1个人手持 50的钞票 有n个人手持 100的钞票 此种情况共有f m 1 n 2020 1 12 67 根据加法原理得到f m n f m 1 n f m n 1 于是得到f m n 的计算公式 2020 1 12 68 计算示意图 2020 1 12 69 计算示意图 2020 1 12 70 计算示意图 2020 1 12 71 可以推出直接的公式 C m n n