西南林業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院

1、西南林業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院,大學(xué)計(jì)算機(jī)基礎(chǔ)與計(jì)算思維,第四章 算法與程序設(shè)計(jì)基礎(chǔ)本章作者：趙家剛、林宏,本章主要內(nèi)容,4.1 可計(jì)算問題 4.2 圖靈機(jī)4.3 解決問題的一般方法4.4 用框圖表示解決問題的算法 4.5 常用語言簡介4.6 Python程序設(shè)計(jì)初步附錄 Python常用知識,4.1 可計(jì)算問題,,算法的概念:算法(Algorithm)是求解特定問題的步驟。算法的五個(gè)重要特性：(1)有窮性

2、 一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成。(2)確定性 算法中每個(gè)步驟必須有確切的含義，讀者理解不會產(chǎn)生二義性。(3)可行性 一個(gè)算法是能行的，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。(4)輸入 一個(gè)算法有0個(gè)或多個(gè)輸入。(5)輸出 一個(gè)算法有一個(gè)或多個(gè)輸出。,4.1 可計(jì)算問題,,算法的設(shè)計(jì)要求:(1)正確性 算法應(yīng)當(dāng)滿足具體問題的需求

3、。對正確的輸入應(yīng)有正確的輸出。(2)可讀性 算法應(yīng)當(dāng)盡可能設(shè)計(jì)得易讀易懂，以便以進(jìn)行閱讀和修改。(3)鍵壯性 當(dāng)輸入數(shù)據(jù)非法時(shí)，算法也能適當(dāng)?shù)刈鞒龇磻?yīng)或處理，而不會意外停止或輸出錯(cuò)誤結(jié)果。(4)高效率 設(shè)計(jì)算法時(shí)應(yīng)考慮使算法的執(zhí)行時(shí)間盡可能短。(5)低存儲量 設(shè)計(jì)算法時(shí)應(yīng)考慮使算法占用的存儲空間盡可能少。,4.1 可計(jì)算問題,,計(jì)算的可行性是算法設(shè)計(jì)與分析的基礎(chǔ)，也是計(jì)算機(jī)科學(xué)的理論基礎(chǔ)。為了回答什么

4、是計(jì)算，什么是可計(jì)算性等問題，許多科學(xué)家提出了計(jì)算模型。 K.哥德爾 S.C.克林尼提出了遞歸函數(shù)。 A.M.圖靈和E.波斯特各自獨(dú)立地提出了抽象計(jì)算機(jī)的概念（后人把圖靈提出的抽象計(jì)算機(jī)稱為圖靈機(jī)）。 胡海星和宋方敏提出了算盤機(jī)。 理論上已經(jīng)證明，遞歸函數(shù)、 圖靈機(jī)、算盤機(jī)具有相同的計(jì)算能力。,可計(jì)算問題： 能夠在上述任何一種數(shù)學(xué)模型上編出算法(有限步驟)進(jìn)行計(jì)算的問題稱為可計(jì)算問題，否則就是不可計(jì)算

5、問題。 丘奇-圖靈論題: 能夠在抽象計(jì)算機(jī)上編出算法(有限步驟)進(jìn)行計(jì)算的問題稱為可計(jì)算問題，否則就是不可計(jì)算問題。 該論題是一個(gè)經(jīng)驗(yàn)結(jié)論，未經(jīng)證明。已得到計(jì)算科學(xué)界的公認(rèn)。,4.1 可計(jì)算問題,英國數(shù)學(xué)家圖靈于1936年發(fā)表《論可計(jì)算數(shù)及其在判定問題中的應(yīng)用》一文，文中提出了一種十分簡單而運(yùn)算能力極強(qiáng)的理想計(jì)算裝置———圖靈機(jī)的概念，推進(jìn)了計(jì)算機(jī)理論的發(fā)展。圖靈機(jī)的基本思想就是用機(jī)器來模擬人們用紙和筆進(jìn)行數(shù)學(xué)運(yùn)

