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

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

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

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

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

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

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

8、格，和讀寫頭符號，構成了整個系統(tǒng)的狀態(tài)。,一臺圖靈機是一個七元組(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 圖靈機的形式化定義,圖靈機的計算規(guī)則,根據(jù)圖靈機的形式化定義，圖靈機的計算規(guī)則如下：aa, x -> bb, y, D中aa是當前狀態(tài)，x是當前格子的值，bb是程序下一步的狀態(tài)，y是當前格的修改值，D是讀寫頭移動的方向(L為左移，R為右移，空則表示不移動)。具體規(guī)則由算法設計

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

11、 用加法圖靈機計算3+2,以1的個數(shù)表示數(shù)值，在紙帶上的數(shù)據(jù)是111A110 ，表示3+2。加法圖靈機的規(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ī)則時停機,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ī)則無定義，從而停機。計算結(jié)果為5,10 1 1 A 1 1 0,,,圖靈機就其計算能力而言，它能模擬任何現(xiàn)代的計算機。丘奇-圖靈論題也已經(jīng)得到計算機科學界的公認。圖靈機形式簡潔且功能強大，但是圖靈機形式化表示一個算法非常復雜。比如乘法需要近23條規(guī)則。由于計算機已經(jīng)發(fā)明出來，為了充分利用計算機的計算功能，因此通常用框圖（流程圖）、自然語言來表示算

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

14、計步驟的一種直觀工具。,,開始,結(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)框—用于解決需要反復進行的問題,,,例子：n=100i=1s=0while i<=n:s=s+ii=i+1print s,【問題4-1】用戶輸入一個三位自然數(shù)，讓計算機輸出佰位、十位和個位。,,,【問題4-2】由鍵盤輸入一個整數(shù)，如果是偶數(shù)則

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

17、（ANSI）于1983年為C語言制定了第一個ANSI標準，稱為ANSI C，簡稱標準C。C++、C#、Java語言這三種語言都是從C語言派生出來的，C語言的知識幾乎都適用于這三種語言。C?語言是一種通用的、程序結(jié)構化、面向過程的計算機程序設計語言。,問題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(微軟)公司旗下的一個主流程序開發(fā)工具 。1991年，微軟公司推出了 Visual Basic 1.0 。 Visual：“可視的”，一種直觀的圖形界面(GUI)設計方法。

19、 Basic指的是一種傳統(tǒng)的編程語言(Beginners All-Purpose Symbolic Instruction Code) 。Visual Basic是在原有BASIC語言基礎上的進一步發(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ū)ο?、直譯式計算機程序設計語言。Python可作腳本語言用于處理系統(tǒng)管理任務、進行Web編程等，一些大規(guī)模軟件開發(fā)計劃例如

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中進行計算2.

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

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

24、用知識,6.輸出數(shù)據(jù)print 如，print 's=', s7.導入模塊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) 請同學們猜一下輸出結(jié)果12.for循環(huán)語句