算法與程序設(shè)計(jì)(備課)概要課件

算法的概念與程序設(shè)計(jì)劉啟明算法的概念與程序設(shè)計(jì)劉啟明1第4節(jié)算法的概念與程序設(shè)計(jì)

【本章提要】

針對(duì)部分模塊進(jìn)行討論，研究其教學(xué)內(nèi)容、教學(xué)處理要點(diǎn)和教學(xué)中應(yīng)注意的問題。第4節(jié)算法的概念與程序設(shè)計(jì)

【本章提要】2

一、算法二、算法與程序三、重要的循環(huán)算法和遞歸算法四、排序問題五、常用算法一、算法3一、算法1．算法：對(duì)特定問題的求解步驟。2．算法復(fù)雜度3．算法的特征：有窮性、確定性、可行性4．計(jì)算方法：對(duì)求數(shù)值解的近似方法的研究【注意事項(xiàng)】計(jì)算機(jī)求解的問題：有兩大類（數(shù)值和非數(shù)值）【例題】交換兩個(gè)變量的值一、算法1．算法：對(duì)特定問題的求解步驟。4算法atbba算法atbba5算法main(){ floata,b,t; scanf("%f,%f",&a,&b);if(a>b){t=a;a=b;b=t；}printf("%5.2f,%5.2f\n",a,b);}算法main()6二、算法與程序

【程序兩要素】瑞士科學(xué)家沃思（NiklausWirth)有一個(gè)著明的公式程序=算法(操作步驟)+數(shù)據(jù)結(jié)構(gòu)（原料）

【說明】高級(jí)語(yǔ)言的數(shù)據(jù)類型非常豐富，如：字符型、整型、實(shí)型、邏輯型等。

【數(shù)組的概念】一組相關(guān)數(shù)據(jù)的集合，它在內(nèi)存中開辟了若干個(gè)連續(xù)的存儲(chǔ)單元，依次存儲(chǔ)。二、算法與程序7算法與程序

算法表示：

(1)自然語(yǔ)言

(2)傳統(tǒng)流程圖

(3)N-S結(jié)構(gòu)圖：又稱納薩－施內(nèi)德曼圖（Nassi-Sschneiderman).

結(jié)構(gòu)化程序設(shè)計(jì)（三種基本結(jié)構(gòu)）

算法與程序算法表示：8【例題】求3個(gè)數(shù)中最小數(shù)

