資源簡介

(共20張PPT)
算法初步
人鬼過河
把三個人和三個鬼都送到對岸，船上必須有一個人或鬼才可以行駛，船上最多能坐兩個人或鬼，在河的任何一邊，當鬼的個數比人多時，鬼就會吃掉人。請問如何才能使人和鬼都平安的到達對岸？
人鬼過河
把三個人和三個鬼都送到對岸，船上必須有一個人或鬼才可以行駛，船上最多能坐兩個人或鬼，在河的任何一邊，當鬼的個數比人多時，鬼就會吃掉人。請問如何才能使人和鬼都平安的到達對岸？
方法一
人鬼過河
把三個人和三個鬼都送到對岸，船上必須有一個人或鬼才可以行駛，船上最多能坐兩個人或鬼，在河的任何一邊，當鬼的個數比人多時，鬼就會吃掉人。請問如何才能使人和鬼都平安的到達對岸？
方法二
算法的概念
解決問題的具體方法和步驟
生活中的算法
燒菜
洗衣服
做數學題
計算機中的算法
兩個賣油的伙計要平分10斤油，可手上沒有秤。他們只有一個油簍，空油罐和空葫蘆（容積各為10斤、7斤、3斤）。兩個伙計不知該怎么分，正在為難之時，遇上了騎馬趕路的漢將韓信。韓信連馬都沒下，三言兩語便說出了分油的辦法
請嘗試設計分油方案
韓信分油
油簍
油罐
葫蘆
10斤
7斤
3斤
韓信分油算法
油桶A中的油量為a，油壺B（容積為bv）中的油量為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;
若bStep3:當C壺滿（c=cv）時，從C壺倒回A桶。
操作中，若有a=i或b=i或c=i時，達到平分目的，操作結束。
韓信分油
第二次分油
兩個賣油的伙計要平分16斤油，可手上沒有秤。他們只有一個油簍，空油罐和空葫蘆（容積各為16斤、9斤、5斤）。
油簍
油罐
葫蘆
16斤
9斤
5斤
請嘗試設計分油方案
00
08
:
開始
計算機利用算法解決問題
計算機中算法的概念
在計算機中，算法是指可以用計算機來解決某一類問題的明確、有效的有限步驟。
算法目的
解決某一類問題（通用性和價值）
算法特征
明確性
可行性
有窮性
有序性
自然語言
易理解，不簡潔，容易發(fā)生歧義
油桶A中的油量為a，油壺B（容積為bv）中的油量為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;
若bStep3:當C壺滿（c=cv）時，從C壺倒回A桶。
操作中，若有a=i或b=i或c=i時，達到平分目的，操作結束。
流程圖
直觀、簡潔，邏輯關系清晰
a,b,c中是
否有等于i？
結束
N
開始
Y
倒空B壺
A倒?jié)MB
B倒?jié)MC壺
b>=cv-c
Y
C壺倒入A桶
N
A桶倒?jié)MB壺
偽代碼
輸入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 If
Loop
Print a, b, c
自然語言
流程圖
算法描述方法
偽代碼
有9個硬幣，其中1個是假幣（偏輕），給你1架天平，你能把這個假幣找出來嗎？ 請設計算法。
s1.任取2枚銀幣分別放在天平的兩邊，如果天平不平衡，則輕的那一邊就是假銀幣；否則進行s2
s2.取下右邊的銀幣，然后把剩下的7枚銀幣依次放在右邊進行稱量，直到天平不平衡，偏輕的那一邊就是假銀幣。
s1.任取兩枚銀幣分別放在天平的兩端，如果天平左右不平衡，則輕的那一邊是假銀幣；否則進行s2
s2.重復執(zhí)行s1，如果前4次天平都平衡，則剩下的那一枚是假銀幣。
s1.分別取四枚銀幣放在天平兩端，如果天平左右平衡，則剩下的那枚硬幣是假銀幣；否則假硬幣在較輕的那組，進行s2。
s2.將較輕的四枚硬幣分成兩份，分別放在天平兩端，假硬幣在較輕的那兩枚硬幣中。
s3.將含假硬幣的兩枚硬幣分別放在天平兩端，較輕的那一枚是假硬幣。
s1.把9枚銀幣平均分成3組，每組3枚。
s2.先將其中兩組放在天平的兩邊，如果天平不平衡，那么假銀幣幣就在輕的那一組；如果天平左右平衡，則假銀幣就在未稱量的那一組內。
s3.取出含有假銀幣的那一組，從中任取2枚銀幣放在天平左右兩邊進行稱量，如果天平不平衡，則輕的那一邊是假銀幣；如果天平平衡，則未稱的那一枚就是假銀幣。
方法一
7次
方法二
4次
方法二
3次
方法四
2次
算法優(yōu)化思想
1、解決同一個問題，可以用不同的算法，其效果和效率可能大不相同。
2、算法很重要，我們要根據實際情況，有意識的設計最優(yōu)的算法解決問題。
算法初探
概念及特征
描述方法
優(yōu)化思想
思想及其重要性
謝 謝

展開更多......

收起↑