- 1、本文档共36页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
* Central South University * Example: Fibonacci Number 问题:一年以后,一共有多少对兔子? 1. In the beginning: (1 pair) 2. End of month 1: (1 pair) Rabbits are ready to mate. 3. End of month 2: (2 pairs) A new pair of rabbits are born. 4. End of month 3: (3 pairs) A new pair and two old pairs. 5. End of month 4: (5 pairs) ... 6. End of month 5: (8 pairs) ... …….. 7.After 12 months, there will be 233 pairs rabbits! * Central South University * Recurrence Relation of Fibonacci Number fib(n) (递推关系) {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …} Tips:自然界中的Fibonacci Number 现象:海浪,钟声,...癌细胞? * Central South University * Algorithm: Fibonacci Problem: What is fib(200)? What about fib(n), where n is any positive integer? Algorithm1 fib (n) if n = 0 thenreturn 0 if n = 1thenreturn 1 return (fib(n?1) + fib(n?2)) Questions that we should ask ourselves: 1. What is the running time of the algorithm? 2. Can we do better? * Central South University * Answer of Questions How fast is the algorithm? If we let the run time of fib(n) be T(n), then we can formulate T(n) = T(n?1) + T(n?2) + 3 ? 1.6n T(200) ? 2139 Tips: 用世界是最快的计算机BlueGene/L: 每秒能运行248 条指令, 需运算 291 秒,(291 seconds = 7.85 × 1019 years ) * Central South University * Improvement Can we do better? Yes, because many computations in the previous algorithm are repeated. Algorithm 2: fib(n) // Initially we create an array A[0: n]A[0] ← 0, A[1] ← 1 For i = 2 to n do A[i] = A[i ? 1] + A[i ? 2] return (A[n]) * Central South University * Part2: Algorithm Design Techniques/Strategies Brute force Divide and conquer Decrease and conquer Greedy approach Dynamic programming Backtracking Branch and bound * * * * * ??=编程 这门课十分有趣,同时也比较难,大家必须努力学习才能学好它! * * * * Gcd(70, 25) = gcd(25, 20) = gcd(20, 5) = gcd (5, 0) = 5 Gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12 * * prime factors:素因数 * Pseudo-code (伪代码),类高级语言,由于其非常简练,便于表达算法的思想, indentation(缩进) * * 性能是1,其它的都是后面的0 * The first part of this course is focused on analysis, the second part of t
您可能关注的文档
最近下载
- 职业暴露处置流程图.docx VIP
- SY∕T 5163-2018 沉积岩中黏土矿物和常见非黏土矿物 X 射线衍射分析方法.pdf
- 2024年衡阳市蒸湘区六上数学期末经典试题含解析.doc VIP
- 人教版四年级数学上册《应用题》专项练习题(含答案).docx VIP
- EIA-364-13C_插拔力测试标准.pdf VIP
- 《GB/T 45298-2025土壤制图 1∶25 000~1∶500 000土壤质地、酸碱度、盐渍化图的图式、用色及图例规范》.pdf
- NYT 2245-2012 县级农产品质量安全监督检测机构建设标准.docx VIP
- 铁路营业线换枕机更换轨枕施工工艺.pptx VIP
- 园林绿化养护工作计划方案.docx VIP
- 《光伏电站晶硅组件隐裂检测及判定方法》-征求意见稿.pdf VIP
文档评论(0)