C語言程序設(shè)計教程 課件 第2章 算法初步

第2章算法初步理論知識算法概述12算法描述3算法設(shè)計方法4算法特性尼古拉斯·沃斯（NikiklasWirth）1.算法概述一個程序應(yīng)包括：（1）對數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu)（DataStructure）（2）對操作的描述。即操作步驟，也就是算法（Algorithm）算法：精確描述解決問題的方法步驟尼古拉斯·沃斯（NikiklasWirth）提出的公式：數(shù)據(jù)結(jié)構(gòu)+算法=程序教材認為：程序=算法+數(shù)據(jù)結(jié)構(gòu)+程序設(shè)計方法+語言工具環(huán)境1.算法概述C語言基本（典型）算法：

1.列(窮)舉法：百雞百錢

2.歸納法：斐波列契

3.遞推法猴子吃桃

4.遞歸法階乘

5.減半遞推法猜數(shù)字6.回溯法（試探法）樹的遍歷簡單算法舉例例1求1*2*3*4*5。最原始的方法：步驟1：先求1*2，得到結(jié)果2步驟2：將步驟1得到的乘積2乘以3，得到6步驟3：將6再乘以4，得24步驟4：將24再乘以5，得120.#include<stdio.h>voidmain(){ intsum; sum=1*2*3*4*5; printf("%d\n",sum);}#include<stdio.h>voidmain(){inti,sum;sum=1;i=2;while(i<=5){sum=sum*i;i=i+1;}printf("%d\n",sum);}改進的算法：S1:使t=1S2:使i=2S3:使t*i，乘積仍然放在變量t中，可表示為t*i→tS4：使i的值+1，即i+1→iS5：如果i<=5,返回重新執(zhí)行步驟S3以及其后的S4和S5；否則，算法結(jié)束。這樣的算法雖然正確，但太繁。2.算法的特性有窮性：一個算法應(yīng)包含有限的操作步驟而不能是無限的。確定性：算法中每一個步驟應(yīng)當是確定的，而不能應(yīng)當是含糊的、模棱兩可的。有零個或多個輸入。有一個或多個輸出。有效性：算法中每一個步驟應(yīng)當能有效地執(zhí)行，并得到確定的結(jié)果。時間復(fù)雜度空間復(fù)雜度3.算法描述-怎么表示一個算法自然語言：一般不用，除了很簡單的問題偽代碼：使用介于自然語言和計算機語言之間的文字和符號來描述算法偽代碼：現(xiàn)在的編程語言種類很多，偽代碼不是具體某一種編程語言的代碼，而是專用普遍的可以理解的方式寫出的代碼，寫這樣的代碼的目的是為了講解描述算法，而不是為了通過編譯得到可執(zhí)行程序。3.算法描述-怎么表示一個算法3.算法描述-怎么表示一個算法自然語言：一般不用，除了很簡單的問題偽代碼：使用介于自然語言和計算機語言之間的文字和符號來描述算法流程圖：直觀形象，易于理解程序流程圖又稱程序框圖，是用統(tǒng)一規(guī)定的標準符號描述程序運行具體步驟的圖形表示。程序框圖的設(shè)計是在處理流程圖的基礎(chǔ)上，通過對輸入輸出數(shù)據(jù)和處理過程的詳細分析，將計算機的主要運行步驟和內(nèi)容標識出來。流程圖實例1：求圓的面積流程圖實例2：求兩個數(shù)中的大數(shù)定義三個數(shù)值求最大流程圖實例3：求5！三種基本結(jié)構(gòu)的流程三種基本結(jié)構(gòu)的共同特點：（1）只有一個入口；（2）只有一個出口；（3）結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到；（4）結(jié)構(gòu)內(nèi)不存在“死循環(huán)”3.算法描述-怎么表示一個算法自然語言：一般不用，除了很簡單的問題偽代碼：使用介于自然語言和計算機語言之間的文字和符號來描述算法流程圖：直觀形象，易于理解N-S圖：1973年美國學(xué)者提出了一種新型流程圖3.算法描述-怎么表示一個算法自然語言：一般不用，除了很簡單的問題偽代碼：使用介于自然語言和計算機語言之間的文字和符號來描述算法流程圖：直觀形象，易于理解N-S圖：1973年美國學(xué)者提出了一種新型流程圖計算機語言：必需嚴格遵循所用語言的語法規(guī)則#include<stdio.h>voidmain(){inti,sum;sum=1;i=2;while(i<=5){sum=sum*i;i=i+1;}printf("%d\n",sum);}4.算法設(shè)計方法——結(jié)構(gòu)化程序設(shè)計方法自頂向下；逐步細化；模塊化設(shè)計；結(jié)構(gòu)化編碼。工作任務(wù)兩個變量互換12三個變量排序3三個變量求最大值4求圓面積

實踐知識任務(wù)1:兩個變量值互換/*案例1-1*/#include"stdio.h"voidmain(){ inta=5,b=3;a=3;b=5;

printf(“a=%d\nb=%d”,a,b);

}實踐知識任務(wù)1:兩個變量值互換/*案例1-1*/#include"stdio.h"voidmain(){ inta=5,b=3,t;t=a;a=b;b=t;

printf(“a=%d\nb=%d”,a,b);

}任務(wù)1:兩個變量值互換/*案例1-1*/#include"stdio.h"voidmain(){inta=5,b=3;a=a+b;

[填空1]

[填空2]

printf(“a=%d\nb=%d”,a,b);

}作答可為此題添加文本、圖片、公式等解析，且需將內(nèi)容全部放在本區(qū)域內(nèi)。b=a-b;a=a-b;答案解析答案解析填空題2分實踐知識

任務(wù)2:輸入半徑，計算圓的周長和面積。

實踐知識任務(wù)2:計算圓面積和周長

/*案例2-1*/#include"stdio.h"#definePI3.1416//注意：不是語句，行末沒有分號voidmain(){ floatradius，area,circumf; radius=6.0; area=PI*radius*radius;circumf=2*PI*radius; printf(“半徑為%f的圓的面積為：%f\n”,radius,area);printf("半徑為%f的圓的周長為：%f\n",radius,circumf);}實踐知識任務(wù)3:輸入三個數(shù)，按從小到大輸出/*案例3*/？實踐