main(){inta,b,c,t;printf("請(qǐng)輸入三個(gè)整數(shù):");scanf(%d,%d,%d",&a,&b,&c);if(a>b){t=a;a=b;b=t;}if(a>c){t=a;a=c;c=t;}printf("三個(gè)整數(shù)中最大得是%d\n",a);}【例題】求3個(gè)數(shù)中最小數(shù)9a>bYN交換a>cYN交換a>dYN交換……i=1ton-1min>a[i]YN交換a>bYN交換a>cYN交換a>dYN交換……i10三、重要的循環(huán)算法和遞歸算法循環(huán)算法兩類具有代表性的算法（窮舉和迭代）循環(huán)控制的方法（計(jì)數(shù)＼標(biāo)志）例如：迭代算法的教學(xué)（二分法＼牛頓切線）掌握知識(shí)與培養(yǎng)能力的統(tǒng)一主體與客體的統(tǒng)一【教案】用牛頓迭代法求下面方程在1.5附近的根。三、重要的循環(huán)算法和遞歸算法循環(huán)算法掌握知識(shí)與培養(yǎng)能力的11典型的遞歸算法Hanoi（漢諾）塔問題：

古代有一個(gè)梵塔，塔內(nèi)有3個(gè)座A、B、C，開始時(shí)A座上有64個(gè)盤子，盤子大小不等，大的在下，小的在上。有一個(gè)老和尚想把這64個(gè)盤子從A盤移到C座，但每次只允許移動(dòng)一個(gè)盤子，且在移動(dòng)過程中在3個(gè)座上都始終大盤在下，小盤在上。在移動(dòng)過程中可以利用B座，要求編程序打印出移動(dòng)步驟。

算法的演示圖示如下所示：典型的遞歸算法Hanoi（漢諾）塔問題：12典型的遞歸算法ABC132典型的遞歸算法ABC13213四、排序問題例如：排序問題（n個(gè)元素排隊(duì)）

對(duì)數(shù)據(jù)進(jìn)行排序有哪些方法可以實(shí)現(xiàn)？

快速排序、冒泡排序、希爾排序、插入排序、歸并排序……采用冒泡排序方法對(duì)待排序的序列進(jìn)行排序。四、排序問題例如：排序問題（n個(gè)元素排隊(duì)）14

定義一個(gè)大小為6的數(shù)組a[6]a[1]a[2]a[3]a[4]a[5]a[6]初始965743一次后695743二次后659743三次后657943四次后657493五次后657439第一趟冒泡排序最大值注：經(jīng)過第一趟冒泡排序，我們找出了待排序序列中的最大值9，最大值9存放在了數(shù)組a的最后一個(gè)位置。定義一個(gè)大小為6的數(shù)組a[6]最大值注：經(jīng)過第一趟冒泡排序15

a[1]a[2]a[3]a[4]a[5]a[6]初始657439一次后567439二次后567439三次后564739四次后564379第二趟冒泡排序注：經(jīng)過第二趟冒泡排序后，我們找到了次大值7，次大值7存放在數(shù)組a的倒數(shù)第二個(gè)位置a[5]次大值最大值a[1]a[2]a16流程圖是用一些圖框表示各種操作。用圖形表示算法，直觀形象、易于理解。

N-S流程圖---全部的算法寫在一個(gè)矩形框內(nèi)，在框內(nèi)還可以包含其他的從屬于它的框，或者說，由一些基本的框組成一個(gè)大的框。這種流程圖又稱為N-S結(jié)構(gòu)化流程圖。據(jù)此在這里我們可畫出上述冒泡排序算法的N-S流程圖流程圖是用一些圖框表示各種操作。用圖形表示算法，直觀形象、易17描述算法

輸入n個(gè)數(shù)給a[1]到a[n]fori=1ton-1forj=1ton-ia[j]>a[j+1]真假a[j]<=>a[j+1]輸出a[1]到a[n]冒泡排序算法N-S流程圖描述算法18N-S圖描述算法依次對(duì)數(shù)據(jù)序列進(jìn)行冒泡排序：第三趟冒泡排序結(jié)果5-4-3-6-7-9第四趟冒泡排序結(jié)果4-3-5-6-7-9第五趟冒泡排序結(jié)果3-4-5-6-7-9最后我們得到從小到大的順序序列為：3-4-5-6-7-9對(duì)n個(gè)數(shù)據(jù)進(jìn)行排序，需進(jìn)行n-1趟的冒泡排序；每趟冒泡排序過程中，（第i趟冒泡排序中）兩兩數(shù)據(jù)比較進(jìn)行了n-i次N-S圖描述算法依次對(duì)數(shù)據(jù)序列進(jìn)行冒泡排序：對(duì)n個(gè)數(shù)據(jù)進(jìn)行排19

程序如下所示：main(){inta[6];inti,j,t;

printf(“input6numbers:\n”);

for(j=1;j<=6;j++)

scanf(“%d”,&a[i]);

for(j=1;j<6;j++)for(i=1;i<6-j;i++)if(a[i]>a[i+1]) {t=a[i];a[i]=a[i+1];a[i+1]=t;}printf(“theorderednumbers:\n”);for(i=1;i<=6;i++)printf(“%d”,a[i]);}

程序如下所示：main()20

比較沉淀（起泡）選擇重要提示：課堂上強(qiáng)調(diào)以學(xué)生為中心建構(gòu)主義認(rèn)為，學(xué)習(xí)不是知識(shí)經(jīng)驗(yàn)從外到內(nèi)的輸入過程，而是學(xué)習(xí)者通過新舊知識(shí)經(jīng)驗(yàn)之間充分的相互作用而“生成”自己的知識(shí)的過程，學(xué)習(xí)要以學(xué)習(xí)者為中心。五、常用算法

比較沉淀（起泡）選擇五、常用算法21算法的概念與程序設(shè)計(jì)劉啟明算法的概念與程序設(shè)計(jì)劉啟明22第4節(jié)算法的概念與程序設(shè)計(jì)

【本章提要】

針對(duì)部分模塊進(jìn)行討論，研究其教學(xué)內(nèi)容、教學(xué)處理要點(diǎn)和教學(xué)中應(yīng)注意的問題。第4節(jié)算法的概念與程序設(shè)計(jì)

【本章提要】23

一、算法二、算法與程序三、重要的循環(huán)算法和遞歸算法四、排序問題五、常用算法一、算法24一、算法1．算法：對(duì)特定問題的求解步驟。2．算法復(fù)雜度3．算法的特征：有窮性、確定性、可行性4．計(jì)算方法：對(duì)求數(shù)值解的近似方法的研究【注意事項(xiàng)】計(jì)算機(jī)求解的問題：有兩大類（數(shù)值和非數(shù)值）【例題】交換兩個(gè)變量的值一、算法1．算法：對(duì)特定問題的求解步驟。25算法atbba算法atbba26算法main(){ floata,b,t; scanf("%f,%f",&a,&b);if(a>b){t=a;a=b;b=t；}printf("%5.2f,%5.2f\n",a,b);}算法main()27二、算法與程序

【程序兩要素】瑞士科學(xué)家沃思（NiklausWirth)有一個(gè)著明的公式程序=算法(操作步驟)+數(shù)據(jù)結(jié)構(gòu)（原料）

【說明】高級(jí)語(yǔ)言的數(shù)據(jù)類型非常豐富，如：字符型、整型、實(shí)型、邏輯型等。

【數(shù)組的概念】一組相關(guān)數(shù)據(jù)的集合，它在內(nèi)存中開辟了若干個(gè)連續(xù)的存儲(chǔ)單元，依次存儲(chǔ)。二、算法與程序28算法與程序

算法表示：

(1)自然語(yǔ)言

(2)傳統(tǒng)流程圖

(3)N-S結(jié)構(gòu)圖：又稱納薩－施內(nèi)德曼圖（Nassi-Sschneiderman).