6、算的過程，他把這樣的過程看作是兩種簡單的動作，即在紙上寫上或擦除某個(gè)符號；把注意力從紙的一個(gè)位置移動到另一個(gè)位置。,4.2 圖靈機(jī),圖靈機(jī)在理論上能夠模擬現(xiàn)代數(shù)字計(jì)算機(jī)的一切運(yùn)算，可視為現(xiàn)代數(shù)字計(jì)算機(jī)的數(shù)學(xué)模型，是一種抽象的計(jì)算模型。實(shí)際上，一切“可計(jì)算”函數(shù)都等價(jià)于圖靈機(jī)可計(jì)算函數(shù)，而圖靈機(jī)可計(jì)算函數(shù)類又等價(jià)于一般遞歸函數(shù)類。圖靈機(jī)能表示算法、程序和符號行的變換，因而可作為電子計(jì)算器的數(shù)學(xué)模型。,圖靈(Turing),圖靈機(jī)(Turi

7、ng Machine)的藝術(shù)表示,4.2.1 圖靈機(jī)的圖形表示,圖靈機(jī)由以下幾個(gè)部分組成：（1）一條無限長的紙帶TAPE。（2）一個(gè)讀寫頭HEAD。（3）一套控制規(guī)則TABLE。（4）一個(gè)狀態(tài)寄存器。圖靈認(rèn)為這樣的一臺機(jī)器就能模擬人類所能進(jìn)行的任何計(jì)算過程。,圖靈機(jī)模型,讀寫頭沿著固定的紙帶移動。要進(jìn)行的指令（q1）存儲在讀寫頭內(nèi)。圖中“空白”的紙帶全部填入0。有陰影的方格，包括讀寫頭掃描到的空白，標(biāo)記了1,1,B的那些方

8、格，和讀寫頭符號，構(gòu)成了整個(gè)系統(tǒng)的狀態(tài)。,一臺圖靈機(jī)是一個(gè)七元組(Q, ?,?,?,q0,qaccept, qreject)，其中Q，?，?都是有限集合，且滿足： （1）Q是狀態(tài)集合； （2）?是輸入字母表，其中不包含特殊的空白符?； （3）?是帶字母表，其中??? 且???；（4）?：Q?? -> Q???{L,R}是轉(zhuǎn)移函數(shù)，其中L，R表示讀寫頭是向左移還是向右移； （5）q0?Q是起

9、始狀態(tài)； （6）qaccept?Q是接受狀態(tài)； （7）qreject?Q是拒絕狀態(tài)，且qaccept ?qreject。,4.2.2 圖靈機(jī)的形式化定義,圖靈機(jī)的計(jì)算規(guī)則,根據(jù)圖靈機(jī)的形式化定義，圖靈機(jī)的計(jì)算規(guī)則如下：aa, x -> bb, y, D中aa是當(dāng)前狀態(tài)，x是當(dāng)前格子的值，bb是程序下一步的狀態(tài)，y是當(dāng)前格的修改值，D是讀寫頭移動的方向(L為左移，R為右移，空則表示不移動)。具體規(guī)則由算法設(shè)計(jì)

10、者根據(jù)計(jì)算需要而定義。如 :0，0->1，0，R請同學(xué)們猜一下該規(guī)則的意思。,加法圖靈機(jī),根據(jù)圖靈機(jī)的計(jì)算規(guī)則，人們設(shè)計(jì)了不同的圖靈機(jī)來完成不同的計(jì)算。如加法圖靈機(jī)、乘法圖靈機(jī)、除法圖靈機(jī)等。加法圖靈機(jī)的規(guī)則如下: (簡化版)0 , 0->1 , 0, R0 , 1->0 , 01 , A->10 , 1, 1 , 1 ->1 ,1, R遇到未定義的規(guī)則時(shí)停機(jī)，紙帶上的內(nèi)容就是計(jì)算結(jié)果。,例

