算法及其實(shí)現(xiàn) 詳細(xì)版課件

1、高中信息技術(shù)基礎(chǔ)（必修）算法及其實(shí)現(xiàn)農(nóng)夫過河 一個(gè)農(nóng)夫帶著一條狼、一頭山羊和一籃蔬菜要過河，但只有一條船。乘船時(shí)，農(nóng)夫只能帶一樣?xùn)|西。農(nóng)夫在場(chǎng)的時(shí)候，這三樣?xùn)|西相安無事。一旦農(nóng)夫不在，狼會(huì)吃羊，羊會(huì)吃菜。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，使農(nóng)夫能安全的將這三樣?xùn)|西帶過河。農(nóng)夫帶狼、山羊、蔬菜過河步驟解一：1、農(nóng)夫帶羊過河2、農(nóng)夫回來3、把狼帶過河4、把羊帶回來5、帶蔬菜過河6、農(nóng)夫回來7、把羊帶過河解二：1、農(nóng)夫帶羊過河2、農(nóng)夫回來3、帶蔬菜過河4、把羊帶回來5、把狼帶過河6、農(nóng)夫回來7、把羊帶過河算法的定義： 所謂“算法”（algorithm）就是解題方法的精確描述。算法的特點(diǎn): 算法的特點(diǎn)是求解步驟必須是有

2、限的,而且每個(gè)環(huán)節(jié)都必須是明確和可行的。 問：如何判斷一個(gè)算法的好壞？ 數(shù)學(xué)家華羅庚的統(tǒng)籌方法中著名的”泡茶算法” ：灌涼水洗茶壺拿茶葉泡茶喝洗茶杯洗開水壺?zé)_水灌涼水洗茶壺拿茶葉泡茶喝洗茶杯洗開水壺?zé)_水灌涼水洗茶壺拿茶葉泡茶喝洗茶杯洗開水壺?zé)_水方法甲方法丙方法乙t(請(qǐng)同學(xué)們對(duì)這幾種算法進(jìn)行評(píng)價(jià)!)算法的表示： 為了表示一個(gè)算法，常用的算法表示形式有：自然語言、流程圖和計(jì)算機(jī)語言。 常用的計(jì)算機(jī)語言有： C 、 C+ 、 Basic 、 VB 和java等。自然語言表示法 自然語言就是人們?nèi)粘Ｊ褂玫恼Z言,可以是漢語、英語或數(shù)學(xué)語言等.用自然語言描述算法的優(yōu)點(diǎn)是通俗易懂,當(dāng)算法中的操作步驟都

3、是順序執(zhí)行時(shí)比較容易理解.缺點(diǎn)是通常所用文字會(huì)比較冗長(zhǎng)，還容易出現(xiàn)“歧義性”.流程圖是人們經(jīng)常用來描述算法的工具，流程圖用圖框及流程線來表示算法形象直觀。美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)（ANSI）規(guī)定了流程圖符號(hào)。1.處理框（ ）：框中指出要處理的內(nèi)容，有出口和入口。2.輸入、輸出框（ ）：表示輸入和輸出數(shù)據(jù)。3.判斷框（ ）：表示條件判斷及產(chǎn)生分支的情況。4.連接框（ ）：連接因頁面寫不下而斷開的流程線。5.流程線（ ）：有向線段，控制流程方向。6.開始、結(jié)束框（ ）：表示本段算法的開始或結(jié)束。例1：要設(shè)計(jì)一個(gè)算法，對(duì)任意輸入的三個(gè)整數(shù)x、y和z，找出并輸出其中的最大值。按照它的思想，我們只需要先比較x

4、和y，得到一個(gè)較大的值max，再用max與y比較，將兩者中較大的值作為結(jié)果輸出即可。用自然語言，可以將這個(gè)算法描述為：（1）輸入變量x、y和z的值。（2）比較x和y。如果xy，則x存入以max命名的存儲(chǔ)單元中；否則，y送max。（3）比較z和max。如果zmax，則z送max。（4）輸出結(jié)果max。 這個(gè)算法也可以用下面的流程圖來描述。圖中的Y表示Yes，N表示No。開始輸入變量x、y和z的值x yz maxmax xmax ymax z輸出變量max的值結(jié)束圖框內(nèi)的符號(hào)“”是賦值號(hào)，表示將賦值號(hào)右邊的表達(dá)式運(yùn)算的結(jié)果值存入左邊的變量。例如，“max x”、i i+1YN練習(xí)1:畫出“我們走路時(shí)躲避障礙”這個(gè)過程的流程圖YN有障礙嗎?往前直走開始結(jié)束躲避障礙觀察道路情況開始輸入變量n的值輸出變量f的值結(jié)束i n？Nf 1i 1f f*ii i+1Y 程序設(shè)計(jì)實(shí)例例2：求n階乘（n!=123n） 首先輸入變量n的值，變量f和i被賦以初值1，然后判斷in是否成立，如果成立，執(zhí)行賦值語句ff*i和i i+1，并回到判斷處，否則結(jié)束循環(huán)，最后輸出f的值。練習(xí)2在抽屜中尋找