資源簡介

(共27張PPT)
第3章
課時(shí)13 解析算法與枚舉算法
信息技術(shù)
課標(biāo)梳理·微知著
教材重點(diǎn) 課標(biāo)要求 學(xué)業(yè)質(zhì)量水平
簡單算法及
其程序?qū)崿F(xiàn) 1.理解解析算法、枚舉算法的思想,能用解析、枚舉的方法來設(shè)計(jì)算法
2.用程序來實(shí)現(xiàn)解析算法、枚舉算法以及其他簡單的算法 2-1
算法程序?qū)崿F(xiàn)
的綜合應(yīng)用 通過綜合解決實(shí)際問題,編寫實(shí)行性程序,培養(yǎng)編程解決問題的能力 2-2
教材研析·固基礎(chǔ)
1
解析算法及其程序?qū)崿F(xiàn)
1.基本思想
根據(jù)問題的前提條件與所求結(jié)果之間的關(guān)系,找出求解問題的數(shù)學(xué)表達(dá)式,并通過表達(dá)式的計(jì)算來實(shí)現(xiàn)問題的求解。
2.解題思路
問題的前提條件
要求的解
t=float(input('請輸入時(shí)間:'))
v0=float(input('請輸入初速度:'))
a=float(input('請輸入加速度:'))
s=v0 t+a t 2/2
print('位移為',s,'米')
典例1 編寫Python程序,實(shí)現(xiàn)如下功能:輸入直角三角形2條直角邊長,應(yīng)用勾股定理求出斜邊長并輸出,程序代碼如下。在劃線處填上合適的代碼。
a=float(input('請輸入直角三角形直角\邊a長:'))
b=float(input('請輸入直角三角形直角\邊b長:'))
print('斜邊長為',________________________________)
(a * * 2+b * * 2) * * 0.5
2
枚舉算法及其程序?qū)崿F(xiàn)
1.基本思想
羅列出所有可能的解,不能遺漏,不能重復(fù),并對每個(gè)可能的解進(jìn)行判斷,是正確的解采納(輸出、計(jì)數(shù)……),不是的拋棄。
2.語法結(jié)構(gòu)
　循環(huán):羅列出所有可能的解
　分支:判斷是否是正確的解(循環(huán)體中通過if后的條件進(jìn)行判斷)
3.范例:輸出所有個(gè)位上是1,同時(shí)又是7的倍數(shù)三位正整數(shù),并將滿足條件的數(shù)的個(gè)數(shù)輸出(如圖1所示)。
4.優(yōu)化
(1)為了提高效率,要使羅列的解的范圍盡可能小 需要判斷的次數(shù)(循環(huán)次數(shù))少。
(2)范例:如圖2所示。
典例2 編寫Python程序,實(shí)現(xiàn)如下功能:輸出所有正的2位奇妙平方數(shù)(某數(shù)的平方與其逆序數(shù)的平方互為逆序數(shù),則該數(shù)為奇妙平方數(shù),例如122=144, 212=441,則12為奇妙平方數(shù))。程序代碼如下。在劃線處填上合適的代碼。
#自定義函數(shù)cp用于檢測參數(shù)n1和n2是否互逆
def cp(n1,n2):
flag=False
n1=str(n1)
n2=str(n2)
if len(n1)==len(n2):
for i in range(len(n1)):
if ①________________________________:
flag=True
break
else:
②________________
return flag
#以下for循環(huán)遍歷所有2位正整數(shù)
c=0
for i in range(10,100,1):
b=0
a=i
n1[i]!=n2[len(n1)-1-i]
flag=True
#以下while循環(huán)用于獲取i當(dāng)前遍歷到的2位正整數(shù)的逆序數(shù)
while a>0:
　b=b 10+a % 10
　a=a//10
if ③____________________________________________ and i!=b:
print(str(i)+'的平方:'+str(i 2)+'<——>'+str(b)+'的平方:'+str(b**2))
　c+=1
print('共有'+str(c)+'個(gè)2位奇妙平方數(shù)')
cp(i**2,b**2)==False(或者not cp(i**2,b**2))
解析 ①自定義函數(shù)cp用于判斷參數(shù)n1和n2是否互逆,在兩數(shù)位數(shù)一樣的前提下,從n1中左起和n2中右起取的數(shù)對只要有1對不相等,就不為互逆,終止判斷,若所有數(shù)對都相等,則n1和n2互逆。
②標(biāo)志位flag初值為False代表開始判斷前默認(rèn)互逆,若n1和n2的數(shù)字個(gè)數(shù)不同,肯定不互逆,將標(biāo)志位的值改為True。
③調(diào)用cp函數(shù)判斷數(shù)i的平方和它逆序數(shù)b的平方是否互逆,如果函數(shù)返回結(jié)果為False,則代表二者的平方數(shù)互逆,若同時(shí)滿足i和其逆序數(shù)b不相等,則可判定i為奇妙平方數(shù)。
典例3 (2022浙江7月學(xué)考)查找與替換。從鍵盤上分別輸入要查找和替換的字符串,對文本文件進(jìn)行查找與替換,替換后保存到新的文本文件中。
完成查找與替換功能的思路是:首先可從待檢索文本文件“in.txt”逐行讀取文本內(nèi)容到列表text,然后從鍵盤上輸入查找的字符串key和替換的字符串new,對列表text中的元素逐個(gè)進(jìn)行查找并替換,結(jié)果保存到列表result,最后將result寫入文件“out.txt”。
(1)主程序。
text=readfile(″in.txt″)#讀入文件
key=input(″請輸入要查找的字符串:″)
new=input(″請輸入要替換的字符串:″)
result=[]
for line in text:
newline=replace(key,new,line)#替換
result.append(newline)#添加到列表
writefile(″out.txt″,result)#寫入文件
該程序段采用的算法是____(單選,填字母:A.解析算法/B.枚舉算法)。
B
(2)讀寫文本文件,如下的readfile函數(shù),逐行讀取文本文件數(shù)據(jù)存入列表并返回。請?jiān)趧澗€處填入合適的代碼。
def readfile(filename):
f=open(″filename″,encoding=″utf-8″) #打開文件
text=[]
line=f.readline() #從文件中讀取一行
while line:
　text.append(line) #添加到列表
　line=f.readline()
f.close()
return ________________
def writefile(filename,text): #將text寫入filename文件,代碼略
Text
(3)查找字符串,如下的findstr函數(shù),在字符串line中從begin位置開始查找key在字符串line中的位置,請?jiān)趧澗€處填入合適的代碼。
def findstr(key,line,begin):
for i in range(begin,len(line)-len\(key)+1):
if________________________________:
return i
return -1
line[i:i+len(key)]==key
(4)替換字符串。如下的replace函數(shù),在字符串line中檢索所有的字符串key并替換為new,請?jiān)趧澗€處填入合適的代碼。
def replace(key,new,line):
begin=0
while begin　 pos=findstr(key,line,begin)
　 if pos==-1:
___________________
　 else:
line=line[0:pos]+new+\line[pos+len(key):len(line)]
begin=pos+len(new)
return line
break(答案不唯一)
解析 (1)枚舉算法的基本思想是把問題所有可能的解一一列舉,然后判斷每一個(gè)列舉出的可能解是否為正確的解。在枚舉算法的程序?qū)崿F(xiàn)中,逐一列舉出每一個(gè)可能解,判斷其是否為正確解的過程可采用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。而在利用問題提供的約束條件篩選、判斷解的過程中則需要用到分支結(jié)構(gòu)。從題干“……逐行讀取文本內(nèi)容到列表text……”,推斷出(1)答案為B。
(2)根據(jù)題干“逐行讀取文本文件數(shù)據(jù)存入列表并返回”,觀察列表相關(guān)語句“text=[]”和“text.append(line)”,答案為text。
(3)自定義函數(shù)findstr的功能是在字符串line中查找key,如果找到了返回第一次出現(xiàn)key的索引,如果不存在key,返回-1。從語句“for i in range(begin,len(line)-len(key)+1)”看出for循環(huán)語句遍歷索引,因此從line中選擇從i開始長度為len(key)的字符,和key進(jìn)行比較,答案為line[i:i+len(key)]==key。
(4)自定義函數(shù)replace的功能是在字符串line中檢索所有的字符串key并替換為new,程序使用了while循環(huán)從begin開始遍歷字符串line,調(diào)用自定義函數(shù)findstr在字符串line中查找key,返回值為pos,pos==-1成立,說明當(dāng)前行不存在key,直接跳出循環(huán)或終止循環(huán)即可。答案可以是break或begin=len(line)-len(key)+1或begin+=len(line)或begin=len(line),能跳出循環(huán)的語句均可。
典例4 (2023浙江7月學(xué)考)小張收集了章回體小說《三國演義》的第1章回至第120章回的120個(gè)文件,其文件名依次sg1.txt、sg2.txt、…、sg120.txt。他編寫Python程序,對書中人物同時(shí)出現(xiàn)的情況進(jìn)行簡單分析,人物及其別名(如“孟德”是“曹操”的別名)作同一人處理。運(yùn)行程序,用戶輸入“曹操|(zhì)孟德　劉備|玄德”,輸出結(jié)果如圖所示,圖中[11,28]表示曹操,劉備在第11章回至第28章回同時(shí)出現(xiàn)。
人物同時(shí)出現(xiàn)的章回?cái)?shù)為:72,章回依次為:[[1,2],[5,6],[11,28],[31,45],[47,52],[54,58],[60,74],[77,82],[106,106],[119,120]]
人物同時(shí)出現(xiàn)的最大連續(xù)章回?cái)?shù)是:18
請回答下列問題:
(1)觀察第12題圖,可知曹操與劉備在第36章回中_____(單選,填字母:A.同時(shí)/B.沒有同時(shí))出現(xiàn)。
主程序如下:

輸入姓名、別名,姓名存入列表names,如names=[″曹操″,″劉備″]
統(tǒng)計(jì)各個(gè)章回中,列表names中每個(gè)人物(含別名)出現(xiàn)的次數(shù),結(jié)果存入字典total,如total={″曹操″:[2,5,7,…],″劉備″:[50,47,0,…]},表示曹操在第1,2,3,…章回分別出現(xiàn)了2,5,7,…次
代碼略

num,result=calculate(total)
mlen=getMaxLen(result)
print(″人物同時(shí)出現(xiàn)的章回?cái)?shù)為:″,\num,″,章回依次為:″)
print(result)
print(″人物同時(shí)出現(xiàn)的最大連續(xù)章回?cái)?shù)\是:″,mlen)
A
(2)定義函數(shù)calculate(total),功能是統(tǒng)計(jì)列表names中人物同時(shí)出現(xiàn)的章回?cái)?shù),以及同時(shí)出現(xiàn)的章回,結(jié)果示例如第12題圖所示,請?jiān)趧澗€處填入合適的代碼。
def calculate(total):
num,length=0,0　#num保存120個(gè)章回中人物同時(shí)出現(xiàn)的章回?cái)?shù)
result=[]　#result[i][0]、result[i][1]分別存儲(chǔ)第i+1段章回的起、止章回號(hào)
k=-1
for i in range(0,120):
　 if allIn(total,i):
_________________________
if length==0:
num+=1(或num=num+1)
begin=i+1
result.append([begin,begin])
#在列表result末尾添加一個(gè)元素
　 k+=1
length+=1
result[k][1]=i+1
　 else:
length=0
return num,result
(3)定義函數(shù)getMaxLen(result),功能是統(tǒng)計(jì)最大連續(xù)章回?cái)?shù),請?jiān)趧澗€處填入合適的代碼。
def getMaxLen(result):
mlen=0
for item in result:
t=item[1]-item[0]+1
if t>________________:
　mlen=t
return mlen
Mlen
(4)定義函數(shù)allIn(total,cno),功能是判斷列表names中人物是否同時(shí)出現(xiàn)在cno章回中,若同時(shí)出現(xiàn),返回True,請?jiān)趧澗€處填入合適的代碼。
def allIn(total,cno):
for item in names:
　 if ________________________:
return False
　 return True
total[item][cno]==0
解析 本題考查Python語言基礎(chǔ)及字符串處理的綜合知識(shí)。(1)觀察圖可知,第36回出現(xiàn)在[31,45]中,表明曹操與劉備這兩個(gè)人物在36回同時(shí)出現(xiàn),故選A。(2)由于num保存120個(gè)章回中人物同時(shí)出現(xiàn)的章回?cái)?shù),其初值為0,因此若檢查到符合條件時(shí),即調(diào)用函數(shù)allIn(total,cno)且其值為True時(shí),計(jì)數(shù)器num加1,因此其表達(dá)式為num+=1。(3)此處統(tǒng)計(jì)最大連續(xù)章回?cái)?shù),變量mlen即為返回值。在循環(huán)中,將連續(xù)章回?cái)?shù)t與最大值mlen進(jìn)行比較,若有比最大值mlen更大的值t,則將t值賦值給mlen,故答案是mlen。(4)由于total={″曹操″:[2,5,7,…],″劉備″:[50,47,0,…]},表示曹操在第1,2,3,…章回分別出現(xiàn)了2,5,7,…次,根據(jù)這個(gè)信息可知total是一個(gè)字典,item是某人物名,cno是某章回號(hào)的值,因此若total[item][cno]==0,則表明人物item在章回號(hào)cno中出現(xiàn)的次數(shù)為0,故函數(shù)返回值為False,反之則返回True。

展開更多......

收起↑