Ch離散數(shù)學(xué)英文實(shí)用

會(huì)計(jì)學(xué)1Ch離散數(shù)學(xué)英文實(shí)用RecursivelyDefinedFunctionsDefineafunctionf(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=45第1頁(yè)/共44頁(yè)RecursiveFunctionExampleRecursivedefinitionoffactorialfunction

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=120第2頁(yè)/共44頁(yè)RecursiveFunctionExampleGivearecursivedefinitionof:Solution:ThefirstpartofthedefinitionisThesecondpartis第3頁(yè)/共44頁(yè)FibonacciFunctionf(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,…第4頁(yè)/共44頁(yè)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=8第5頁(yè)/共44頁(yè)FibonacciExampleTheorem: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?第6頁(yè)/共44頁(yè)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-3第7頁(yè)/共44頁(yè)RecursivelyDefinedInfiniteSetsBasisStep:SpecifyaninitialcollectionofelementsinthesetRecursiveStep:ProviderulesforformingnewelementsinthesetfromthosealreadyknowntobeinthesetExample:BasisStep:3SRecursiveStep:ifxSandySthenx+ySThen,S={3,6,9,12,15,18,21,…}第8頁(yè)/共44頁(yè)RecursiveDefinitionofStringsSetofstrings,denotedas*,overanalphabetorsymbolsetcanbedefinedrecursivelybyBasis:

*(istheemptystring)Recursive:ifw

*andx

,thenwx

*Example:={0,1}.*containsthefollowing:emptystring0,100,01,10,11000,001,010,011,100,101,110,111,…第9頁(yè)/共44頁(yè)StringConcatenationDefinition:Twostringscanbecombinedviatheoperationofconcatenation(串聯(lián)).LetΣbeasetofsymbolsandΣ*bethesetofstringsformedfromthesymbolsinΣ.Wecandefinetheconcatenationoftwostrings,denotedby?,asfollowsForanyw

Σ*,w?λ=w,λistheemptystringIfw1

Σ*andw2

Σ*,then

theconcatenationofw1andw2isw1?w2

orjustw1w2Ifw1=abraandw2=cadabra,theconcatenationw1w2=abracadabra第10頁(yè)/共44頁(yè)LengthofStringLengthofastringisdefinedasthenumberofsymbolsinthestringRecursivedefinitionoflengthofastringBasis: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=4第11頁(yè)/共44頁(yè)BalancedParenthesesExample:GivearecursivedefinitionofthesetofbalancedparenthesesP

Solution:BasisStep:()?

PRecursiveStep:Ifw

?

P,then

()w?

P,(w)

?

Pandw()

?

P.Showthat(()(()))isinP.Whyis))(()notinP?第12頁(yè)/共44頁(yè)Well-FormedFormulas(合適公式)ExampleWell-FormedFormulasforcompoundpropositionsincludeT,F,propositionalvariablesandoperators(,,,,)Recursivedefinitionofwell-formedformulas:Basis:T,Fandanypropositionalvariablexarewell-formedformulasRecursive:ifAandBarewell-formedformulas,thenA,AB,AB,ABandABarealsowell-formedformulas第13頁(yè)/共44頁(yè)Well-FormedFormulasExampleExamples.Arethefollowingwell-formedformulas?

(Fromdefinition,startwiththevariableofsingle-operandoperator)((A((B)))((C)(D)))(((AB))C)((A(B))(D))(AB)C第14頁(yè)/共44頁(yè)T1T2T3T4T5T1T2T2T2T2T1T1FullBinaryTree(滿二叉樹)ExampleBasisStep:anysinglenodeisabinarytreeInductiveStep::IfT1andT2arefullbinarytrees,thenthefollowingtreeTisalsoafullbinarytree:pickanewrootnodeandattachittotherootofT1asaleftsubtreeandtotherootofT2asarightsubtree(T1andT2canbethesame).DenotedT=T1T2So,whatisafullbinarytree?第15頁(yè)/共44頁(yè)Basis:theemptysetisanextendedbinarytreeInductive::IfT1andT2areextendedbinarytrees,thenthefollowingtreeTisalsoanextendedbinarytree:pickanewrootnodeandattachittotherootofT1asaleftsubtreeandtotherootofT2asarightsubtree(T1andT2canbethesame).DenotedT=T1T2ExtendedBinaryTreeExampleT0T1T2T3T4T1T1T1T0T1T0T0T5T6T7T8T9T13T0第16頁(yè)/共44頁(yè)StructuralInductionApplyingStructuralInductionforrecursivelydefinedsetsBasisStep:ShowthattheresultistrueforallelementsspecifiedinthebasisstepoftherecursivedefinitionRecursive(orinductive)Step:Showthat,iftheresultistruefortheoldelementsusedinconstructingnewelements,thenitisalsotrueforthenewelements第17頁(yè)/共44頁(yè)InductionExampleShowthatthesetSrecursivelydefinedas“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+3S第18頁(yè)/共44頁(yè)StructuralInductionExampleProof(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+yA第19頁(yè)/共44頁(yè)StructuralInductionExampleUsestructuralinductiontoshowthatl(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)第20頁(yè)/共44頁(yè)BinaryTreeExampleRecursiveDefinitionoftheheightofafullbinarytreeT,denotedh(T):

Basis:Theheightofthefullbinarytreeofonlyarootiszero:

h(T)=0

Recursive:IfT1andT2arefullbinarytrees,thenthefullbinarytreeformedfromthem,T=T1T2,hasheight

h(T)=1+max(h(T1),h(T2))第21頁(yè)/共44頁(yè)BinaryTreeExampleRecursiveDefinitionofthenumberofnodesinabinarytreeT,denotedn(T):

Basis:Thenumberofnodesofthefullbinarytreeofonlyaroot:n(T)=1

Recursive:IfT1andT2arebinarytrees,thenthenumberofnodesforthefullbinarytreeT=T1T2is

n(T)=1+n(T1)+n(T2)第22頁(yè)/共44頁(yè)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)holds第23頁(yè)/共44頁(yè)BinaryTreeExampleProof(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–1第24頁(yè)/共44頁(yè)n(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–1T1T2T3T4T5T1T2T2T2T2T1T1BinaryTreeExample第25頁(yè)/共44頁(yè)RecursiveAlgorithmsDefinition:

AnalgorithmiscalledrecursiveifItsolvesaproblembyreducingittoaninstanceofthesameproblemwithsmallerinputThisreductionmustleadtothebasisstepforwhichthesolutionisknown第26頁(yè)/共44頁(yè)FactorialRecursiveAlgorithmComputingn!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?第27頁(yè)/共44頁(yè)P(yáng)owerRecursiveAlgorithmComputinganbasedontherecursivedefinition (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?第28頁(yè)/共44頁(yè)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)第29頁(yè)/共44頁(yè)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)第30頁(yè)/共44頁(yè)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)=…=5第31頁(yè)/共44頁(yè)Firstsplitlistsuccessivelyintopairssotheresultisabalancedbinarytree(upperhalf)Sortingisdonebysuccessivelymergingthepairsoflistsinascendingorder(bottomhalf)MergeSort(歸并排序)AlgorithmSplitMerge第32頁(yè)/共44頁(yè)RecursiveAlgorithmforMergeSortProceduremergesortusesasubroutine

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)=…第33頁(yè)/共44頁(yè)MergingExampleLL1L2第34頁(yè)/共44頁(yè)MergingTwoListsprocedure

