問(wèn)題求解論題1-4：算法的基本結(jié)構(gòu)PPT課件

1、問(wèn)題求解論題1-4：算法的基本結(jié)構(gòu)陶先平2021-10-28吃一只湯包的“算法”順序很重要：將包子從蒸籠中輕輕提起，and then將包子慢慢移動(dòng)到面前的碟子中，and then在包子的上方咬開(kāi)一個(gè)小口，and then通過(guò)小口吸食包子里的湯，and then將包子送入口中完成！順序，是組織算法的最基本的方法按照算法步驟，順序書(shū)寫(xiě)指令如何理解下面這句話？ My second remark is that our intellectual powers are rather geared to master static relations and that our powers to visu

2、alize processes evolving in time are relatively poorly developed. For that reason we should do our utmost to shorten the conceptual gap between the static program and the dynamic process, to make the correspondence between the program (spread out in text space) and the process (spread out in time) a

3、s trivial as possible. -E.W.Dijkstra順序結(jié)構(gòu)產(chǎn)生最小的gap問(wèn)題2：但是我們并不只吃一只，怎么辦？Bound iteration如果即使飽了，也希望再品嘗一個(gè)，該怎么辦？Unbound iteration問(wèn)題：你能正確選擇采用何種策略設(shè)計(jì)循環(huán)嗎？程序中的死循環(huán)，一定是什么原因？問(wèn)題： 如果說(shuō)順序、分支和循環(huán)構(gòu)成了算法組織的三個(gè)基本結(jié)構(gòu)，那么順序結(jié)構(gòu)是算法組織的基本中的基本。為什么？嵌套結(jié)構(gòu)：循環(huán)嵌套冒泡冒泡排序排序冒泡排序的算法描述關(guān)于Goto語(yǔ)句#includestdio.hint main(void) int n=0; printf(input a st

4、ring ：n);loop: if(getchar()!=n) n+; goto loop; printf(%d,n); Goto語(yǔ)句#include int main(void) int i, j, k; for (i = 0; i 10; i+) for (j = 0; j 10; j+) for (k = 0; k 10; k+) if (i + j + k = 10) break； printf(%d %d %d, i, j, k); #include int main(void) int i, j, k; for (i = 0; i 10; i+) for (j = 0; j 10;

5、 j+) for (k = 0; k 10; k+) if (i + j + k = 10) goto exit_for; exit_for: printf(%d %d %d, i, j, k);如果不加限制地使用goto語(yǔ)句： 面條式的程序： 文本空間中的程序： 下鍋前的面條 運(yùn)行中的執(zhí)行序列： 下鍋后的面條 難以想象！ 文本空間和時(shí)間空間上巨大的gap重新閱讀下面這句話？ My second remark is that our intellectual powers are rather geared to master static relations and that our pow

6、ers to visualize processes evolving in time are relatively poorly developed. For that reason we should do our utmost to shorten the conceptual gap between the static program and the dynamic process, to make the correspondence between the program (spread out in text space) and the process (spread out

7、 in time) as trivial as possible. -E.W.Dijkstra順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)這三種結(jié)構(gòu)產(chǎn)生的gap？Goto結(jié)構(gòu)產(chǎn)生的gap？理解并記?。篧hy？何為：控制結(jié)構(gòu)的表達(dá)能力 Various minimal sets of control structures have been identified, meaning that in certain technical senses other control structures can be replaced by appropriate combinations of those in the

8、minimal set, so that in practice these are the only ones needed.一種新的算法組織方法：子程序(過(guò)程,函數(shù))問(wèn)題：什么情況下，我們會(huì)想到用過(guò)程來(lái)“封裝”一段算法？ 這是一種自底向上的思維方式什么情況下，我們會(huì)想到將一個(gè)算法“分解”為若干個(gè)“子算法”的聯(lián)合？ 這是一種自頂向下的思維方式兩種思維方法的碰撞產(chǎn)生了“結(jié)構(gòu)化程序設(shè)計(jì)”一種新的算法組織方法：子程序(過(guò)程,函數(shù)) 過(guò)程的優(yōu)點(diǎn)： 復(fù)用 封裝 抽象 豐富了算法結(jié)構(gòu)： 順序、 分支、循環(huán) 調(diào)用若干問(wèn)題子程序這么一種算法(或者說(shuō)程序)的構(gòu)造和使用方式，其數(shù)學(xué)基礎(chǔ)是什么？從它的數(shù)學(xué)基礎(chǔ)出發(fā)

9、，你能夠洞悉程序設(shè)計(jì)中關(guān)于子程序的以下概念嗎?形式參數(shù)、實(shí)在參數(shù)、傳參變量的作用域子程序的副作用遞歸：自己調(diào)用自己的過(guò)程它怎么就遞歸了呢？ 定義Move N from X to Y using Z 當(dāng)N=4時(shí)問(wèn)題：它怎么就遞歸了呢？XYZ遞歸：自己調(diào)用自己的過(guò)程 例題：從一個(gè)很長(zhǎng)的數(shù)列中，怎樣找到最大的數(shù)？觀察： 遞歸調(diào)用自身時(shí)，輸入的參數(shù)相比前一次調(diào)用時(shí)使用的參數(shù)，在值上通常會(huì)有什么特點(diǎn)？問(wèn)題：為什么這個(gè)問(wèn)題能夠用遞歸的方法去做？問(wèn)題：為什么這個(gè)問(wèn)題能夠用遞歸的方法去做？思考：遞歸方法和數(shù)學(xué)歸納法有關(guān)聯(lián)關(guān)系嗎？如何確定循環(huán)過(guò)程是正確的？循環(huán)不變式(循環(huán)不變量)： 一個(gè)邏輯表達(dá)式 該表達(dá)式通常可用來(lái)表征循環(huán)的功能 循環(huán)初試時(shí)為真 在循環(huán)執(zhí)行過(guò)程中始終為“真” 循環(huán)結(jié)束時(shí)，必定為真下例