11、 用加法圖靈機(jī)計(jì)算3+2,以1的個(gè)數(shù)表示數(shù)值，在紙帶上的數(shù)據(jù)是111A110 ，表示3+2。加法圖靈機(jī)的規(guī)則如下：(1) 0 , 1->0 , 0 (2) 0 , 0->1 , 0, R (3) 1 , A->10,1 (4) 1 , 1->1 ,1, R (5) 遇到無定義規(guī)則時(shí)停機(jī),10 1 1 A 1 1 0,,01 1 1 A 1 1 0,,10 1 1 A 1 1 0,100 1

12、 1 1 1 1 0,,00 1 1 A 1 1 0,,,狀態(tài)10,讀到的值為1的規(guī)則無定義，從而停機(jī)。計(jì)算結(jié)果為5,10 1 1 A 1 1 0,,,圖靈機(jī)就其計(jì)算能力而言，它能模擬任何現(xiàn)代的計(jì)算機(jī)。丘奇-圖靈論題也已經(jīng)得到計(jì)算機(jī)科學(xué)界的公認(rèn)。圖靈機(jī)形式簡潔且功能強(qiáng)大，但是圖靈機(jī)形式化表示一個(gè)算法非常復(fù)雜。比如乘法需要近23條規(guī)則。由于計(jì)算機(jī)已經(jīng)發(fā)明出來，為了充分利用計(jì)算機(jī)的計(jì)算功能，因此通常用框圖（流程圖）、自然語言來表示算

13、法。,4.3 解決問題的一般方法,,用計(jì)算機(jī)可以解決兩類問題：(1)數(shù)值計(jì)算問題,抽象出數(shù)學(xué)模型,,設(shè)計(jì)算法,編程,測試,修改,,,,(2)非數(shù)值計(jì)算問題通常要用到一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu),4.3 解決問題的一般方法,用計(jì)算機(jī)解決問題的一般方法：(1)描繪出解決問題的步驟 自然語言 、框圖 等(2)用程序設(shè)計(jì)語言實(shí)現(xiàn)上述步驟,4.4 用框圖表示解決問題的算法,框圖又稱流程圖，是表達(dá)程序設(shè)計(jì)思想和程序設(shè)

14、計(jì)步驟的一種直觀工具。,,開始,結(jié)束,,流程線,4.4 用框圖表示解決問題的算法,功能框,例子1：x=1y=3*x例子2:x=0.5y=math.sin(x),輸入框,用于向程序輸入數(shù)據(jù)例子：x=input('x='),用于向程序輸出數(shù)據(jù)例子：print s,輸出框,4.4 用框圖表示解決問題的算法,單分支判斷框—用于解決單分支問題,例子：if x>0:n=n+1,False,4.4 用框

15、圖表示解決問題的算法,,,雙分支判斷框—用于解決雙分支問題,例子：if x>0:y=1+2*xelse:y=x**2,4.4 用框圖表示解決問題的算法,循環(huán)框—用于解決需要反復(fù)進(jìn)行的問題,,,例子：n=100i=1s=0while i<=n:s=s+ii=i+1print s,【問題4-1】用戶輸入一個(gè)三位自然數(shù)，讓計(jì)算機(jī)輸出佰位、十位和個(gè)位。,,,【問題4-2】由鍵盤輸入一個(gè)整數(shù)，如果是偶數(shù)則

16、輸出“偶數(shù)”，如果是奇數(shù)是輸出“奇數(shù)”。,,,【問題4-3】 編程計(jì)算1+2+3+…+n 的值，n由鍵盤輸入。,,,4.5 常用語言簡介,,如果需要把用框圖、自然語言表示的算法在計(jì)算機(jī)上執(zhí)行，還需要用某種計(jì)算機(jī)語言表示出來。算法是程序的靈魂，語言是靈魂的表示。計(jì)算機(jī)語言是人與計(jì)算機(jī)溝通的橋梁。,4.5.1 C語言,C語言于?1972?年由Dennis Ritchie在貝爾電話實(shí)驗(yàn)室實(shí)現(xiàn)Unix操作系統(tǒng)時(shí)開發(fā)。美國國家標(biāo)準(zhǔn)協(xié)會

