問題求解論題1-4：算法的基本結構PPT課件

1、問題求解論題1-4：算法的基本結構陶先平2021-10-28吃一只湯包的“算法”順序很重要：將包子從蒸籠中輕輕提起，and then將包子慢慢移動到面前的碟子中，and then在包子的上方咬開一個小口，and then通過小口吸食包子里的湯，and then將包子送入口中完成！順序，是組織算法的最基本的方法按照算法步驟，順序書寫指令如何理解下面這句話？ 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順序結構產生最小的gap問題2：但是我們并不只吃一只，怎么辦？Bound iteration如果即使飽了，也希望再品嘗一個，該怎么辦？Unbound iteration問題：你能正確選擇采用何種策略設計循環(huán)嗎？程序中的死循環(huán)，一定是什么原因？問題： 如果說順序、分支和循環(huán)構成了算法組織的三個基本結構，那么順序結構是算法組織的基本中的基本。為什么？嵌套結構：循環(huán)嵌套冒泡冒泡排序排序冒泡排序的算法描述關于Goto語句#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語句#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語句： 面條式的程序： 文本空間中的程序： 下鍋前的面條 運行中的執(zhí)行序列： 下鍋后的面條 難以想象！ 文本空間和時間空間上巨大的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順序結構、分支結構、循環(huán)結構這三種結構產生的gap？Goto結構產生的gap？理解并記?。篧hy？何為：控制結構的表達能力 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.一種新的算法組織方法：子程序(過程,函數)問題：什么情況下，我們會想到用過程來“封裝”一段算法？ 這是一種自底向上的思維方式什么情況下，我們會想到將一個算法“分解”為若干個“子算法”的聯(lián)合？ 這是一種自頂向下的思維方式兩種思維方法的碰撞產生了“結構化程序設計”一種新的算法組織方法：子程序(過程,函數) 過程的優(yōu)點： 復用 封裝 抽象 豐富了算法結構： 順序、 分支、循環(huán) 調用若干問題子程序這么一種算法(或者說程序)的構造和使用方式，其數學基礎是什么？從它的數學基礎出發(fā)

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