3.2算法及其描述課件

3.2算法及其描述假設(shè)要喝一杯茶有以下幾個步驟：a.燒水b.洗刷水壺c.找茶葉d.洗刷茶具e.沏茶請問你怎樣安排？導入一燒水泡茶問題：解：燒水泡茶可分下面四步完成：第一步：洗好開水壺；第二步：灌好涼水，放在火上，等待水開；第三步：等待時洗好茶杯，茶杯里放好茶葉；第四步：水開后再沖水泡茶。一個農(nóng)夫帶著一條狼、一頭山羊和一籃蔬菜要過河,但只有一條小船.乘船時,農(nóng)夫只能帶一樣東西.當農(nóng)夫在場的時候,這三樣東西相安無事.一旦農(nóng)夫不在,狼會吃羊,羊會吃菜.請設(shè)計一個算法,使農(nóng)夫能安全地將這三樣東西帶過河.第一步:農(nóng)夫帶羊過河;第二步:農(nóng)夫獨自回來;第三步:農(nóng)夫帶狼過河;第四步:農(nóng)夫帶羊回來;第五步:農(nóng)夫帶蔬菜過河;第六步:農(nóng)夫獨自回來;第七步:農(nóng)夫帶羊過河.計算機解決問題的步驟分析問題——可采用建立數(shù)學模型的方式使問題變得更明確、易理解。設(shè)計算法——數(shù)學模型確定了應(yīng)該“做什么”，接下來就要為它尋找一個“如何做”的算法。編寫程序——用一種計算機能接受的程序設(shè)計語言來描述問題求解的算法。調(diào)試程序——查找和改正程序中存在的錯誤，使程序能順利地執(zhí)行，得出正確結(jié)果。華南太陽能設(shè)備廠在計劃期內(nèi)擬生產(chǎn)甲乙丙三種產(chǎn)品，每件銷售收入分別為4萬，3萬，2萬。按工藝規(guī)定，甲乙丙三種產(chǎn)品都需要在A、B、C、D四種不同設(shè)備上加工，已知 A、B、C、D四種設(shè)備在計劃期內(nèi)有效使用臺數(shù)分別為12、8、16、12。如何安排生產(chǎn)可使收入最大?

設(shè)備產(chǎn)品ABCD甲2140乙2204丙1100設(shè):甲，乙，丙三種產(chǎn)量分別為x,y,z臺。根據(jù)題意列出如下關(guān)系式。

2X+2Y+Z≤12X+2Y+Z≤84X≤164Y≤12根據(jù)不等式x,y,z是整數(shù)滿足：0≤x≤4,0≤y≤3,0≤z≤8.可以用窮舉的方法在許可的范圍內(nèi)找到合適（就是滿足不等式組）的x,y,z.求F(x,y,z)=4X+3Y+2Z的值，然后再所有f(x,y,z)函數(shù)中找出最大的值'把滿足不等式組x、y、z代入f(x,y,z)=4x+3y＋2z中求值Forx=0To4Fory=0To3Forz=0To8If

(2*x+2*y+z<=12)And(x+2*y+z<=8)

Then

f(x,y,z)=4*x+3*y+2*z

Else

f(x,y,z)=0EndIfNextzNextyNextx'在所有的f(x,y,z)中，找出最大值f_max=0Forx=0To4Fory=0To3Forz=0To8Iff_max<f(x,y,z)Then

f_max=f(x,y,z)x_max=xy_max=yz_max=zEndIfNextzNextyNextx

在數(shù)學中，算法通常是指按照一定規(guī)則解決某一類問題的明確和有限的步驟?，F(xiàn)在，算法通?？梢跃幊捎嬎銠C程序，讓計算機執(zhí)行并解決問題。1.算法的概念講授新課算法計算機中算法概念：計算機求解某一問題的方法，是能被機械的執(zhí)行的指令的有窮集合。實踐兩個整數(shù)m=112和n=64，利用輾轉(zhuǎn)相除法，求它們的最大公約數(shù)1、112除以64，余數(shù)為2、除以余數(shù)為3、除以余數(shù)為4、112和64的最大公約數(shù)為486448164816016二、算法的特征有窮性：執(zhí)行有限步之后結(jié)束，且每一

步的執(zhí)行時間也都是有限的確定性：每一步都有確切的含義輸入：有零個或多個輸入輸出：至少產(chǎn)生一個輸出可行性：原則上能精確運行，用紙和筆

做有限次運算后即可完成三算法的描述1、用自然語言來描述。2、用流程圖來描述。3、用偽代碼描述算法。1、用自然語言來描述。什么是自然語言？人們?nèi)粘Ｉ钪惺褂玫恼Z言

