1、信息技術(shù)（選修1）算法與程序設(shè)計(jì) 第一章第二節(jié),算法和算法的描述,計(jì)算機(jī)解決問題的過程,分析問題,設(shè)計(jì)算法,編寫程序,調(diào)試程序,學(xué)習(xí)、生活中的算法,過河游戲,問題如下：有一個(gè)牧羊人帶著一頭羊,一只狼和一顆大白菜準(zhǔn)備過河,他找到一只很小的船,每次只能帶一樣?xùn)|西過去,可是如果讓狼與羊單獨(dú)在一起,狼會吃羊,讓羊與白菜單獨(dú)在一起,羊會吃白菜，牧羊人應(yīng)如何過河？,結(jié)合過河游戲，思考并回答如下問題：,1、這個(gè)方案總共有多少步？,3、通過以上例子，我們能不能總結(jié)出什么是算法？,2、第二步和第三步可以改變先后順序，其它順序還能不能顛倒，比如說：第一步先過狼？,理解算法,過河方案： 第一步：人和羊過河，人返回，

2、留下羊； 第二步：人和狼過河，人和羊返回，留下狼； 第三步：人和菜過河，人返回，留下菜； 第四步：人和羊過河。,算法的概念,通俗地說：算法就是用計(jì)算機(jī)解決某一問題的步驟和方法，是能被機(jī)械地執(zhí)行的動作或指令的有窮集合。,現(xiàn)實(shí)生活中的算法,用銀行自動取款機(jī)取款算法1插入銀行卡2輸入密碼后按確定 3若密碼不正確，返回23選擇取款項(xiàng) 4輸入金額后按確定 5將錢取出 6取回銀行卡,超市，收銀員操作的算法1拿起顧客的挑選食品2用掃描器把條形碼掃描進(jìn)計(jì)算機(jī)3若一個(gè)顧客的商品位掃描完繼續(xù)第2步 4計(jì)算機(jī)處理數(shù)據(jù)：單價(jià)、數(shù)量、總價(jià)5計(jì)算機(jī)打印給顧客總花費(fèi)6顧客付錢營業(yè)員收錢找錢,算法的特征,設(shè)給定的兩個(gè)正整數(shù)m

3、=112和n=64，利用輾轉(zhuǎn)相除法，求它們的最大公約數(shù)。,我們已經(jīng)了解了算法的概念，接下來我們一起研究一下算法具備什么樣的特征，以歐幾里得算法為例，我們思考并歸納出算法特征：,算法如下： （1）112除以64，余數(shù)為； （2）除以，余數(shù)為； （3）除以，余數(shù)為。 答：112和64的最大公約數(shù)為。,算法的特征,輸入,有窮性,確定性,能行性,輸出,輸入兩個(gè)整數(shù)m和n（一個(gè)算法有零個(gè)或多個(gè)輸入）,輸出兩個(gè)數(shù)的最大公約數(shù)（算法有一個(gè)或多個(gè)輸出）,有限個(gè)步驟之后完成最大公約數(shù)的計(jì)算,步驟（1）中明確規(guī)定“m除以n”，而不能有類似“m除以n或n除以m”有兩種可能的做法。,算法的每個(gè)步驟都必須是基本的、能精

4、確進(jìn)行的。,一個(gè)算法應(yīng)該具有以下五個(gè)方面的重要特征：,算法的描述：請用自然語言描述歐幾里得算法,2、若r=0,則輸出結(jié)果n,算法結(jié)束；否則，繼 續(xù)步驟（3）。,3、令m=n，n=r，并返回步驟（1）繼續(xù)進(jìn)行。,1、以除以，令所得的余數(shù)為。,這種描述方法通俗易懂，但有其局限性：語句一般很長、容易造成歧義、復(fù)雜算法比較難清晰表示出來，也不方便翻譯成計(jì)算機(jī)可以直接執(zhí)行的程序設(shè)計(jì)語言。,請問還有其他描述算法的方法嗎？有沒有更加清晰簡潔的描述方式嗎？,自然語言描述算法的優(yōu)缺點(diǎn),開始,r=0,輸入正整數(shù)m和n,m=n，n=r,輸出n的值,結(jié)束,用流程圖描述歐幾里得算法,r = m除以n的余數(shù),是,否,用流

5、程圖描述的算法清晰簡潔，容易表達(dá)復(fù)雜的算法，有利于轉(zhuǎn)化成不同的程序設(shè)計(jì)語言,用流程圖描述算法的優(yōu)點(diǎn),流程圖基本圖形及其功能,用偽代碼描述算法,用自然語言描述算法，通俗易懂，但有其局限性：容易造成歧義、 語句一般很長、復(fù)雜算法比較難清晰表示出來，也不方便翻譯成 程序設(shè)計(jì)語言,用流程圖描述的算法清晰簡潔，容易表達(dá)復(fù)雜的算法，有利于轉(zhuǎn)化成不同的程序設(shè)計(jì)語言,我們設(shè)計(jì)算法，目的是讓計(jì)算機(jī)去處理數(shù)據(jù)，最終將計(jì)算的結(jié)果呈現(xiàn)給我們，為了更為方便地向程序設(shè)計(jì)語言過渡，人們也經(jīng)常用偽代碼描述算法：,INPUT m，n R=m mod n DO while r0 m=r n=r r=m mod n Loop PR

6、INT n,描述算法的一些方法,自然語言,流程圖,偽代碼,NS框圖,PAD圖,以上形式描述的算法，都不能直接被計(jì)算機(jī)執(zhí)行，最終都要轉(zhuǎn)化成計(jì)算機(jī)程序讓計(jì)算機(jī)去執(zhí)行。,由求最大公約數(shù)問題、過河問題我們可以得知，一個(gè)問題，可能有多種算法 ，應(yīng)該通過分析、比較、挑選一種最優(yōu)的算法。一個(gè)好算法必須用到科學(xué)的方法 ，應(yīng)該好好學(xué)習(xí)各學(xué)科處理問題的科學(xué)方法。,算法的擇優(yōu),問題一：著名數(shù)學(xué)家華羅庚“燒水泡茶”的兩個(gè)算法。 算法一 第一步：燒水； 第二步：水燒開后，洗刷茶具； 第三步：沏茶。 算法二 第一步：燒水； 第二步：燒水過程中，洗刷茶具； 第三步：水燒開后沏茶。 問題二： 模仿第一節(jié)中調(diào)試程序的操作，運(yùn)行P13探究（求兩個(gè)整數(shù)9147485和5147480的最大公約數(shù)）兩個(gè)程序，比較它們的效率，把觀察到的現(xiàn)象填在表1-6中。,算法的擇優(yōu),小結(jié),算法的概念,算法的特征,算法的描述,算法就是解決某一問題的步驟和方法,輸入、輸出、確定性、有窮性、可行性,自然語言、流程圖、偽代碼等,下節(jié)課我們將開始學(xué)習(xí)用程序設(shè)計(jì)語言實(shí)現(xiàn)自己的算法，讓計(jì)算機(jī)幫我們解決現(xiàn)實(shí)生活中的難題,課后討論,李汝珍筆上鏡花緣中有這么一個(gè)故事：有一位才女叫米蘭芬，有一天她和眾姐妹在宗伯府聚會，來到小鰲山樓上觀燈。樓下的燈有兩