计算机问题求解：递归及其数学基础

计算机问题求解

–

论题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：你能解释一下这是如何“推广”的吗？证明的关键