第一步:運羊過河,回來第二步:運菜過河,并運羊回來第三步:運狼過河,回來第四步:運羊過河

通俗易懂，但缺乏直觀性，不簡潔，且易產(chǎn)生歧義。例題：有兩個杯子A和B，分別盛有果汁和酒，要求將這兩個杯子進行互換。根據(jù)常識，必須增加一個空杯C作為過渡。其算法表示步驟1：先將A杯中的果汁倒在C杯中；步驟2：再講B杯中的酒倒在A杯中；步驟3：最后將C杯中的果汁倒在B杯中

一個籠子里有雞和兔，現(xiàn)在只知道里面一共有35個頭，94只腳，問雞和兔各有多少只？

X+Y=a2X+4Y=b解方程組得：X＝2a-b/2，Y＝b/2-a雞兔同籠問題設(shè)計算法輸入a和b的值求X=2a-b/2求Y=b/2-a輸出X，Y的值結(jié)束自然語言的優(yōu)點：通俗易懂。缺點：容易產(chǎn)生歧義。例如：“這個人連老張也不認識”。

意思之一：這個人不認識老張。意思之二：老張不認識這個人。

2、用流程圖來描述

也稱程序框圖，它是算法的一種圖形化表示方法。什么是流程圖？

直觀易懂、邏輯關(guān)系清晰，不容易產(chǎn)生歧義。流程圖

圖形名稱功能開始／結(jié)束表示算法的開始或結(jié)束輸入／輸出表示算法中變量的輸入或輸出處理表示算法中變量的計算與賦值判斷表示算法中的條件判斷流程線表示算法中的流向連接點表示算法中的轉(zhuǎn)接第一步:運羊過河,回來第二步:運菜過河,并運羊回來第三步:運狼過河,回來第四步:運羊過河開始結(jié)束運羊過河,回來

運菜過河,

并運羊回來運狼過河,回來運羊過河例：將過河的算法用流程圖描述出來韓信點兵我國漢代有一位大將，名叫韓信。劉邦去一次去查看部隊，問韓信部隊的人數(shù)，韓信說，如果3個3個的數(shù)，最后剩2個；如果5個5個的數(shù)，最后剩3個；如果7個7個的數(shù)，最后剩2個。最少有多少人？這樣可把劉邦給難住了。他的這種巧妙算法，人們稱為“鬼谷算”、“隔墻算”、“秦王暗點兵”等。算法描述：以“韓信點兵問題”

為例：算法分析：以“韓信點兵問題”

為例：數(shù)學家程大位把這個問題的算法編成了四句歌訣：三人同行七十稀，五樹梅花廿一枝；七子團圓正半月，除百零五便得知一個數(shù)用3除，除得的余數(shù)乘70；用5除，除得的余數(shù)乘21；用7除，除得的余數(shù)乘15。最后把這些乘積加起來再減去105的倍數(shù)，就知道這個數(shù)是多少。

被5、7整除，而被3除余1的最小正整數(shù)是70；被3、7整除，而被5除余1的最小正整數(shù)是21；被3、5整除，而被7除余1的最小正整數(shù)是15

所以，這三個數(shù)的和是15×2＋21×3＋70×2，必然具有被3除余2，被5除余3，被7除余2的性質(zhì)。這個問題的算法是：

70×2＋21×3＋15×2＝233

233－105－105＝23所以這些物品最少有23個。問題二有一個年級的同學，每9人一排多5人，每7人一排多1人，每5人一排多2人，這個年級至少有多少人？問題二：280×5+225×1+126×2－315×5＝302人（9）（7）（5）

一位商人有9枚金幣，其中有一枚略輕的是假幣，你能用天平（無砝碼）將假幣找出來嗎？寫出解決這一問題的算法。創(chuàng)新型例題第一步：把9枚金幣平均分成三組，每組三枚。第三步：取出含假幣的那一組，從中任取兩枚金幣放在天平兩邊進行稱量，如果天平不平衡，則假金幣在輕的那一邊；若平衡，則未稱的那一枚就是假幣。第二步：先將其中的兩組放在天平的兩邊，如果天平不平衡，那么假金幣就在輕的那一組；如果天平左右平衡，則假金幣就在未稱量的那一組里。我國有這樣一個流傳已久，被稱作“韓信分油”的算術(shù)游戲：“3斤葫蘆、7斤罐、10斤油簍分一半”，就是用3斤、7斤和10斤這樣三種容器來分出兩個5斤，