17、（ANSI）于1983年為C語言制定了第一個(gè)ANSI標(biāo)準(zhǔn)，稱為ANSI C，簡稱標(biāo)準(zhǔn)C。C++、C#、Java語言這三種語言都是從C語言派生出來的，C語言的知識幾乎都適用于這三種語言。C?語言是一種通用的、程序結(jié)構(gòu)化、面向過程的計(jì)算機(jī)程序設(shè)計(jì)語言。,問題1 用C語言程序?qū)崿F(xiàn)1+2+……+100的值。,#includevoid main(){int i,sum;sum=0;for(i=1;i<=100;i

18、++){sum=sum+i; } printf("1+2+……+100=%d",sum); },4.5.2 VB語言,Visual Basic（以下簡稱VB）是美國Microsoft(微軟)公司旗下的一個(gè)主流程序開發(fā)工具 。1991年，微軟公司推出了 Visual Basic 1.0 。 Visual：“可視的”，一種直觀的圖形界面(GUI)設(shè)計(jì)方法。

19、 Basic指的是一種傳統(tǒng)的編程語言(Beginners All-Purpose Symbolic Instruction Code) 。Visual Basic是在原有BASIC語言基礎(chǔ)上的進(jìn)一步發(fā)展。,問題2 用VB語言程序?qū)崿F(xiàn)1+2+……+100的值。,Private Sub Command1_Click()Dim i As IntegerDim sum As Integersum = 0For i = 1 T

20、o 100 Step 1 sum = sum + iNext iPrint "1+2+……+100=", sumEnd Sub,4.5.3 Python語言,Python由吉多·范羅蘇姆（Guido van Rossum）于1989年未開發(fā)。Python是一種面向?qū)ο?、直譯式計(jì)算機(jī)程序設(shè)計(jì)語言。Python可作腳本語言用于處理系統(tǒng)管理任務(wù)、進(jìn)行Web編程等，一些大規(guī)模軟件開發(fā)計(jì)劃例如

21、Zope、Mnet及BitTorrent，Google也廣泛地使用它 。注：本書使用Python 2.7,#Ques4_3pyi, s = 1, 0n=input('n=')while i <= n :s = s + ii += 1print '1+2+3+...+ ', n, '= ', s,問題4-3的Python語言程序,1.在Idle中進(jìn)行計(jì)算2.

22、編寫并執(zhí)行Python程序參考大基實(shí)驗(yàn)6,4.6 Python程序設(shè)計(jì)初步,上機(jī)安排,完成大基實(shí)驗(yàn)3,課 后 作 業(yè),習(xí)題4.7 之2，3 畫出框圖,附錄：Python常用知識,1.運(yùn)算符 算術(shù)運(yùn)算符： +,-,*,/ ,** 加，減，乘，除, 乘方 // 求整商 % 求余數(shù) 關(guān)系運(yùn)算符： >,=,<=, ==,!= 大于，小于，大于等于，小于等于，等

23、于，不等 邏輯運(yùn)算符： and, or, not 與，或，非 成員測試： in , not in,Python的常用知識,2.賦值 y=33.表達(dá)式計(jì)算 a=3 b=5 s=a*b q=s**(1.0/2)4.輸入實(shí)數(shù) s=input('s=')5.輸入字符串 x=raw_input('x='),Python的常

24、用知識,6.輸出數(shù)據(jù)print 如，print 's=', s7.導(dǎo)入模塊import 如，import math8.單分支判斷語句if 如： if x<0:y=-x,Python的常用知識,9.雙分支判斷語句if-else 如： if x>0:y=-x else:y=x,Python的常用知識,10.while循環(huán)語句

25、 如： t=1 i=1 n=10 while i<=nt=t*ii=i+1 print 't=',t,Python的常用知識,11.列表的使用 a=[1, 2, 8, 5, 9] a[2]=-4 x=a[0]+a[2] print(x) 請同學(xué)們猜一下輸出結(jié)果12.for循環(huán)語句