浙江省高三信息技術(shù)學考總復考點突破課件解析算法與枚舉算法

解析算法與枚舉算法課標梳理教材重點課標要求學業(yè)質(zhì)量水平簡單算法及其程序?qū)崿F(xiàn)1.理解解析算法、枚舉算法的思想,能用解析、枚舉的方法來設(shè)計算法2.用程序來實現(xiàn)解析算法、枚舉算法以及其他簡單的算法2-1算法程序?qū)崿F(xiàn)的綜合應用通過綜合解決實際問題,編寫實行性程序,培養(yǎng)編程解決問題的能力2-2教材研析1解析算法及其程序?qū)崿F(xiàn)1.基本思想根據(jù)問題的前提條件與所求結(jié)果之間的關(guān)系,找出求解問題的數(shù)學表達式,并通過表達式的計算來實現(xiàn)問題的求解。2.解題思路問題的前提條件

要求的解

t=float(input('請輸入時間:'))v0=float(input('請輸入初速度:'))a=float(input('請輸入加速度:'))s=v0

t+a

t

2/2print('位移為',s,'米')典例1編寫Python程序,實現(xiàn)如下功能:輸入直角三角形2條直角邊長,應用勾股定理求出斜邊長并輸出,程序代碼如下。在劃線處填上合適的代碼。a=float(input('請輸入直角三角形直角\邊a長:'))b=float(input('請輸入直角三角形直角\邊b長:'))print('斜邊長為',________________________________)(a**2+b

**2)

**0.52枚舉算法及其程序?qū)崿F(xiàn)1.基本思想羅列出所有可能的解,不能遺漏,不能重復,并對每個可能的解進行判斷,是正確的解采納(輸出、計數(shù)……),不是的拋棄。2.語法結(jié)構(gòu)

循環(huán):羅列出所有可能的解

分支:判斷是否是正確的解(循環(huán)體中通過if后的條件進行判斷)3.范例:輸出所有個位上是1,同時又是7的倍數(shù)三位正整數(shù),并將滿足條件的數(shù)的個數(shù)輸出(如圖1所示)。4.優(yōu)化(1)為了提高效率,要使羅列的解的范圍盡可能小

需要判斷的次數(shù)(循環(huán)次數(shù))少。(2)范例:如圖2所示。典例2編寫Python程序,實現(xiàn)如下功能:輸出所有正的2位奇妙平方數(shù)(某數(shù)的平方與其逆序數(shù)的平方互為逆序數(shù),則該數(shù)為奇妙平方數(shù),例如122=144,212=441,則12為奇妙平方數(shù))。程序代碼如下。在劃線處填上合適的代碼。#自定義函數(shù)cp用于檢測參數(shù)n1和n2是否互逆defcp(n1,n2):flag=Falsen1=str(n1)n2=str(n2)iflen(n1)==len(n2):foriinrange(len(n1)):if①________________________________:

flag=Truebreakelse:②________________returnflag#以下for循環(huán)遍歷所有2位正整數(shù)c=0foriinrange(10,100,1):b=0a=in1[i]!=n2[len(n1)-1-i]flag=True#以下while循環(huán)用于獲取i當前遍歷到的2位正整數(shù)的逆序數(shù)whilea>0:

b=b

10+a%10

a=a//10if③____________________________________________andi!=b:

print(str(i)+'的平方:'+str(i

2)+'<——>'+str(b)+'的平方:'+str(b**2))

c+=1print('共有'+str(c)+'個2位奇妙平方數(shù)')cp(i**2,b**2)==False(或者notcp(i**2,b**2))解析

①自定義函數(shù)cp用于判斷參數(shù)n1和n2是否互逆,在兩數(shù)位數(shù)一樣的前提下,從n1中左起和n2中右起取的數(shù)對只要有1對不相等,就不為互逆,終止判斷,若所有數(shù)對都相等,則n1和n2互逆。②標志位flag初值為False代表開始判斷前默認互逆,若n1和n2的數(shù)字個數(shù)不同,肯定不互逆,將標志位的值改為True。③調(diào)用cp函數(shù)判斷數(shù)i的平方和它逆序數(shù)b的平方是否互逆,如果函數(shù)返回結(jié)果為False,則代表二者的平方數(shù)互逆,若同時滿足i和其逆序數(shù)b不相等,則可判定i為奇妙平方數(shù)。典例3(2022浙江7月學考)查找與替換。從鍵盤上分別輸入要查找和替換的字符串,對文本文件進行查找與替換,替換后保存到新的文本文件中。完成查找與替換功能的思路是:首先可從待檢索文本文件“in.txt”逐行讀取文本內(nèi)容到列表text,然后從鍵盤上輸入查找的字符串key和替換的字符串new,對列表text中的元素逐個進行查找并替換,結(jié)果保存到列表result,最后將result寫入文件“out.txt”。(1)主程序。text=readfile(″in.txt″)#讀入文件key=input(″請輸入要查找的字符串:″)new=input(″請輸入要替換的字符串:″)result=[]forlineintext:newline=replace(key,new,line)#替換result.append(newline)#添加到列表writefile(″out.txt″,result)#寫入文件該程序段采用的算法是____(單選,填字母:A.解析算法/B.枚舉算法)。

