算法描述與設(shè)計課件

1、算法描述與設(shè)計,（選修）,幫助這個人用船把狼、羊和一箱菜運送到河對面,但是有苛刻的附加條件：(1)船一次只能運一樣;(2)當人不在時，狼會吃羊，羊會吃菜。,第一步:運羊過河,回來 第二步:運菜過河,并運羊回來 第三步:運狼過河,回來 第四步:運羊過河,將過河的方法描述出來:,一、算法的概念,解決問題的 方法和步驟,二、算法的特征,有窮性：執(zhí)行有限步之后結(jié)束，且每一 步的執(zhí)行時間也都是有限的 確定性：每一步都有確切的含義 輸 入：有零個或多個輸入 輸 出：至少產(chǎn)生一個輸出 可行性：原則上能精確運行，用紙和筆 做有限次運算后即可完成,三、算法的描述,1、用自然語言來描述。 2、用流程圖來描述。 3

2、、用偽代碼描述算法。,1、用自然語言來描述。,什么是自然語言？,人們?nèi)粘Ｉ钪惺褂玫恼Z言,第一步:運羊過河,回來 第二步:運菜過河,并運羊回來 第三步:運狼過河,回來 第四步:運羊過河,通俗易懂，但缺乏直觀性， 不簡潔，且易產(chǎn)生歧義。,想起來了。,那天發(fā)生的事情我終于想起來了。 小明躺了一天，想起來了。,咬死了獵人的狗 發(fā)現(xiàn)了敵人的哨兵 沒有買票的人 ,練習一：,已知變量x和y中分別存放了數(shù)據(jù)，現(xiàn)在要交換其中的數(shù)據(jù)。用自然語言描述算法。,算法描述,第1步：將x中的數(shù)據(jù)送給變量m，即 xm； 第2步：將y中的數(shù)據(jù)送給變量x，即 yx ； 第3步：將m中的數(shù)據(jù)送給變量y，即 my。,2、用流程圖來

3、描述,也稱程序框圖，它是算法的一種圖形化表示方法。,什么是流程圖？,直觀易懂、邏輯關(guān)系清晰， 不容易產(chǎn)生歧義。,組成流程圖的流程圖符號,開始或結(jié)束,輸入或輸出,處 理,判 斷,連 接 線,第一步:運羊過河,回來 第二步:運菜過河,并運 羊回來 第三步:運狼過河,回來 第四步:運羊過河,運羊過河,回來,運菜過河, 并運羊回來,運狼過河,回來,運羊過河,例：將過河的算法 用流程圖描述出來,練習二：,將交換兩個變量的算法用流程圖描述。,xm,yx,mx,例： 任意輸入一個實數(shù)到變量X，求下面函數(shù)的Y值：,Y=,X (X0),2X (X0),N,X大于0?,輸出Y,輸入一個實數(shù)到變量X,Y,判斷框只能有兩個出口,Y=x,Y=2x,X大于0?,Y,N,X等于0?,Y,N,輸入一個實數(shù)到變量X,Y=x,Y=0,Y=2X,輸出Y,分析流程圖,XY?,Y,N,輸入3個數(shù)到變量X,Y,Z,XC,YC,輸出C,ZC?,Y,N,ZC,3、用偽代碼來描述,偽代碼是介于自然語言和計算機語言之間的一種算法描述,在偽代碼描述中,關(guān)鍵詞一般用英文單詞.,什么是偽代碼？,簡單、易懂，容易修改，且容 易轉(zhuǎn)化為程序語言代碼。,例 ：用偽代碼描述求解分段函數(shù) 的算法,輸入實數(shù)到變量x IF x大于0 THEN y=x ELSE y=2x END IF 打印y,思 考,小 結(jié),一、算法