235-Ch5-离散数学英文版课件

Chapter5:InductionandRecursion(Part2)ElementsofDiscreteStructuresRecursivelyDefinedFunctionsDefineafunctionf(n)recursively,nisanintegerandn≥0:BasisStep:Specifythevalueofthefunctionatn=0(oraspecialvalue):f(0)RecursiveStep:Forn≥0,specifyaruleforproducingthevalueoff(n+1)fromf(n)Example:

f(0)=3

f(n+1)=2f(n)+3

f(3)=2f(2)+3=2(2f(1)+3)+3

=2(2(f(0)+3)+3)+3=2(2(3+3)+3)+3=45RecursiveFunctionExampleRecursivedefinitionoffactorialfunction

f(n)=n!=n(n-1)(n-2)…21andf(0)=0!=1Basis:f(0)=1Recursive:f(n+1)=(n+1)f(n)f(5)=5f(4)=54f(3)=543f(2)=5432f(1)=54321f(0)=543211=120RecursiveFunctionExampleGivearecursivedefinitionof:Solution:ThefirstpartofthedefinitionisThesecondpartisFibonacciFunctionf(0)=0,f(1)=1,f(n)=f(n-1)+f(n-2)

forn=2,3,4,...f(2)=f(1)+f(0)=1+0=1f(3)=f(2)+f(1)=1+1=2f(4)=f(3)+f(2)=2+1=3f(5)=f(4)+f(3)=3+2=5f(6)=f(5)+f(4)=5+3=8WedenoteFibonaccinumbersasfn=f(n),n=0,1,2,…FibonacciNumbersSupposeanewly-bornpairofrabbits,onemale,onefemale,areputinafield.Rabbitsareabletomateattheageofonemonthsothatattheendofitssecondmonthafemalecanproduceanotherpairofrabbits.Supposethatourrabbitsneverdieandthatthefemalealways

producesonenewpair(onemale,onefemale)everymonth

f1=1f2=f1+f0=1+0=1f3=f2+f1=1+1=2f4=f3+f2=2+1=3f5=f4+f3=3+2=5f6=f5+f4=5+3=8FibonacciExampleTheorem:Whenn≥3,fn>n-2,=(1+5)/2ProofbystronginductionBasisstep:Forn=3,f3=2>=(1+5)/2(5=2.236…)

Forn=4,f4=3>2=(3+5)/2Whyweneedtoproven=3andn=4?FibonacciExampleInductivestep:Assumefj>j-2,forallj,3jk,k≥4.

Wemustshowthatfk+1>k-1.Notethat

fk+1=fk+fk-1

Byinductionassumption,fk>k-2andfk-1>k-3

So,fk+1=fk+fk-1>k-2+k-3

Wenowonlyneedtoshowthatk-2+k-3=k-1isasolutionofx2–x–1=0,so2=+1

k-1=2k-3=(+1)k-3=k-2+k-3RecursivelyDefinedInfiniteSetsBasisStep:SpecifyaninitialcollectionofelementsinthesetRecursiveStep:ProviderulesforformingnewelementsinthesetfromthosealreadyknowntobeinthesetExample:BasisStep:3SRecursiveStep:ifxSandySthenx+ySThen,S={3,6,9,12,15,18,21,…}RecursiveDefinitionofStringsSetofstrings,denotedas*,overanalphabetorsymbolsetcanbedefinedrecursivelybyBasis:

*(istheemptystring)Recursive:ifw

*andx

,thenwx

*Example:={0,1}.*containsthefollowing:emptystring0,100,01,10,11000,001,010,011,100,101,110,111,…StringConcatenationDefinition:Twostringscanbecombinedviatheoperationofconcatenation(串联).LetΣbeasetofsymbolsandΣ*bethesetofstringsformedfromthesymbolsinΣ.Wecandefinetheconcatenationoftwostrings,denotedby∙,asfollowsForanyw

Σ*,w∙λ=w,λistheemptystringIfw1

Σ*andw2

Σ*,then

theconcatenationofw1andw2isw1∙w2

orjustw1w2Ifw1=abraandw2=cadabra,theconcatenationw1w2=abracadabraLengthofStringLengthofastringisdefinedasthenumberofsymbolsinthestringRecursivedefinitionoflengthofastringBasis:l()=0Recursive:l(wx)=l(w)+1,w

*andx

LetbetheEnglishletters.Findthelengthof“math”:l(math)=l(mat)+1=(l(ma)+1)+1=((l(m)+1)+1)+1=(((l()+1)+1)+1)+1=(0+1)+3=4BalancedParenthesesExample:GivearecursivedefinitionofthesetofbalancedparenthesesP

Solution:BasisStep:()∊

PRecursiveStep:Ifw

∊

P,then

()w∊

P,(w)

∊

Pandw()

∊

P.Showthat(()(()))isinP.Whyis))(()notinP?Well-FormedFormulas(合适公式)ExampleWell-FormedFormulasforcompoundpropositionsincludeT,F,propositionalvariablesandoperators(,,,,)Recursivedefinitionofwell-formedformulas:Basis:T,Fandanypropositionalvariablexarewell-formedformulasRecursive:ifAandBarewell-formedformulas,thenA,AB,AB,ABandABarealsowell-formedformulasWell-FormedFormulasExampleExamples.Arethefollowingwell-formedformulas?

(Fromdefinition,startwiththevariableofsingle-operandoperator)((A((B)))((C)(D)))(((AB))C)((A(B))(D))(AB)CT1T2T3T4T5T1T2T2T2T2T1T1FullBinaryTree(满二叉树)ExampleBasisStep:anysinglenodeisabinarytreeInductiveStep::IfT1andT2arefullbinarytrees,thenthefollowingtreeTisalsoafullbinarytree:pickanewrootnodeandattachittotherootofT1asaleftsubtreeandtotherootofT2asarightsubtree(T1andT2canbethesame).DenotedT=T1T2So,whatisafullbinarytree?Basis:theemptysetisanextendedbinarytreeInductive::IfT1andT2areextendedbinarytrees,thenthefollowingtreeTisalsoanextendedbinarytree:pickanewrootnodeandattachittotherootofT1asaleftsubtreeandtotherootofT2asarightsubtree(T1andT2canbethesame).DenotedT=T1T2ExtendedBinaryTreeExampleT0T1T2T3T4T1T1T1T0T1T0T0T5T6T7T8T9T13T0StructuralInductionApplyingStructuralInductionforrecursivelydefinedsetsBasisStep:ShowthattheresultistrueforallelementsspecifiedinthebasisstepoftherecursivedefinitionRecursive(orinductive)Step:Showthat,iftheresultistruefortheoldelementsusedinconstructingnewelements,thenitisalsotrueforthenewelementsInductionExampleShowthatthesetSrecursivelydefinedas“3SandifxSandySthenx+yS”,isthesetofallpositiveintegersthataremultiplesof3Proof:letAbethesetofallpositiveintegersthataremultiplesof3,A={3n|n=1,2,…}.WeneedtoproveASandSA,whichprovesS=AAS:(SimpleInductiononn)whenn=1,3S.Assumewhenn=k,3kS.Forn=k+1,weneedtoshowthat3(k+1)S.3(k+1)=3k+3,byinductionassumption3kS.Alsofrominductionbasis,3S.ByrecursivedefinitionofS(letx=3kandy=3),3(k+1)=3k+3SStructuralInductionExampleProof(continued):SA:(StructuralInduction)weneedtoshowthatanyelementinSisamultipleof3(A)

Basisstep:3isinSand3isamultipleof3

Recursivestep:assumetheelements(xandy)usedtobuildnewelementsaretrue(multiplesof3).Showthatthenewlybuiltelements(x+y)isalsotrue(multipleof3).Weknowbypreviousknowledgethatif3|xand3|y,then3|(x+y).So,x+yAStructuralInductionExampleUsestructuralinductiontoshowthatl(xy)=l(x)+l(y)l(w)=lengthofstringwandx,y,w

*oversymbolsetBasisstep:(Inductiononlengthofy).Whenlengthofy=0,y=.

l(x)=l(x)=l(x)+0=l(x)+l()Recursivestep:assumel(xy)=l(x)+l(y),whenlengthofy=k.Weneedtoprove,whenthelengthofyaisk+1,a

,l(xya)=l(x)+l(ya)Bydefinitionoflength,l(xya)=l(xy)+1

=l(x)+l(y)+1(byinductionassumption)

=l(x)+l(ya)(bydefinitionoflength)BinaryTreeExampleRecursiveDefinitionoftheheightofafullbinarytreeT,denotedh(T):

Basis:Theheightofthefullbinarytreeofonlyarootiszero:

h(T)=0

Recursive:IfT1andT2arefullbinarytrees,thenthefullbinarytreeformedfromthem,T=T1T2,hasheight

h(T)=1+max(h(T1),h(T2))BinaryTreeExampleRecursiveDefinitionofthenumberofnodesinabinarytreeT,denotedn(T):

Basis:Thenumberofnodesofthefullbinarytreeofonlyaroot:n(T)=1

Recursive:IfT1andT2arebinarytrees,thenthenumberofnodesforthefullbinarytreeT=T1T2is

n(T)=1+n(T1)+n(T2)BinaryTreeExampleTheorem:IfTisafullbinarytreeT,

thenn(T)2h(T)+1–1 (i)ProofbystructuralInduction

Basis:forafullbinarytreeofonlyaroot,n(T)=1andh(T)=0.So,1=n(T)2h(T)+1–1=21–1=1

Inductive:AssumeforfullbinarytreeT1,

n(T1)2h(T1)+1–1 (ii)

andforfullbinarytreeT2,

n(T2)2h(T2)+1–1 (iii)

weneedtoshowthatifT=T1T2,

then(i)holdsBinaryTreeExampleProof(continued)

n(T)=1+n(T1)+n(T2)(recursivedefinition)

1+(2h(T1)+1–1)+(2h(T2)+1–1)((ii)and(iii))

=2h(T1)+1+2h(T2)+1–1

2max(2h(T1)+1,

2h(T2)+1)–1

=22max(h(T1)+1,

h(T2)+1)

–1(max(2x,2y)=2max(x,y))

=22max(h(T1),

h(T2))+1–1

=22h(T)–1 (recursivedefinitionofh(T))

=2h(T)+1–1n(T2)=3,h(T2)=1,verifythatn(T2)2h(T2)+1–1n(T3)=5,h(T3)=2,verifythatn(T3)2h(T3)+1–1n(T5)=7,h(T5)=2,verifythatn(T5)2h(T5)+1–1T1T2T3T4T5T1T2T2T2T2T1T1BinaryTreeExampleRecursiveAlgorithmsDefinition:

AnalgorithmiscalledrecursiveifItsolvesaproblembyreducingittoaninstanceofthesameproblemwithsmallerinputThisreductionmustleadtothebasisstepforwhichthesolutionisknownFactorialRecursiveAlgorithmComputingn!basedontherecursivedefinition (i)0!=1and(ii)n!=n

(n1)!forn>0

procedure

factorial(n:nonnegativeinteger)

if

n

1then

factorial(n):=1 {BasisStep}else

factorial(n):=n

factorial(n-1)Howisfactorial(6)calculated?PowerRecursiveAlgorithmComputinganbasedontherecursivedefinition (i)a0=1and(ii)an=a

an-1forn>0

procedure

power(a:nonzerorealnumber,n:nonnegativeinteger)

if

n=0thenpower(a,n):=1

else

power(a,n):=a

power(a,n–1)Howis24iscomputedinpower?SumRecursiveAlgorithmWeuserecursivealgorithmtocomputethesumofnnumbersa1,a2,…,an.Exampleofsum(a1,a2,a3:3)=…proceduresum(a1,,an:list,n:positiveInteger)

ifn=1thensum(a1,,an,n)=a1

elsesum(a1,,an,n)=an+sum(a1,,an,n-1)GCDRecursiveAlgorithmComputinggcd(a,b)basedon

(i)Basisstep:gcd(a,0)=awhena>0,and

(ii)Recursive

step:gcd(a,b)=gcd(b,a

mod

b)

forb>0

procedure

gcd(a,b:nonnegativeintegerswitha>b)if

b=0then

gcd(a,b):=aelse

gcd(a,b):=gcd(b,amodb)Example:Computegcd(44,24)BinarySearchRecursiveAlgorithmBinarysearchinasortedlistofnelementscanbereducedtoacomparisonwiththemiddleelementsandabinarysearchofoneofthetwosmallerlistswith(n+1)/2elementsprocedure

binary-search(i,j,x){Dataina1,,aninascendingorder}m:=(i+j)/2if

x=amthen

returnm {misthelocationforx}elseif(x<am

andi<m)then

binary-search(i,m–1,x)elseif(x>am

andj>m)then

binary-search(m+1,j,x)else

return

0 {Notfound!}{Outputisthelocationofthetermequaltox,or0ifnotfound}Example:a=(2,3,5,6,8),binary-search(1,5,8)=…=5Firstsplitlistsuccessivelyintopairssotheresultisabalancedbinarytree(upperhalf)Sortingisdonebysuccessivelymergingthepairsoflistsinascendingorder(bottomhalf)MergeSort(归并排序)AlgorithmSplitMergeRecursiveAlgorithmforMergeSortProceduremergesortusesasubroutine

merge(onthenextslide)tomergetwolistsintoasortedoneinascendingorderprocedure

ms(L=a1,,an){msformergesort,omittingn}ifn1then

return

Lelse

m:=n/2

L1:=a1,,am

L2:=am+1,,an

L:=merge(ms(L1),ms(L2))Example:ms(8,2,3,6,1)=…MergingExampleLL1L2MergingTwoListsprocedure

merge(L1,L2:sortedlistsinnondecreasingorder)

L:=emptylist

while

L1andL2arebothnonemptyRemovesmalleroffirstelementofL1andL2fromthelistitisinandaddittotheendofL.

ifremovalofthiselementmakesonelistemptythenRemoveallelementsfromtheremaininglistandappendthemtoLreturnL{Listhemergedlistwithelementsinnondecreasingorder}TimeComplexityofMergeLetm,2mn,bethetotalnumberofnumbersinthetwoliststobemerged.nisthenumberofnumberstobesortedbymergesortEverycomparisonresultsinoneelementbeingremovedfromoneofthetwolistsTherewillbeatmostm–1comparisons(thelastonedoesnotneedacomparison)ThisleadstoO(m)timecomplexityTimeComplexityofMergeSortLetnbethenumberofnumberstobesortedandisapowerof2(n=2k,forsomepositiveintegerk.So,k=log2(n))Thismakesthetreeacompletebinarytree(worstcase).Whentheheightisk,therearen(=2k)leavesInmergingthelists,thefirststepistocompareandsortthenumbersattheleaves:

n/2comparisonsThelaststepiscompareandsorttwolistsrightundertheroot:n–1comparisonsTimeComplexityofMergeSortTimecomplexityoftherecursivemergesortalgorithmiskO(n)=O(kn)=O(nlog2n)height=k:n/2=O(n)

ComparisonsEachheightfrom2tok-1:

n/2<Comparisons<n-1

AlsoO(n)height=1:n–1=O(n)

Comparisonsheight=k-1:3(n/4)=O(n)

Comparisons1178591341216610142151371158193412166102141315578111349610121621314151345789112610121314151612345678910111213141516TimeComplexityofMergeSortTotalnumberofcomparisonsis

TimecomplexityoftherecursivemergesortalgorithmisO(nlog2n)(Sameasinthetextbook)Recursio