B(2)讀寫文本文件,如下的readfile函數(shù),逐行讀取文本文件數(shù)據(jù)存入列表并返回。請在劃線處填入合適的代碼。defreadfile(filename):f=open(″filename″,encoding=″utf-8″)#打開文件text=[]line=f.readline()#從文件中讀取一行whileline:

text.append(line)#添加到列表

line=f.readline()f.close()return________________defwritefile(filename,text):#將text寫入filename文件,代碼略Text(3)查找字符串,如下的findstr函數(shù),在字符串line中從begin位置開始查找key在字符串line中的位置,請在劃線處填入合適的代碼。deffindstr(key,line,begin): foriinrange(begin,len(line)-len\(key)+1): if________________________________:

returnireturn-1line[i:i+len(key)]==key(4)替換字符串。如下的replace函數(shù),在字符串line中檢索所有的字符串key并替換為new,請在劃線處填入合適的代碼。defreplace(key,new,line): begin=0 whilebegin<len(line)-len(key)+1:

pos=findstr(key,line,begin)

ifpos==-1:

___________________

else:line=line[0:pos]+new+\line[pos+len(key):len(line)]begin=pos+len(new) returnlinebreak(答案不唯一)解析

(1)枚舉算法的基本思想是把問題所有可能的解一一列舉,然后判斷每一個列舉出的可能解是否為正確的解。在枚舉算法的程序?qū)崿F(xiàn)中,逐一列舉出每一個可能解,判斷其是否為正確解的過程可采用循環(huán)結(jié)構(gòu)來實現(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進行比較,答案為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成立,說明當前行不存在key,直接跳出循環(huán)或終止循環(huán)即可。答案可以是break或begin=len(line)-len(key)+1或begin+=len(line)或begin=len(line),能跳出循環(huán)的語句均可。典例4(2023浙江7月學考)小張收集了章回體小說《三國演義》的第1章回至第120章回的120個文件,其文件名依次sg1.txt、sg2.txt、…、sg120.txt。他編寫Python程序,對書中人物同時出現(xiàn)的情況進行簡單分析,人物及其別名(如“孟德”是“曹操”的別名)作同一人處理。運行程序,用戶輸入“曹操|(zhì)孟德劉備|玄德”,輸出結(jié)果如圖所示,圖中[11,28]表示曹操,劉備在第11章回至第28章回同時出現(xiàn)。人物同時出現(xiàn)的章回數(shù)為:72,章回依次為:[[1,2],[5,6],[11,28],[31,45],[47,52],[54,58],[60,74],[77,82],[106,106],[119,120]]人物同時出現(xiàn)的最大連續(xù)章回數(shù)是:18A(2)定義函數(shù)calculate(total),功能是統(tǒng)計列表names中人物同時出現(xiàn)的章回數(shù),以及同時出現(xiàn)的章回,結(jié)果示例如第12題圖所示,請在劃線處填入合適的代碼。defcalculate(total): num,length=0,0

#num保存120個章回中人物同時出現(xiàn)的章回數(shù) result=[]

#result[i][0]、result[i][1]分別存儲第i+1段章回的起、止章回號 k=-1 foriinrange(0,120):

ifallIn(total,i):_________________________iflength==0:num+=1(或num=num+1)begin=i+1

result.append([begin,begin])

#在列表result末尾添加一個元素

k+=1length+=1result[k][1]=i+1

else:length=0returnnum,result(3)定義函數(shù)getMaxLen(result),功能是統(tǒng)計最大連續(xù)章回數(shù),請在劃線處填入合適的代碼。defgetMaxLen(result): mlen=0 foriteminresult: t=item[1]-item[0]+1 ift>________________:

mlen=treturnmlenMlen(4)定義函數(shù)allIn(total,cno),功能是判斷列表names中人物是否同時出現(xiàn)在cno章回中,若同時出現(xiàn),返回True,請在劃線處填入合適的代碼。defallIn(total,cno): foriteminnames: