ancakes with a problem：有问题的煎饼

《ancakes with a problem：有问题的煎饼》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、PancakesWithAProblem!GreatTheoreticalIdeasInComputerScienceAnupamGuptaCS15-251Fall2O05Lecture1Aug29th,2OO5CarnegieMellonUniversityCourseStaffProfs:AnupamGuptaJohnLaffertyTAs:KanatTangwongsanYinmengZhanghttp://www.cs.cmu.edu/~15251Pleasecheckthewebpagesregularly!Pleasefeelfreetoa

2、skquestions!((()))CourseDocumentYoumustreadthiscarefully.Gradingformulaforthecourse.40%homework5%in-classquizzes25%in-recitationtests30%finalSevenpointsadaylatepenalty.Collaboration/CheatingPolicyYoumayNOTsharewrittenwork.Wereusehomeworkproblems.PancakesWithAProblem!GreatTheore

3、ticalIdeasInComputerScienceAnupamGuptaCS15-251Fall2O05Lecture1Aug29th,2OO5CarnegieMellonUniversityThechefatourplaceissloppy,andwhenhepreparesastackofpancakestheycomeoutalldifferentsizes.Therefore,whenIdeliverthemtoacustomer,onthewaytothetableIrearrangethem(sothatthesmallestwinds

4、upontop,andsoon,downtothelargestatthebottom)Idothisbygrabbingseveralfromthetopandflippingthemover,repeatingthis(varyingthenumberIflip)asmanytimesasnecessary.DevelopingANotation:TurningpancakesintonumbersDevelopingANotation:TurningpancakesintonumbersDevelopingANotation:Turni

5、ngpancakesintonumbers23451DevelopingANotation:Turningpancakesintonumbers52341Howdowesortthisstack?Howmanyflipsdoweneed?523414FlipsAreSufficient1234552341432152341514325AlgebraicRepresentation52341X=Thesmallestnumberofflipsrequiredtosort:?X?UpperBoundLowerBoundAlgebraicR

6、epresentation52341X=Thesmallestnumberofflipsrequiredtosort:?X4UpperBoundLowerBound4Flipsarenecessaryinthiscase523414132514325Flip1hastoput5onbottomFlip2mustbring4totop.UpperBoundLowerBound4X4X=45thPancakeNumberThenumberofflipsrequiredtosorttheworstcasestackof5pancakes.?P5

7、?UpperBoundLowerBoundP5=5thPancakeNumberThenumberofflipsrequiredtosorttheworstcasestackof5pancakes.4P5?UpperBoundLowerBoundP5=..........The5thPancakeNumber:TheMAXoftheX’s120119932X1X2X3X119X120523414The5thPancakeNumber:TheMAXoftheX’s1201993..........X1X2X3X119X12052341412345

8、543211201993..........X1X2X3X119X12052341412345