資源簡介

(共16張PPT)
算法及其特征
——枚舉算法
學 習 目 標
深入學習算法的重要特征
運用Python語言實現簡單算法，解決問題
學會用枚舉算法解決問題
01
02
03
PART 1
算法及其特征
一、舊知回顧
什么是算法？
怎樣描述算法？
算法的基本特征有哪些？
二、問題導入
小王報名參加學校社團時。面試中有一道IQ題：有四個裝了藥丸的罐子，每個藥丸都有一定的重量，其中有一個藥罐被污染了。每片被污染的藥丸比污染前增重1克。只允許稱量一次，判斷出哪個罐子的藥被污染了。
分析問題
考慮1顆藥丸的質量變化，如果藥丸被污染，則增重 克，否則增重0 克。
從任一藥瓶中提取n顆藥丸，如果被污染，則增重 克，否則增重0 克。
從第一罐中取出1顆，第二罐中取出2顆，第三罐中取出3顆，從第四罐中取出4顆（共10顆）。如果增重________克，則________號藥瓶被污染。
輸入：？
計算：？
輸出：？
幾
幾
思考：
三、算法及其特征
1
n
請設計程序并運行，使輸入10顆藥丸的總重量及單顆藥丸標準質量就可以看到結果，找到被污染的藥丸。
2.設計算法
分析 現象（可多選） 算法的特征
哪些信息屬于輸入： 輸入項： □0個輸入 □1個輸入 □多個輸入
哪些信息屬于輸出： 輸出項： □0個輸出 □1個輸出 □多個輸出
執行的結果： 執行的結果：□確定的 □不確定的 □都可以
需要 步得到結果。 執行的步驟：□有限 □無限 □都可以
題耗時 。 執行的時間：□有限 □無限 □都可以
單顆標準重量，稱重后重量
多出的重量
找到被污染的瓶子
4
幾秒
√
√
√
√
√
0個或多個輸入
一定有輸出
確切性
有窮性
可行性
稱重后的質量-10顆標準質量
danke=int(input(‘請輸入每顆藥丸的標準重量：’))
zongde=int(input(‘請輸入藥丸稱得的重量：’))
x=zongde-10*danke
print('被污染的藥瓶序號是：',x)
3.編寫程序
運行代碼
PART 2
枚舉算法
有一種算法是把所有可能的答案一一列舉，合適就保留，不合適就丟棄。這種方法稱作“枚舉”或“窮舉”。
四、枚舉算法
枚舉算法基本思想：一 一列舉、逐一檢驗
枚舉法解決問題的一般結構：
枚舉使用要點：確定枚舉范圍和驗證條件
循環+判斷
密碼暴力破解
火柴棒擺數字
查找罪犯指紋
生活中的枚舉：
查找1000以內所有能被3、5 、7整除的數：
例：
范圍：
條件：
1--1000
整除3
整除5
整除7
for i in range(1,1001):
if (i%3==0)and (i%5==0)and (i%7==0):
print(i)
GO
循環
判斷
這次面試的冠軍就在小王和其他A、B、C、D四位同學中。消息很快傳到了班上，當A、B、C、D四人回到班上，小王迫不及待地問他們中誰得了冠軍。四人相對一笑：
A說：“不是我。”
B說：“是C。”
C說：“是D。”
D說：“C說的不對。”
原來他們想讓小王猜出答案，而且有一人說了假話。小明很快就知道了答案，大家都想知道他的方法。你能判斷到底誰是冠軍嗎？
三、枚舉算法
解析：利用枚舉法，逐一假設A、B、C、D是冠軍，判斷是否正確。
冠軍 A說：“不是我。” B說：“是C。” C說：“是D。” D說：“C說的不對。”
A
B
C
D
分子問題+設計算法
×
×
×
×
×
×
×
×
√
√
√
√
√
√
√
√
用程序求誰是冠軍時，我們需要把每個人說的話轉化成計算機能夠執行的表達式。如A說：“不是我。”可以表示為“i!='A'”，其中i為枚舉的冠軍選手編號。
冠軍 i!=‘A’ i==‘C’ i==‘D' i!='D’
A × × × √
B √ × × √
C √ √ × √
D √ × √ ×
實現方法：布爾值數值化
i!=‘A’的運算結果是一個邏輯值，在數值計算中會自動轉換成1（True）或0（Flase）
分析以下代碼的含義，理解解題思路。
xuanshou=['A','B','C','D'] #設置選手列表
for i in xuanshou: #循環讀取選手編號
tiaojian=(i!=‘A’)+(i==‘C’) + (i==‘D')+(i!='D‘) #查找符合條件的選手
if tiaojian==3: #說真話是否是3人
print("冠軍是:",i)
GO
范圍：
條件：
A、B、C、D
說真話的人數是否為3人
編寫程序
課堂小結
枚舉算法基本思想：一 一列舉、逐一檢驗
枚舉法解決問題的一般結構：循環+判斷。
枚舉使用要點：確定枚舉范圍和驗證條件

展開更多......

收起↑