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

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

要求的解

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

t+a

t

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

**2)

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

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

分支:判斷是否是正確的解(循環(huán)體中通過(guò)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編寫(xiě)Python程序,實(shí)現(xiàn)如下功能:輸出所有正的2位奇妙平方數(shù)(某數(shù)的平方與其逆序數(shù)的平方互為逆序數(shù),則該數(shù)為奇妙平方數(shù),例如122=144,212=441,則12為奇妙平方數(shù))。程序代碼如下。在劃線處填上合適的代碼。#自定義函數(shù)cp用于檢測(cè)參數(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當(dāng)前遍歷到的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)+'個(gè)2位奇妙平方數(shù)')cp(i**2,b**2)==False(或者notcp(i**2,b**2))解析

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

B(2)讀寫(xiě)文本文件,如下的readfile函數(shù),逐行讀取文本文件數(shù)據(jù)存入列表并返回。請(qǐng)?jiān)趧澗€處填入合適的代碼。defreadfile(filename):f=open(″filename″,encoding=″utf-8″)#打開(kāi)文件text=[]line=f.readline()#從文件中讀取一行whileline:

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

line=f.readline()f.close()return________________defwritefile(filename,text):#將text寫(xiě)入filename文件,代碼略Text(3)查找字符串,如下的findstr函數(shù),在字符串line中從begin位置開(kāi)始查找key在字符串line中的位置,請(qǐng)?jiān)趧澗€處填入合適的代碼。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,請(qǐng)?jiān)趧澗€處填入合適的代碼。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)枚舉算法的基本思想是把問(wèn)題所有可能的解一一列舉,然后判斷每一個(gè)列舉出的可能解是否為正確的解。在枚舉算法的程序?qū)崿F(xiàn)中,逐一列舉出每一個(gè)可能解,判斷其是否為正確解的過(guò)程可采用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。而在利用問(wèn)題提供的約束條件篩選、判斷解的過(guò)程中則需要用到分支結(jié)構(gòu)。從題干“……逐行讀取文本內(nèi)容到列表text……”,推斷出(1)答案為B。(2)根據(jù)題干“逐行讀取文本文件數(shù)據(jù)存入列表并返回”,觀察列表相關(guān)語(yǔ)句“text=[]”和“text.append(line)”,答案為text。(3)自定義函數(shù)findstr的功能是在字符串line中查找key,如果找到了返回第一次出現(xiàn)key的索引,如果不存在key,返回-1。從語(yǔ)句“for

i

in

range(begin,len(line)-len(key)+1)”看出for循環(huán)語(yǔ)句遍歷索引,因此從line中選擇從i開(kāi)始長(zhǎng)度為len(key)的字符,和key進(jìn)行比較,答案為line[i:i+len(key)]==key。(4)自定義函數(shù)replace的功能是在字符串line中檢索所有的字符串key并替換為new,程序使用了while循環(huán)從begin開(kāi)始遍歷字符串line,調(diào)用自定義函數(shù)findstr在字符串line中查找key,返回值為pos,pos==-1成立,說(shuō)明當(dāng)前行不存在key,直接跳出循環(huán)或終止循環(huán)即可。答案可以是break或begin=len(line)-len(key)+1或begin+=len(line)或begin=len(line),能跳出循環(huán)的語(yǔ)句均可。典例4(2023浙江7月學(xué)考)小張收集了章回體小說(shuō)《三國(guó)演義》的第1章回至第120章回的120個(gè)文件,其文件名依次sg1.txt、sg2.txt、…、sg120.txt。他編寫(xiě)Python程序,對(duì)書(shū)中人物同時(shí)出現(xiàn)的情況進(jìn)行簡(jiǎ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ù)是:18A(2)定義函數(shù)calculate(total),功能是統(tǒng)計(jì)列表names中人物同時(shí)出現(xiàn)的章回?cái)?shù),以及同時(shí)出現(xiàn)的章回,結(jié)果示例如第12題圖所示,請(qǐng)?jiān)趧澗€處填入合適的代碼。defcalculate(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 foriinrange(0,120):

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

result.append([begin,begin])

#在列表result末尾添加一個(gè)元素

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

else:length=0returnnum,result(3)定義函數(shù)getMaxLen(result),功能是統(tǒng)計(jì)最大連續(xù)章回?cái)?shù),請(qǐng)?jiān)趧澗€處填入合適的代碼。defgetMaxLen(result): mlen=0 foriteminresult: t=item[1]-item[0]+1 ift>________________:

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