![计算机问题求解:递归及其数学基础_第1页](http://file4.renrendoc.com/view5/M00/28/0E/wKhkGGZn0zaAVe9YAACtVw6vbqg286.jpg)
![计算机问题求解:递归及其数学基础_第2页](http://file4.renrendoc.com/view5/M00/28/0E/wKhkGGZn0zaAVe9YAACtVw6vbqg2862.jpg)
![计算机问题求解:递归及其数学基础_第3页](http://file4.renrendoc.com/view5/M00/28/0E/wKhkGGZn0zaAVe9YAACtVw6vbqg2863.jpg)
![计算机问题求解:递归及其数学基础_第4页](http://file4.renrendoc.com/view5/M00/28/0E/wKhkGGZn0zaAVe9YAACtVw6vbqg2864.jpg)
![计算机问题求解:递归及其数学基础_第5页](http://file4.renrendoc.com/view5/M00/28/0E/wKhkGGZn0zaAVe9YAACtVw6vbqg2865.jpg)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
计算机问题求解
–
论题2-4
递归及其数学基础问题1:以HanoiTower为例,说说你对“递归过程”、“递归式”的理解。它们与实际的操作过程是什么关系?最简单的解递归的方法–回朔问题2:为什么不应该将递归仅仅看成一种编程的技术?SolutionofTowersofHanoiT(n)=2T(n-1)+12T(n-1)=4T(n-2)+24T(n-2)=8T(n-3)+4…….2n-2T(2)=2n-1T(1)+2n-2T(n)=2n-1递归思维:直线划分平面问题:n
条直线(无限长)最多能将平面分为多少个区域(包括有限与无限区域)?
Linen怎样能使划分的区域尽可能得多?L(0)=1L(n)=L(n-1)+n用回朔的办法解递归L(n)=L(n-1)+n=L(n-2)+(n-1)+n=L(n-3)+(n-2)+(n-1)+n=……=L(0)+1+2+……+(n-2)+(n-1)+nL(n)=n(n+1)/2+1递归思维:Josephus问题Liveordie,it’saproblem!LegendhasitthatJosephuswouldn'thavelivedtobecomefamouswithouthismathematicaltalents.DuringtheJewishRomanwar,hewasamongabandof41JewishrebelstrappedinacavebytheRomans.Preferringsuicidetocapture,therebelsdecidedtoformacircleand,proceedingaroundit,tokilleverythirdremainingpersonuntilnoonewasleft.ButJosephus,alongwithanunindictedco-conspirator,wantednoneofthissuicidenonsense;sohequicklycalculatedwhereheandhisfriendshouldstandintheviciouscircle.Weuseasimplerversion:“everysecond...”试试看:n=10187624510391753917539survivorFor2nPersons(n=1,2,3,...)122n2n-13k+1kk-1132n-12n-35k+3k+1k-1n
personsleftThesolutionis:newnumber(J(n))Andthenewnumber(k)is......2k-1AndWhatabout2n+1Persons(n=1,2,3,...)122n+12n3k+1kk-1352n+12n-17k+3k+1k-1dothesame:n
personsleftThesolutionis:newnumber(J(n))Andforthetime,thenewnumber(k)is......2k+1递归方程:奇偶数分情况列出问题3:你能看出什么规律吗?Eureka!Ifwewritenintheformn=2m+l,(where2misthelargestpowerof2notexceedingnandwhereliswhat'sleft),thesolutiontoourrecurrenceseemstobe:Asanexample:J(100)=J(64+36)=36*2+1=73问题4:你能否想出一种简单易行的计算办法?用二进制表示Supposen’sbinaryexpansionis:then:例如:100
=
(1100100)2
(1001001)2
=
73
问题5:你上小学时学的是自然数的加法,还是“自然数的十进制表示”的加法?问题6:这是Fibonacci序列,你知道它为什么那么出名吗?黄金分割Phidias(460-430BC)or
-bonacci?线性齐次递归式iscalledlinearhomogeneousrelationofdegreek.YesNo线性齐次递归式的特征方程Foralinearhomogeneousrecurrencerelationofdegreekthepolynomialofdegreekiscalleditscharacteristicequation.Thecharacteristicequationoflinearhomogeneousrecurrencerelationofdegree2is:解线性齐次递归式–解代数方程Ifthecharacteristicequationoftherecurrencerelationhastwodistinctrootss1ands2,thenwhereuandvdependontheinitialconditions,istheexplicitformulaforthesequence.Iftheequationhasasingleroots,then,boths1ands2intheformulaabovearereplacedbysProofoftheSolutiontheFibonacciSequencef1=1f2=1fn=fn-1+fn-21,1,2,3,5,8,13,21,34,......
ExplicitformulaforFibonacciSequenceThecharacteristicequationisx2-x-1=0,whichhasroots:Note:(byinitialconditions)whichresults:
问题7:你能说说MasterTheorem的含义与其背后的原理吗?最简单的形式问题8:三种情况的本质差别在哪里?平滑函数Letf(n)beanonnegativeeventuallynon-decreasingfunctiondefinedonthesetofnaturalnumbers,f(n)iscalledsmoothiff(2n)
(f(n)).Note:logn,n,nlogn
andn
(0)areallsmooth.Forexample:2nlog2n=2n(logn+log2)
(nlogn)比想像的更“平滑”Letf(n)beasmoothfunction,then,foranyfixedintegerb2,f(bn)(f(n)).Thatis,thereexistpositiveconstantscb
anddb
andanonnegativeintegern0suchthatdbf(n)f(bn)cbf(n)forn
n0.平滑规则LetT(n)beaneventuallynondecreasingfunctionandf(n)beasmoothfunction.IfT(n)
(f(n))forvaluesofnthatarepowersofb(b2),thenT(n)
(f(n)).
Non-decreasinghypothesisPriorresultNon-decreasing问题9:你能解释一下这是如何“推广”的吗?证明的关键
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 结构力学优化算法:灵敏度分析:结构优化设计方法学
- 元音字母在开闭音节中的发音规律
- 英语教学法教程unitteachingspeaking(共54张课件)
- 公司饭堂天然气使用操作规程
- 做有梦想的少年 课件-2024-2025学年统编版道德与法治七年级上册
- 第37讲+近代西方的商业贸易、城市化进程(课件)-2024年高考历史一轮复习讲练测(新教材新高考)
- 压床护理操作技术
- 外科围手术期的护理
- 第27讲 区域发展对交通运输布局的影响(练习)(原卷版)
- 深圳桐林半山豪宅项目品牌形象广告策划案
- 机械设备修理工艺教案
- 渠道工程施工方案及方法
- 第二章 数据管理 _stata统计分析与应用
- 义务教育阶段课堂教学评价指导意见
- 中国历史地理
- 电火花测试题
- 市政道路给排水管道的设计与施工要点分析
- 青岛版九年级上数学教学计划
- 托管班创业项目企划书
- 外研版四年级上册英语课件 Module 2 Unit 2
- DFMEA表格模板(完整版)
评论
0/150
提交评论