merge(L1,L2:sortedlistsinnondecreasingorder)

L:=emptylist

while

L1andL2arebothnonemptyRemovesmalleroffirstelementofL1andL2fromthelistitisinandaddittotheendofL.

ifremovalofthiselementmakesonelistemptythenRemoveallelementsfromtheremaininglistandappendthemtoLreturnL{Listhemergedlistwithelementsinnondecreasingorder}第35頁(yè)/共44頁(yè)TimeComplexityofMergeLetm,2mn,bethetotalnumberofnumbersinthetwoliststobemerged.nisthenumberofnumberstobesortedbymergesortEverycomparisonresultsinoneelementbeingremovedfromoneofthetwolistsTherewillbeatmostm–1comparisons(thelastonedoesnotneedacomparison)ThisleadstoO(m)timecomplexity第36頁(yè)/共44頁(yè)TimeComplexityofMergeSortLetnbethenumberofnumberstobesortedandisapowerof2(n=2k,forsomepositiveintegerk.So,k=log2(n))Thismakesthetreeacompletebinarytree(worstcase).Whentheheightisk,therearen(=2k)leavesInmergingthelists,thefirststepistocompareandsortthenumbersattheleaves:

n/2comparisonsThelaststepiscompareandsorttwolistsrightundertheroot:n–1comparisons第37頁(yè)/共44頁(yè)TimeComplexityofMergeSortTimecomplexityoftherecursivemergesortalgorithmiskO(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)

Comparisons1178591341216610142151371158193412166102141315578111349610121621314151345789112610121314151612345678910111213141516第38頁(yè)/共44頁(yè)TimeComplexityofMergeSortTotalnumberofcomparisonsis

TimecomplexityoftherecursivemergesortalgorithmisO(nlog2n)(Sameasinthetextbook)第39頁(yè)/共44頁(yè)Recursionv