3.2算法及其描述課件

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

設(shè)備產(chǎn)品ABCD甲2140乙2204丙1100設(shè):甲，乙，丙三種產(chǎn)量分別為x,y,z臺(tái)。根據(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ù)學(xué)中，算法通常是指按照一定規(guī)則解決某一類問題的明確和有限的步驟?，F(xiàn)在，算法通常可以編成計(jì)算機(jī)程序，讓計(jì)算機(jī)執(zhí)行并解決問題。1.算法的概念講授新課算法計(jì)算機(jī)中算法概念：計(jì)算機(jī)求解某一問題的方法，是能被機(jī)械的執(zhí)行的指令的有窮集合。實(shí)踐兩個(gè)整數(shù)m=112和n=64，利用輾轉(zhuǎn)相除法，求它們的最大公約數(shù)1、112除以64，余數(shù)為2、除以余數(shù)為3、除以余數(shù)為4、112和64的最大公約數(shù)為486448164816016二、算法的特征有窮性：執(zhí)行有限步之后結(jié)束，且每一

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

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

第一步:運(yùn)羊過河,回來第二步:運(yùn)菜過河,并運(yùn)羊回來第三步:運(yùn)狼過河,回來第四步:運(yùn)羊過河

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

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

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

意思之一：這個(gè)人不認(rèn)識(shí)老張。意思之二：老張不認(rèn)識(shí)這個(gè)人。

2、用流程圖來描述

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

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

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

運(yùn)菜過河,

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

為例：算法分析：以“韓信點(diǎn)兵問題”

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

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

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

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

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

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