1、算法初探,上饒中學 李娜,算法初探,人鬼安全渡河,把三個人和三個鬼都送到對岸，船上必須有一個人或鬼才可以行駛，船上最多能坐兩個人或鬼，在河的任何一邊，當鬼的個數(shù)比人多時，鬼就會吃掉人。請問如何才能使人和鬼都平安的到達對岸？,請討論并試驗，設計成功過河方案。,算法的概念,算法初探,什么是算法？,解決問題的具體方法和步驟,Step1:一人一鬼乘船至對岸 ； Step2:鬼上岸，人乘船回； Step3:兩個鬼乘船至對岸； Step4:一個鬼上岸，一個鬼乘船回； Step5:兩個人乘船至對岸； Step6:一個人上岸，一人一鬼乘船回； Step7:兩個人乘船至對岸。 Step8:兩個人上岸，一個鬼乘船

2、回； Step9:兩個鬼乘船至對岸； Step10:一個鬼上岸，一鬼乘船回； Step11:兩個鬼乘船至對岸。,Step1:兩個鬼乘船至對岸 ； Step2:一鬼上岸，另一鬼乘船回； Step3:兩個鬼乘船至對岸； Step4:一個鬼上岸，一個鬼乘船回； Step5:兩個人乘船至對岸； Step6:一個人上岸，一人一鬼乘船回； Step7:兩個人乘船至對岸。 Step8:兩個人上岸，一個鬼乘船回； Step9:兩個鬼乘船至對岸； Step10:一個鬼上岸，一鬼乘船回； Step11:兩個鬼乘船至對岸。,算法的概念,算法初探,什么是算法？,解決問題的具體方法和步驟,Step1:兩個鬼乘船至對岸

3、； Step2:一鬼上岸，另一鬼乘船回； Step3:兩個鬼乘船至對岸； Step4:一個鬼上岸，一個鬼乘船回； Step5:兩個人乘船至對岸； Step6:一個人上岸，一人一鬼乘船回； Step7:兩個人乘船至對岸。 Step8:兩個人上岸，一個鬼乘船回； Step9:兩個鬼乘船至對岸； Step10:一個鬼上岸，一鬼乘船回； Step11:兩個鬼乘船至對岸。,Step1:一人一鬼乘船至對岸 ； Step2:鬼上岸，人乘船回； Step3:兩個鬼乘船至對岸； Step4:一個鬼上岸，一個鬼乘船回； Step5:兩個人乘船至對岸； Step6:一個人上岸，一人一鬼乘船回； Step7:兩個人乘

4、船至對岸。 Step8:兩個人上岸，一個鬼乘船回； Step9:兩個鬼乘船至對岸； Step10:一個鬼上岸，一鬼乘船回； Step11:兩個鬼乘船至對岸。,算法的概念,算法初探,生活中有哪些地方用到算法？,算法的概念,算法初探,計算機中的算法,兩個賣油的伙計要平分10斤油，可手上沒有秤。他們只有一個油桶，中油壺和小油壺（容積各為10斤、7斤、3斤）。兩個伙計不知該怎么分，正在為難之時，遇上了騎馬趕路的漢將韓信。韓信連馬都沒下，三言兩語便說出了分油的辦法。韓信立馬分油故事,請嘗試設計分油方案。,10 0 0,桶 中壺 小壺,3 7 0,算法初探,算法的概念,油桶A中的油量為a，油壺B（容積為b

5、v)中的油量為b，油壺C（容積為cv)中的油量為c，需要將A中油量a平分為兩個i； 操作步驟如下：A-B-C-A step1.當B壺空（b=0）時，從A桶倒?jié)MB壺。 step2.從B壺分一次或多次倒?jié)MC壺 若b=cv-c，倒?jié)MC壺，操作step3; 若bcv-c，倒空B壺，操作step1; Step3:當C壺滿（c=cv）時，從C壺倒回A桶。 操作中，若有a=i或b=i或c=i時，達到平分目的，操作結束。,算法的概念,算法初探,第二次分油,兩個賣油的伙計要平分16斤油，可手上沒有秤。他們只有一個油簍，一個油罐和一個油葫蘆（容積各為16斤、9斤、5斤）。,算法初探,算法的概念,算法的概念,算法初

