计算机问题求解：基本的算法结构

计算机问题求解

–

论题1-4

基本的算法结构问题1:你会吃蟹黄汤包吗?轻轻提,慢慢移,先开窗,再喝汤。吃一只蟹黄汤包的“算法”顺序很重要：将包子从蒸笼中轻轻提起，andthen将包子慢慢移动到面前的小碟子中，andthen在包子的正上方咬开一个小口，andthen通过小口吸食包子里的汤(当心别烫着)，andthen将包子送入口中。完成！问题2：你如何确保过程无误？假如我们认为在步骤4和5执行前要确保前面的结果是正确的，可以在相应的地方设个“监视哨”–“guard”。问题3：但是我们并不只是吃一只，那怎么办呢？策略一：控制数量假如规定吃8只：开始设一个计数器，并将其值设定为0。吃一只汤包计数器值加1，并判断其是否为8否是结束注意：这个过程的“结构”与计数器的初始值没有关系！策略二：吃饱为止是否已饱？是否问题4：如果即使饱了，也希望至少品尝一只，该怎么办？如何确定循环过程是正确的？循环不变式这是一个逻辑表达式在循环体中它应该始终为“真”例如：用一个逐项累加的循环计算a*b,循环不变式可以是：“存放中间结果的量的值=a*“循环变量的当前值”问题5：你能为上述两种吃蟹黄汤包的策略选定一个循环不变式吗？“冒泡”排序–循环的嵌套自下往上问题6:是否可以将“冒泡”中的内层循环表示成一个procedure/subroutine,形式上成为单层循环？Max(E,low,high):找出指定范围内的最大元素有人知道饱不饱，但有人不知道！开始要吃汤包的人不到5岁吗？是选用策略1选用策略2否结束问题7：如果要判断的不止是两种可能，那怎么办？分类定量控制开始要吃汤包的人不到5岁吗？否参数设为2是结束要吃汤包的人不到60岁吗？参数设为8是参数设为4否选用策略1(带参数)一个相对复杂的复合结构的例子两个指针各是什么含义？关于“Goto”问题8：你理解下面的话吗？Dijkstra,EdsgerW.,“GoTostatementconsideredharmful,”CommunicationsoftheACM,Vol.11,Num.3,1968,pp.147–148.TheLettertotheEditorthatignitedtheinfamous“GoTo”controversy.Submittedunderthetitle“AcaseagainsttheGOTOstatement,”andretitledbytheeditor.Thetitletemplate“Xconsideredharmful”wasformanyyearsusedinthetitlesofrantsanddiatribes.Forfundamentalcontributionstoprogrammingasahigh,intellectualchallenge;foreloquentinsistenceandpracticaldemonstrationthatprogramsshouldbecomposedcorrectly,notjustdebuggedintocorrectness;forilluminatingperceptionofproblemsatthefoundationsofprogramdesign.大师与“goto语句”EdsjerWybeDijkstra(1930-2002),获1972年图林奖ThetitleofEdsger

Dijkstra’s1968“GoToStatementConsideredHarmful”isamongthebest-knownphrasesinthehistoryofprogramming.Interestingly,thephrasingofthetitle—whichhasbecomesoregularaclicheinthefielditinspiredEricMeyertocomposethewaggish“‘ConsideredHarmful’EssaysConsideredHarmful”—wasnotDijkstra’sworkatall.AsDijkstraexplainedit:

Finallyashortstoryfortherecord.In1968,theCommunicationsoftheACMpublishedatextofmineunderthetitle“Thegotostatementconsideredharmful,”whichinlateryearswouldbemostfrequentlyreferenced,regrettably,however,oftenbyauthorswhohadseennomoreofitthanitstitle,whichbecameacornerstoneofmyfamebybecomingatemplate:wewouldseeallsortsofarticlesunderthetitle“Xconsideredharmful”foralmostanyX,includingonetitled“Dijkstraconsideredharmful.”Butwhathadhappened?Ihadsubmittedapaperunderthetitle“Acaseagainstthegotostatement”,which,inordertospeedupitspublication,theeditorhadchangedintoa“lettertotheEditor”,andintheprocesshehadgivenitanewtitleofhisowninvention!TheeditorwasNiklausWirth.关于“Goto”的历史逸事HanoiTower–