結(jié)構(gòu)化程序設(shè)計(jì)（三種基本結(jié)構(gòu)）

算法與程序算法表示：29【例題】求3個(gè)數(shù)中最小數(shù)

main(){inta,b,c,t;printf("請(qǐng)輸入三個(gè)整數(shù):");scanf(%d,%d,%d",&a,&b,&c);if(a>b){t=a;a=b;b=t;}if(a>c){t=a;a=c;c=t;}printf("三個(gè)整數(shù)中最大得是%d\n",a);}【例題】求3個(gè)數(shù)中最小數(shù)30a>bYN交換a>cYN交換a>dYN交換……i=1ton-1min>a[i]YN交換a>bYN交換a>cYN交換a>dYN交換……i31三、重要的循環(huán)算法和遞歸算法循環(huán)算法兩類具有代表性的算法（窮舉和迭代）循環(huán)控制的方法（計(jì)數(shù)＼標(biāo)志）例如：迭代算法的教學(xué)（二分法＼牛頓切線）掌握知識(shí)與培養(yǎng)能力的統(tǒng)一主體與客體的統(tǒng)一【教案】用牛頓迭代法求下面方程在1.5附近的根。三、重要的循環(huán)算法和遞歸算法循環(huán)算法掌握知識(shí)與培養(yǎng)能力的32典型的遞歸算法Hanoi（漢諾）塔問題：

古代有一個(gè)梵塔，塔內(nèi)有3個(gè)座A、B、C，開始時(shí)A座上有64個(gè)盤子，盤子大小不等，大的在下，小的在上。有一個(gè)老和尚想把這64個(gè)盤子從A盤移到C座，但每次只允許移動(dòng)一個(gè)盤子，且在移動(dòng)過程中在3個(gè)座上都始終大盤在下，小盤在上。在移動(dòng)過程中可以利用B座，要求編程序打印出移動(dòng)步驟。

算法的演示圖示如下所示：典型的遞歸算法Hanoi（漢諾）塔問題：33典型的遞歸算法ABC132典型的遞歸算法ABC13234四、排序問題例如：排序問題（n個(gè)元素排隊(duì)）

對(duì)數(shù)據(jù)進(jìn)行排序有哪些方法可以實(shí)現(xiàn)？

快速排序、冒泡排序、希爾排序、插入排序、歸并排序……采用冒泡排序方法對(duì)待排序的序列進(jìn)行排序。四、排序問題例如：排序問題（n個(gè)元素排隊(duì)）35

定義一個(gè)大小為6的數(shù)組a[6]a[1]a[2]a[3]a[4]a[5]a[6]初始965743一次后695743二次后659743三次后657943四次后657493五次后657439第一趟冒泡排序最大值注：經(jīng)過第一趟冒泡排序，我們找出了待排序序列中的最大值9，最大值9存放在了數(shù)組a的最后一個(gè)位置。定義一個(gè)大小為6的數(shù)組a[6]最大值注：經(jīng)過第一趟冒泡排序36

a[1]a[2]a[3]a[4]a[5]a[6]初始657439一次后567439二次后567439三次后564739四次后564379第二趟冒泡排序注：經(jīng)過第二趟冒泡排序后，我們找到了次大值7，次大值7存放在數(shù)組a的倒數(shù)第二個(gè)位置a[5]次大值最大值a[1]a[2]a37流程圖是用一些圖框表示各種操作。用圖形表示算法，直觀形象、易于理解。

N-S流程圖---全部的算法寫在一個(gè)矩形框內(nèi)，在框內(nèi)還可以包含其他的從屬于它的框，或者說，由一些基本的框組成一個(gè)大的框。這種流程圖又稱為N-S結(jié)構(gòu)化流程圖。據(jù)此在這里我們可畫出上述冒泡排序算法的N-S流程圖流程圖是用一些圖框表示各種操作。用圖形表示算法，直觀形象、易38描述算法

輸入n個(gè)數(shù)給a[1]到a[n]fori=1ton-1forj=1ton-ia[j]>a[j+1]真假a[j]<=>a[j+1]輸出a[1]到a[n]冒泡排序算法N-S流程圖描述算法39N-S圖描述算法依次對(duì)數(shù)據(jù)序列進(jìn)行冒泡排序：第三趟冒泡排序結(jié)果5-4-3-6-7-9第四趟冒泡排序結(jié)果4-3-5-6-7-9第五