6、探,什么是計算機中算法？,在計算機中，算法是指可以用計算機來解決某一類問題的明確、有效的有限步驟。,算法的目的：解決某一類問題（通用性和價值） 算法的特征：明確性、可行性、有窮性、有序性,算法初探,易理解，不簡潔，容易發(fā)生歧義,算法的描述方法,油桶A中的油量為a，油壺B（容積為m)中的油量為b，油壺C（容積為n)中的油量為c，需要將A中油量a平分為兩個i； 操作步驟如下：A-B-C-A step1.當B壺空（b=0）時，從A桶倒?jié)MB壺。 step2.從B壺分一次或多次倒?jié)MC壺 若b=cv-c，倒?jié)MC壺，操作step3; 若bcv-c，倒空B壺，操作step1; Step3:當C壺滿（c=cv）

7、時，從C壺倒回A桶。 操作中，若有a=i或b=i或c=i時，達到平分目的，操作結束。,算法初探,算法的描述方法,直觀、簡潔，邏輯關系清晰,以“韓信分油為例,用各種框圖及文字表示各種操作步驟。,輸入a，b，cv c=0，i = a / 2，a = a - b Do While a i And b i And c i print a, b, c If b = cv-c Then B壺倒?jié)MC壺（b = b - cv , c = cv） Print a, b, c C倒入A(a = a + c) Else B全部倒入C壺（ c = b，b = 0） Print a, b, c A桶倒?jié)MB壺 End I

8、f Loop Print a, b, c,算法初探,算法的描述方法,偽代碼-介于自然語言和真正的程序代碼之間的一種算法描述,“韓信分油” 偽代碼,算法的描述,算法初探,如何表達和描述算法？,自然語言,流程圖,偽代碼,算法初探,有9個硬幣，其中1個是假幣（偏輕），給你1架天平，你能把這個假幣找出來嗎？ 請設計算法。,小試牛刀,算法初探,方法一：s1.任取2枚銀幣分別放在天平的兩邊，如果天平不平衡，則輕的那一邊就是假銀幣；否則進行s2。s2.取下右邊的銀幣，然后把剩下的7枚銀幣依次放在右邊進行稱量，直到天平不平衡，偏輕的那一邊就是假銀幣。,方法二：s1.任取兩枚銀幣分別放在天平的兩端，如果天平左右

9、不平衡，則輕的那一邊是假銀幣；否則進行s2。s2.重復執(zhí)行s1，如果前4次天平都平衡，則剩下的那一枚是假銀幣。,方法三：s1.把9枚銀幣平均分成3組，每組3枚。s2.先將其中兩組放在天平的兩邊，如果天平不平衡，那么假銀幣幣就在輕的那一組；如果天平左右平衡，則假銀幣就在未稱量的那一組內。s3.取出含有假銀幣的那一組，從中任取2枚銀幣放在天平左右兩邊進行稱量，如果天平不平衡，則輕的那一邊是假銀幣；如果天平平衡，則未稱的那一枚就是假銀幣。,方法四： s1.分別取四枚銀幣放在天平兩端，如果天平左右平衡，則剩下的那枚硬幣是假銀幣；否則假硬幣在較輕的那組，進行s2。 s2.將較輕的四枚硬幣分成兩份，分別放在天平兩端，假硬幣在較輕的那兩枚硬幣中。 s3.將含假硬幣的兩枚硬幣分別放在天平兩端，較輕的那一枚是假硬幣。,小試牛刀,7次,4次,3次,2次,算法初探,算法優(yōu)化思想,1、解決同一個問題，可以用不同的算法，其效果和效率可能大不相同。 2、算法很重要，我們要根據(jù)實際情況，有意識的設計最優(yōu)的算法解決問題。,算法初探,課堂小結,算法的概念,算法的初探,第二次分油,兩