計(jì)算機(jī)問(wèn)題求解

–

論題1-4

基本的算法結(jié)構(gòu)問(wèn)題1:你會(huì)吃蟹黃湯包嗎?輕輕提,慢慢移,先開(kāi)窗,再喝湯。吃一只蟹黃湯包的“算法”順序很重要：將包子從蒸籠中輕輕提起，andthen將包子慢慢移動(dòng)到面前的小碟子中，andthen在包子的正上方咬開(kāi)一個(gè)小口，andthen通過(guò)小口吸食包子里的湯(當(dāng)心別燙著)，andthen將包子送入口中。完成！問(wèn)題2：你如何確保過(guò)程無(wú)誤？假如我們認(rèn)為在步驟4和5執(zhí)行前要確保前面的結(jié)果是正確的，可以在相應(yīng)的地方設(shè)個(gè)“監(jiān)視哨”–“guard”。問(wèn)題3：但是我們并不只是吃一只，那怎么辦呢？策略一：控制數(shù)量假如規(guī)定吃8只：開(kāi)始設(shè)一個(gè)計(jì)數(shù)器，并將其值設(shè)定為0。吃一只湯包計(jì)數(shù)器值加1，并判斷其是否為8否是結(jié)束注意：這個(gè)過(guò)程的“結(jié)構(gòu)”與計(jì)數(shù)器的初始值沒(méi)有關(guān)系！策略二：吃飽為止是否已飽？是否問(wèn)題4：如果即使飽了，也希望至少品嘗一只，該怎么辦？如何確定循環(huán)過(guò)程是正確的？循環(huán)不變式這是一個(gè)邏輯表達(dá)式在循環(huán)體中它應(yīng)該始終為“真”例如：用一個(gè)逐項(xiàng)累加的循環(huán)計(jì)算a*b,循環(huán)不變式可以是：“存放中間結(jié)果的量的值=a*“循環(huán)變量的當(dāng)前值”問(wèn)題5：你能為上述兩種吃蟹黃湯包的策略選定一個(gè)循環(huán)不變式嗎？“冒泡”排序–循環(huán)的嵌套自下往上問(wèn)題6:是否可以將“冒泡”中的內(nèi)層循環(huán)表示成一個(gè)procedure/subroutine,形式上成為單層循環(huán)？Max(E,low,high):找出指定范圍內(nèi)的最大元素有人知道飽不飽，但有人不知道！開(kāi)始要吃湯包的人不到5歲嗎？是選用策略1選用策略2否結(jié)束問(wèn)題7：如果要判斷的不止是兩種可能，那怎么辦？分類(lèi)定量控制開(kāi)始要吃湯包的人不到5歲嗎？否參數(shù)設(shè)為2是結(jié)束要吃湯包的人不到60歲嗎？參數(shù)設(shè)為8是參數(shù)設(shè)為4否選用策略1(帶參數(shù))一個(gè)相對(duì)復(fù)雜的復(fù)合結(jié)構(gòu)的例子兩個(gè)指針各是什么含義？關(guān)于“Goto”問(wèn)題8：你理解下面的話(huà)嗎？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語(yǔ)句”EdsjerWybeDijkstra(1930-2002),獲1972年圖林獎(jiǎng)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“l(fā)ettertotheEditor”,andintheprocesshehadgivenitanewtitleofhisowninvention!TheeditorwasNiklausWirth.關(guān)于“Goto”的歷史逸事HanoiTower–