資源簡介

課時8　解析、枚舉算法及程序實現
課時目標
1.掌握解析和枚舉算法的基本思想。2.掌握使用解析和枚舉算法解決實際問題的基本方法,并通過編寫程序實現問題求解。
一、解析算法的基本思想
解析算法的基本思想是指根據問題的前提條件與所求結果之間的關系,找出求解問題的數學表達式,并通過表達式的計算來實現問題的求解。
二、解析算法解題的基本思路
1.建立正確的數學模型,即得出正確的數學代數式。
2.將數學代數式轉化為Python式子。
三、解析算法程序實現的步驟
1.運用解析算法分析問題,尋找問題中各要素之間的關系,用數學表達式表示它們的關系。
2.寫出解決問題的解析步驟,編寫程序實現,通過運行程序求得問題的正確解。
四、枚舉算法的基本思想
枚舉算法的基本思想是把問題所有可能的解一一列舉,然后判斷每一個列舉出的可能解是否為正確的解。
枚舉算法常用于解決是否存在或有多少種可能等類型的問題。
五、枚舉算法的基本框架
1.枚舉算法三要素
枚舉范圍、枚舉對象、判斷條件。
2.基本框架
循環結構
分支結構
枚舉范圍是用來表示枚舉對象存在的一個連續區間,用循環結構語句實現。
判斷條件用來檢測當前枚舉的對象是否為問題的解。
　　　　　　　　　　　　　　　　
例1 已排序的列表a有n個整型元素,現要查找出現次數最多的值并輸出。若出現次數最多的值有多個,則輸出最前面的一個。實現該功能的程序段如下,方框中應填入的正確代碼為 (　　)
c,m,v =1,1,0
for i in range(1,n):
　　　　
print(a[v])
A.if a[i]==a[i-1]:
　　 c+=1
　　 if c>m:
　　　　m=c
　　　　v=i
　else:
　　 c=1
B.if a[i]==a[i-1]:
　　 c+=1
　　 if c>m:
　　　　m=c
　　　　v=i
　　 else:
　　　　c=1
C.if a[i]==a[i-1]:
　　 c+=1
　else:
　　 if c>m:
　　　　m=c
　　　　v=i-1
　　　　c=1
D.if a[i]==a[i-1]:
　　 c+=1
　else:
　　if c>m:
　　　　m=c
　　　　v=i-1
　　c=1
答案　A
解析　本題考查一維列表的遍歷和最值的查找。 已排序的列表a有n個整型元素,當條件a[i]==a[i-1]成立時,表示有連續相等的數量c。A選項每找到一個相等的值,求解數量的最大值,并保存此時的索引位置v,若不相等時初始化c的個數為1。B選項初始化c的個數就在兩個不相等的值時。C選項當兩個數相等時進行計數,當兩個數不相等時,進行最值的查找,同時初始c的值為1,但該選項c的初始化發生在找到最大值時。D選項若長度的最大值發生在最后,即該列表最后的幾個數是長度是最大值時,只是在進行計數,并未進行最大值的查找。
例2 某倉庫有一排連續相鄰的貨位,編號依次為0~n-1,用于放置A、B兩種類型的箱子,A型箱子占2個相鄰貨位,B型箱子占1個貨位。編寫程序,根據已完成的放置或搬離操作,輸出空貨位數及還可以放置A型箱子的最多數量(不移動已放置的箱子)。請回答下列問題:
箱子類型 操作類型 貨位編號
B 放置 5
A 放置 2,3
B 放置 0
A 放置 7,8
A 搬離 2,3
(1)若n為10,開始時貨位全空,經過如圖所示的放置或搬離操作后,不移動已放置箱子的情況下,還可放置A型箱子的最多數量為　　　　個。
(2)實現上述功能的部分Python程序如下,請在劃線處填入合適的代碼。
#讀取貨位總數存入n,代碼略。
cnt1=n
lst=[0]*n　#貨位狀態,0表示對應的貨位為空
while True:
　　#讀取本次已描過數據:箱子類型、操作類型、貨位編號起始值存入t,d和s,代碼略
　　if t=="A":
　　　　w=2
　　①　　　　:
　　　　w=1
　　else:　#不是"A"或"B"時退出循環
　　　　break
　　if d== "P":　#d為P時表示放置,否則表示搬離
　　　　②　　　　
　　else:
　　　　cnt1+=w
　　lst[s]=1-lst[s]
　　if t=="A":
　　　　lst[s+1]=1-lst[s+1]
　　i,cnt2=0,0
　　while i< n-1:
　　　　if lst[i]==0 and lst[i+1]== 0:
　　　　　　③　　　
　　　　　　cnt2+= 1
　　　　i+=1
　　print("當前空貨位數",cnt1,",還可放置A型箱子的最多數量:",cnt2)
答案　(1) 2或兩　(2)①elif t=="B"或elif (t=='B')　②cnt1-=w或cnt1=cnt1 - w　③i +=1或i=i+1
解析　本題考查列表的遍歷。(1)經過放置或搬離操作后,索引位置1-4是空的,6和9是空的,因此可以放置A型箱子2個。(2)① w是兩種箱子所占貨位,因此當輸入是B是占位為1。②cnt1是當前空貨位數,d為P時表示放置,否則表示搬離,條件不成立時,空位增加,因此條件成立時,空位減少。③cnt2表示還可放置A型箱子的最多數量,當條件lst[i]==0 and lst[i+1]== 0成立時,表示可以放置A類型,因此下一個貨位要跳過。
例3 快遞分揀機器人會根據指令將快遞送到指定的位置。某款快遞分揀機器人有“東西南北”四個方向移動的指令,比如指令“西1”表示朝西移動1個單位的距離。機器人的起點位置在(0,0),當服務器下達指令“西3”“北2”“東5”“南7”“東3”后,機器人行走路線如圖a所示。
圖a
根據快遞分揀機器人行走規則,小明編寫程序實現功能如下:程序運行時,輸入機器人的起點坐標位置(輸入x坐標和y坐標并以逗號分隔),根據給定的指令模擬機器人行走,依次輸出機器人經過點的坐標位置,最后輸出終點離起點的直線距離并保留兩位小數。
(1)如果機器人的起點坐標位置為(0,0),執行指令“西1”“北1”“東5”“南3”“東2”后,終點z坐標位置為　　　　。
(2)請在劃線處填入合適的代碼。
d = ['西','北','東','南','東']　#行走方向
s = [3,2,5,7,3]　#行走長度
start = input('請輸入起點坐標位置(逗號分隔):')
for i in range(len(start)):
　　if start[i] == ',':
　　　　①　　　
x0 = int(start[0:pos])
y0 = int(start[pos+1:len(start)])
x,y = x0,y0
②　　　
for i in range(n):
　　if d[i] == '東':
　　　　x = x + s[i]
　　elif d[i] == '西':
　　　　x = x - s[i]
　　elif d[i] == '南':
　　　　y = y - s[i]
　　else:
　　　　③　　　
　　print('(', x ,',' , y,')') 　#輸出經過點的坐標
④　　　
dist = round(dist,2)
print('距離起點的直線距離為',dist)
答案　(1)(6,-2)　(2)①pos = i
②n = len (d)
③y = y+s [i]
④dist =((x-x0)**2+(y-y0 )**2)**0.5
解析　本題考查解析算法。(1)依次經過的坐標為(-1,0),(-1,1),(4,1),(4,-2)(6,-2)。
(2)①輸入起點坐標位置(逗號分隔),找到逗號位置并賦值給pos。②d表示行走方向,需要行走的步子。③方向依次為東南西北,向北y的值增加,x的值不變。④利用兩點公式計算兩點(x0,y0)、(x,y)之間的距離。
變式訓練1　某Python程序段如下:
info=["男",79,"女",97,"女",94,"男",91,"女",85,"女",100,"男",82]
tot=0
c=0
for i in range(0,len(info),2):
　　if info[i]=="男":
　　　　continue
　　tot+=info[i+1]
　　c+=1
print(round(tot/c,1))
運行該程序段,輸出結果是　　　　。
答案　94.0
解析　本題考查循環中continue的相關知識,程序中用到計數器和累計器。男生跳過循環,那么只統計女生的數值,平均數=總計/數量。
例4 我國《算經》中經典的“百錢買百雞”問題,描述如下:雞翁一值錢五,雞母一值錢三,雞雛三值錢一。百錢買百雞,問雞翁、雞母、雞雛各幾何
現A、B、C三位同學分別編寫了計算機程序解決該問題。程序代碼如下,請回答下列問題。
A同學的程序:
na = 0
for x in range(21):
　　for y in range(34):
　　　　for z in range(101):
　　　　　　na += 1
　　　　　　if ①　　　　:
　　　　　　　　print(x,y,z)
B同學的程序:
nb = 0
for x in range(21):
　　for y in range(34):
　　　　nb += 1
　　　　②　　　
　　　　if x * 5 + y * 3 + z / 3 == 100:
　　　　　　print(x,y,z)
C同學的程序:
nc = 0
for x in range(0,21,③　　　　): #劃線③處要求填入后算法效率最高
　　nc += 1
　　y = 25 - 7 * x ∥ 4
　　z = 100 - x - y
　　if x * 15 + y * 9 + z == 300 and y >= 0:
　　　　print(x,y,z)
(1)A、B、C 三位同學解決“百錢買百雞”問題均使用了　　　　(單選,填字母:A.解析 /B. 枚舉)算法。
(2)請在劃線處填入合適的代碼。
(3)程序運行后,變量 na、nb、nc 的大小關系為　　　　(單選:填字母。選項中的表達式均為數學表達式)
A.na=nb=nc B.na>nb>nc
C.nanc
答案　(1)B　(2)①x+y+z==100 and x*5+y*3+z/3==100或者x+y+z==100 and x*15+y*9+z==300　②z=100-x-y　③4　(3)B
解析　本題考查枚舉算法。(1)對每一種解進行判斷,屬于枚舉算法。(2)表達式y=25-7*x∥4,若要保證y是整數,x必須是4的倍數,因此步長為4。(3)循環次數依次為21*34*101、21*34和6次。
變式訓練2　有Python程序段如下,執行該程序段后,變量sum的值為 (　　)
m="p25y3t12h8n5"
sum=t=0
flag=True
for ch in m:
　　if "0"<=ch<="9":
　　　　t=t*10+int(ch)
　　else:
　　　　if flag==True:
　　　　　　sum+=t
　　　　t=0
　　　　flag=not flag
print(sum)
A.53 B.48 C.32 D.11
答案　D
解析　本題考查循環結構的綜合應用。用ch來便遍歷符串m,用t來存儲數字,當找到第一個非數字字符且flag為True時,將t的值累加入sum,只有當遇到非數字字符時才將數字累加入sum,最終sum的值為11,答案為D。
例5 在“三位一體”招生考試中學考成績占據一定的比例。表1為某高校學考等級成績折算表(學考等級分為A、B、C、D、E),少于5A計0分;表2為某學生的學考等級成績單。
表1　某高校學考等級成績折算表
學業水平考試等級 A B C D
成績折算(分) 10 8 6 4
表2　某學生學考等級成績單
科目 語文 數學 英語 物理 化學 生物 政治 歷史 地理 技術
等級 A A A A A B A C B A
編寫Python程序實現學考成績總分折算。表2學生的折合分數如圖所示。
(1)若輸入的學生學考等級為“AAAABBBBCC”,則折合分數為:　　　　。
(2)實現上述功能的Python程序如下,請在劃線處填入合適的代碼。
s=input("請輸入各學科學考等級:")
num=0
scores=0
for t in ①　　　　:
　　if t=="A":
②　　　
scores+=10
　　elif t=="B":
scores+=8
　　elif t=="C":
scores+=6
　　elif t=="D":　#③
scores+=4
if num<5:
　　print("折合分數為0分")
else:
　　print("折合分數為:",scores)
(3)若將③處代碼改為“else:”,對程序運行結果是否有影響 　　　　(選填文字:是/否);并說明理由_______________________________。
答案　(1)0　(2)①s或其他等價答案
②num+=1或num=num+1　(3)是　無法排除“E”情況,“D”“E”統加4分
解析　本題考查枚舉算法。(1)A等的個數為4,少于5,得分為0。(2)從條件t=="A"來看,t可能是AB等等級名稱,因此t是s中某個字符,①處答案為s。從等級成績折算表來看,A等為10分,scores為折算分。少于5A計0分,結合條件num<5來看,num應為A等的個數,②處統計A等個數。(3)題目中對ABC等級分別進行了賦值,等級還有DE的可能性,若直接用else,對E等也進行了賦值,不正確。
變式訓練3　某密碼強度判斷程序功能如下:將密碼字符分為大寫字母、小寫字母、數字字符以及其他符號四種類型。輸入一串密碼字符,如果該字符串的長度小于8,則輸出“密碼長度不符合要求!”;若該字符串包含三種字符及以上,則輸出“強度:強”;若該字符串包含兩種字符,則輸出“強度:中”;若該字符串僅包含一種字符,則輸出“強度:弱”。
(1)實現上述功能的Python程序如下,請補充完整程序代碼。
r =[0]*4;sum=0
s=input("輸入密碼:")
①　　　　　
if n<8:
　　print("密碼長度不符合要求!");
else:
　　for②　　　　　　:
　　　　ch =s[i]
　　　　if ch>="a" and ch<="z":
　　　　　　r[0]=1
　　　　elif ch>="A" and ch<="Z":
　　　　　　r[1]=1
　　　　 ③　　　　　　:
　　　　　　r[2]=1
　　　　else:
　　　　　　r[3]=1
　　　　sum=r[0]+r[1]+r[2]+r[3]
　　　　if sum>=3:　　
　　　　　　print("強度:強")
　　　　elif④　　　　　　:
　　　　　　print("強度:中")
　　　　else:　　
　　　　　　print("強度:弱")
(2)若輸入的密碼字符串為“Asd 237”,則輸出的結果為　　　　。
答案　(1)①n=len(s)　②i in range(0,n,1)或i in range(0,n)或i in range(n)或i in range(len(s))或其它等價表達式　③elif "0"<=ch<="9"或elif ch>="0" and ch<="9"　④sum==2或sum>1或sum>=2
(2)“密碼長度不符合要求!”(雙引號沒有也正確)
解析　本題考查字符串遍歷和多分支選擇結構。(1)在條件語句if n<8中,將判斷密碼的長度,因此①處答案為n=len(s)。對符合長度的密碼進行遍歷,結合語句ch=s[i]來看,變量i是字符串索引值,因此②處通過循環獲取密碼各個字符的索引位置。密碼字符分為大寫字母、小寫字母、數字字符以及其他符號四種類型,因此③中將判斷該字符ch是否屬于數字字符類型。變量sum表示字符類型的種類數量,密碼強度為中,需包含2種類型的字符,在第二分支中,條件sum>=3已經不成立,即sum的值只要大于1或大于等于2即可。(2)密碼字符串“Asd 237”的長度值為7,屬于密碼長度不符合要求。
　　　　　　　　　　　　　　　　
1.有如下Python程序段:
listn=[0]*10
for i in range(len(listn)):
　　if i==0 or i==1:
　　　　listn[i]=1
　　else:
　　　　listn[i]=listn[i-1]+listn[i-2]
執行該程序段后,listn[9]的值為 (　　)
A.55 B.34 C.21 D.0
答案　A
解析　本題考查枚舉算法。滿足條件i==0 or i==1,表示列表前兩項的值為1。從第3項開始,為前兩項之和。
2.某Python程序代碼如下:
a=[10,5,2,11,7,6]
c=0
i=0
while i　　if a[i]%2==0:
　　　　c-=a[i]
a[i]∥=2
　　else:
　　　　c+=a[i]
　　　　i=i+1
print(int(c))
程序執行后,輸出的結果是 (　　)
A.5 B.14 C.23 D.51
答案　B
解析　本題考查枚舉算法。將其中的偶數減去a[i],并將a[i]進行折半,加個奇數。
3.斐波那契數列(Fibonacci sequence),又稱黃金分割數列、因數學家列昂納多·斐波那契(Leonardoda Fibonacci)以兔子繁殖為例子而引入,故又稱為“兔子數列”,指的是這樣一個數列:1、1、2、3、5、8、13、……,即從數列的第三項開始,當前項
為前兩項之和,編寫程序實現求斐波那契數列的第n項的值。
(1)用Python語言編寫的程序如下,請在劃線處填入合適的代碼,實現程序功能。
n=int(input("輸入n的值:"))
a=b=1
for i in range(3,n+1):
c=a+b
①　　　　　
print("第n項為:"+②　　　　　　)
(2)當輸入n=10,則程序輸出的第n項為　　　　。
答案　(1)①a,b=b,c　②str(c)　(2)55
解析　(1)本題采用迭代法求斐波那契數列,斐波那契數列的規律為:從第三項開始,當前項為前兩項之和,因此求出c后,應更新a、b的值為b、c,以便求解數列的下一項,因此①處代碼為a,b=b,c;第n項的值為c,由于print語句輸出時使用了“+”號,因此需使用str函數將c轉換為字符型,即②處代碼為str(c)。
(2)可以根據斐波那契數列的特點推算出,第10項為55。
4.有如下Python程序段:
count=0
for i in range(100,1000,1):
　　if i% 10==i∥100:
　　　　count+=1
執行該程序段后,count的值為　　　　。
答案　90
5.有如下Python程序段:
s="AAACBBBBCBBB"
count=1;cmax=1;last=s[0]
for i in s[1:len(s)]:
　　if last==i:
　　　　count+=1
　　else:
　　　　last=i
　　　　count=1
　　if cmax　　　　cmax=count
執行該程序段后,cmax的值為　　　　。
答案　4
6.某Python程序實現的功能:運行程序輸入一個四位整數,能夠判斷該四位整數是否存在數字重復的位。程序代碼如下:
n=int(input("請輸入一個四位正整數:"))
f=[0]*10
while n>0:
　　y=n%10
　　①　　　
　　n=n∥10
if ②　　　　:
　　print("有重復的位。")
else:
　　print("沒有重復的位。")
劃線處的代碼應填 (　　)
A.①f[y]=1　　 ②sum(f)<4
B.①f[y]+=1 ②sum(f)<4
C.①f[y]=1 ②sum(f)==4
D.①f[y]+=1 ②sum(f)==4
答案　A
解析　本題考查桶的算法思想。表達式n%10的功能是取出個位數,語句n=n ∥ 10的功能是去除個位數。語句f[y]=1的功能是y是否出現過,如果出現為1,沒有出現為0。語句f[y]+=1的功能是統計y出現的次數。sum(f)是統計f列表元素之和。
7.水往低處流,下雨時道路上的低洼地(兩邊高中間低的凹處)總會有積水。例如某地面高度數據為“0,0,2,1,2,0,0,1”,則該地面有 2 處低洼地。實現該算法的程序段如下:
gd=input("請輸入地面高度,以空格間隔開:")
h=list(map(int,gd.split(",")))　#將字符串轉換為列表,例如"1,0,2",轉換為[1,0,2]
cnt=0　　
f=False
for i in range(1,len(h)):
　　if ①　　　　:
　　　　f=True
　　elif h[i-1]　　　　cnt+=1
　　　　②　　　
print("該地面有",cnt,"處低洼地。")
上述代碼中劃線處應填入的代碼是 (　　)
A.①h[i]>h[i+1]　②f=False
B.①h[i]>h[i+1]　②f=True
C.①h[i-1]>h[i]　②f=False
D.①h[i-1]>h[i]　②f=True
答案　C
解析　本題考查在一個序列中查找一個下降子序列。flag是下降段的標志,從索引1開始遍歷,若他比他前面的數小,表示處理下降段,將flag置為True。在下降過程中,若他比他前面的數大,表示從該位置開始處理上升段,因此將增加一個下降段,同時將標志設置為False。
8.m錢買n雞問題。用m元買n只雞,公雞5元一只,母雞3元一只,小雞1元3只,輸出用m錢買n雞的所有方案及方案總數。
編寫程序實現上述功能,程序運行效果如圖所示。
請輸入錢:50請輸入要買的雞的數量:20方案1:3 11 6方案2:7 4 9共有方案數:2
實現上述功能的程序如下,請在劃線處填入合適的代碼。
count=0
m=int(input("請輸入錢:"))
n=int(input("請輸入要買的雞的數量:"))
for i in range(m∥5+1):
　 for j in range(m∥3+1):
　　　k=①　　　　　
　　　if②　　　　　　:
　　　　　 count+=1
　　　　　 print("方案",count,":",i,j,k)
print("共有方案數:",count)
答案　①n-i-j　②5*i+3*j+k/3==m
解析　本題主要考查的是枚舉算法的綜合應用。本題的枚舉對象有兩個,分別是公雞和母雞的數量,i表示公雞的數量,j表示母雞的數量,k表示小雞的數量,已知公雞、母雞和小雞共有n只,因此①處的代碼為n-i-j;如果買公雞、母雞和小雞的錢正好是m元,表示當前的購買方案可行,則進行計數,并輸出購買方案,因此,②處的代碼為5*i+3*j+k/3==m,需注意的是判斷條件不能寫為5*i+3*j+k∥3==m。
　　　　　　　　　　　　　　　　
一、基礎鞏固
1.有如下Python程序段:
str1=input("輸入一組由身高和體重構成的有規律字符串:")
hmax=int(str1[0:3])
wmin=int(str1[4:6])
for i in range(0,len(str1),7):
　　h=int(str1[i:i+3])
　　w=int(str1[i+4:i+6])
　　if h>hmax and w　　　　hmax=h
　　　　wmin=w
運行該程序段,輸入"176/65/169/59/180/62/185/63/"(輸入時,不含前后的雙引號),待程序段結束后,變量hmax、wmin的值分別為 (　　)
A.180　62 B.185　63 C.169　59 D.185　59
答案　A
解析　本題考查枚舉算法。查找一個身高是最高的,同時體重也是最小的。
2.現要通過Python程序輸出所有既是對稱數,又是素數的三位數,比如:101、131、727等(對稱數是它的各位數字是左右對稱的數,素數是除了1和它本身以外,不能被其他任何整數整除的數),其功能實現的Python程序如下:
for num in range(100,　(1)　 ,1):
　　flag1=False
　　flag2=True
　　a=num%10
　　b=　(2)　
　　if a==b:
　　　　flag1=True
　　for i in range(2,num,1):
　　　　if num%i==0:
　　　　　　flag2=　(3)　
　　if flag1 and flag2:
　　　　print(num)
上述程序中劃線處可選語句為:
①999　②1000　③num∥100
④num∥10%10　⑤False　⑥True
為了實現題干描述功能,則(1)(2)(3)劃線處語句依次為 (　　)
A.①④⑥ B.②④⑤ C.②③⑥ D.②③⑤
答案　D
解析　本題考查枚舉算法。查找一個三位數,因此(1)中應為1000,取到的num最大值為999。(2)處b是最高位,因此需整除100。(3)處素數不能被2至num-1之間的數整除,如果除通,則設計標志為False。
3.有如下Python程序,程序執行,輸入數據k之后輸出的結果不正確的是 (　　)
L=[8,10,9,14,13,4,9,13,10]
k=int(input('請輸入k值:'))
j=0
for i in range(8):
　　if L[i]<=k:
　　　　L[j]=L[i]
　　　　j=j+1
print(L[:j])
A.k=8輸出:[8,4]
B.k=9輸出:[8,9,4,9]
C.k=10輸出:[8,10,9,4,9,10]
D.k=13輸出:[8,10,9,13,4,9,13]
答案　C
解析　本題考查循環和分支結構的綜合應用。綜合分析程序可得for循環用循環變量i作為位置來遍歷列表L的前八位元素,當相應位置上的值不大于輸入的k值時,將i位置上的元素賦值到j位置上,并且更新j的的值,若是i位置上的值大于輸入的k值,則不做任何處理,因此可以大致得到該程序的作用是將列表L前八位元素中不大于k的值依次前移并且輸出新列表。C選項中最后一個10的索引值為8,訪問不到,因此錯誤。
4.有如下程序段:
s=input("請輸入字符串:")
count=0
for i in s:
　 　if i>="0" and i<="9":
　　　　 count+=1
print(s[count:count+3])
若輸入的字符串為“AB12CCC222GGBD”則程序運行結果為 (　　)
A.CCC B.GGBD C.CC2 D.C22
答案　C
解析　本題考查枚舉算法,統計數字的個數,count的值為5,因此從索引5至7的字符串。
5.有下列Python程序段:
s="6p25y3t"
sum,t=0,0
flag=True
for ch in s:
　　if "0"<=ch<="9":
　　　　t=t*10+int(ch)
　　else:
　　　　if flag==True:
　　　　　　sum+=t
　　　　t=0
　　　　flag=not flag
執行該程序段后,變量sum的值為 (　　)
A.6 B.9 C.28 D.34
答案　B
解析　本題綜合考查了算法的控制結構,特別是分支結構及循環結構的應用。ch作為循環變量遍歷字符串s,分析內部分支結構可知,當ch取到非數字字符時,t歸零,并結合第一個分支的語句塊可得t用于表示當前通過ch遍歷字符串得到的數字,題中分別為6,25,3,找到非數字字符時修改flag的值為not flag,因此flag的變化過程為T,F,T,F,而只有當flag為True時才會將t的值累加如sum,因此sum=0+6+3=9,選擇B。
6.在一個包含數字和其他非數字字符混合的原始數據中,提取其中的連續數字,當數據中存在多個數字串,以“,”間隔不同數字串。如字符串China86USA1HK852中包含86,1,852三個數字串。
實現該功能的程序代碼如下,請將空白處填寫完整。
s="China86USA1HK852"
ans="";flag=False
for i in s:
　　if ①　　　　 :
　　　　ans+=i
　　　　②　　　　
　　③　　　　 :
　　　　ans+=","
　　　　flag=False
print("提取的數字有:"+ans)
答案　①"0"<=i<="9"　②flag=True
③elif flag
解析　①遍歷字符串s,如果遍歷到數字。②flag是數字串開始的標志,如果是數字則flag值為True。③若不是數字,分為前面是數字和前面不是數字兩種情況。
7.黑洞數。黑洞數是指這樣的整數:由這個數字每位上的數字組成的最大數減去數字組成的最小數,它們的差等于原來的整數。例如3位黑洞數是495,因為954-459=495,4位數字的黑洞數是6174,因為7641-1467=6174。編寫程序,功能如下:輸入整數n,輸出3位~n位整數中的黑洞數。程序運行效果如圖所示。
實現上述功能的程序如下,請在程序劃線處填入合適的代碼。
n=int(input("輸入n:"))
count=0
for x in range(3,n+1):
　 start=10**(x-1)
　 ①　　　　　
　 for i in range(start,end):
#把數字轉換字符后拼接,并按降序排列
maxnum=".join(sorted(str(i),reverse=True))　
minnum=".join(reversed(maxnum))　#將maxnum中字符升序排列后拼接
②　　　　　
　　　if dis==i:
　　　　　print(i)
　　　　　count=count+1
print("count="+③　　　　　　)
答案　①end=10**x　②dis=int(maxnum)-int(minnum)　③str(count)
解析　根據代碼range(start,end)可知,長度為x位的整數范圍為[start,end-1],因此①處代碼end=10**x;②處代碼的功能是求最大數與最小數的差,根據if語句可知,兩數之差存儲在變量dis中,因為maxnum和minnum是數字字符串,所以在求差之前應將其轉換為整數類型,因此,②處代碼為dis=int(maxnum)-int(minnum);count用來計數,統計黑洞數的個數,由于輸出時使用了“+”后,因此需將count轉換為字符串型,即③處代碼為str(count)。
8.某網站要求新注冊用戶的密碼必須以字母開頭,并且含有字母(區分大小寫)、數字和特殊符號(!、@、#、$、%、&、*,7個符號中只要有一個即可),密碼長度為8~18個字符。
下列程序的功能是判斷用戶輸入的密碼是否合法。
password=input("please input password:")
check1=False　#判斷首字符和長度是否滿足要求
check2=False　#判斷數字
check3=False　#判斷特殊字符
ss="!@　#$%&*"
n=len(password)
①　　　　　
if 7　　check1=True
if check1:
　　for i in range(1,n):
　　　　ch=password[i]
　　　　if "0"<=ch<="9":
　　　　　　check2=True
　　　　elif ②　　　　　　:
　　　　　　check3=True
if　③　　　　　　:
　　print("密碼不合法")
else:
　　print("密碼合法")
請回答下列問題。
(1)若輸入的密碼為“mylo@e9”,則判斷結果為　　　　　　。
(2)請在程序劃線處填入合適的代碼。
答案　(1)不合法　(2)①ch=password[0]
②ch in ss　③not(check1 and check2 and check3)
解析　(1)由于密碼“mylo@e9”的長度只有7位,因此判斷結果為“不合法”。(2)check1的作用是判斷首字符和長度是否滿足要求,密碼串的首字符為字符串password中的第一個字符,即password[0],因此①處代碼為ch=password[0];check3的作用是判斷密碼中是否包含特殊字符,特殊字符串存放在ss中,當前判斷的字符為ch,因此②處代碼為ch in ss;當check1、check2和check3的值均為True時,密碼合法,其他情況均為不合法,根據if下面的print語句可知,if條件為密碼不合法時的情況,因此③處代碼為not(check1 and check2 and check3)。
二、能力提升
9.用Python程序實現統計隨機數出現的次數。下面程序的功能是:首先隨機產生30個[10,99]之間的不重復整數,并以每行10個輸出在屏幕上,然后統計[10,19]、[20,29]、…、[90,99]各區間段的整數個數,并輸出統計結果。程序運行效果如圖所示:
實現上述功能的程序如下,回答下列問題。
import random
def check(x):
check=True
if①　　　　　　:
　　　 check=False
　 return check
list1=[]
list2=[0]*10
n=1
while n<=30:
num=random.randint(10,99)
if check(num):
　　　　list1.append(num)
　　　　②　　　　　
　　　　n+=1
print("30個不重復的隨機整數為:")
for i in range(0,30):
　 print(list1[i],end="")
　 if③　　　　　　:
　　 　print()　　　#換行輸出
print("各區間段統計結果為:a")
for i in range(1,10):
　　 if list2[i] =0:
　　 　print(i*10,"-",i*10+9,":",list2[i])
(1)check函數的功能是 　。
(2)請在程序劃線處填入合適的代碼。
答案　(1)check函數的功能是檢查整數x是否與列表list1中的元素重復　
2)①x in list1
②list2[num∥10]+=1或②list2[num∥10]=list2[num∥10]+1　③i%10==9
解析　(1)check函數的功能是檢查整數x是否與列表list1中的元素重復,若重復則返回函數值False,否則返回函數值True。根據check函數的功能可知,①處代碼為x in list1;②處循環的功能是統計各區間段中整數的個數,根據程序最后的for循環可知,區間[10,19]內的數統計在list2[1]中,而該區間內的數整除10的值均為1,其他區間的統計也是如此,因此,②處代碼為list2[num∥10]+=1;③處代碼的功能是以每行10個數輸出隨機整數,由于第一個整數的索引號為0,因此③處代碼為i%10==9,而不是i%10==0。
10.某數據壓縮方法描述如下:
①原始數據中,某數不為 0 且相鄰無重復,壓縮數據用該數據表示;②原始數據中,某數為0 且相鄰無重復,壓縮數據用兩個數表示,第 1 個為 0,第 2 個為 0;③原始數據中,某數據相鄰有重復,壓縮數據用 3 個數表示:第 1 個為 0,第 2 個為重復數的個數,第 3 個為該數本身。
根據上述壓縮方法,對應的解壓縮方法示例如圖所示。
壓縮前的代碼存儲在"壓縮數據.txt"文件中,每兩個壓縮數據間用逗號分隔。編寫該文件每行的數據解壓縮的Python程序代碼。
(1)如果壓縮數據為“23,0,21,66,0,0,77,0,5,0”,則解壓縮數據的個數是　　　　 。
(2)實現上述功能的 Python 程序如下。請在劃線處填入合適代碼。
def jy(a):
　　s=""
　　i=0
　　while i　　　　if a[i]=="0":
　　　　　　if ①　　　　:
　　　　　　　　s+="0"+","
　　　　　　　　i+=2
　　　　　　else:
　　　　　　　　for j in range(int(a[i+1])):
　　　　　　　　　　s+=a[i+2]+","
　　　　　　　　②　　　　
　　　　else:
　　　　　　s+=a[i]+","
　　　　　　i+=1
　　return s[:-1]
f=open("壓縮數據.txt","r",encoding="utf-8")
for i in f:
　　s1=i.split(",\n")
　　③　　　　
print(s2)
答案　(1)29　(2)①a[i+1]=="0"　②i+=3　③s2=jy(s1)
解析　(1)解壓縮后為1個23,21個66,1個0,1個77,5個0,數據個數為1+21+1+1+5=29。(2)①從語句s+="0"+","來看,解壓縮為一個0,某數為0 且相鄰無重復,壓縮數據用兩個數表示,第 1 個為 0,第 2 個為 0;②循環for j用于解壓縮多個字符,因此壓縮用3個單位的數據,因此i將加3。③語句s1= i.split(",\n")是對文件中一行按逗號和換行符進行分隔,并把分隔后的內容保存在列表s1中,因此需調用函數來計算解壓縮后的數據。
11.用英文字母A~D數字字符0~9進行編碼,編碼規則如表所示:
例如,數字字符串“718”的編碼為“BDABCA”。
用Python程序實現上述編碼,功能如下:輸入待編碼的一串數字字符,輸出編碼結果,程序運行界面如圖所示。
實現上述功能的Python程序如下,請回答下列問題:
(1)運行該程序,若輸入的數字字符串為“5736”,則輸出的編碼結果為　　　　　　　　。
(2)請在程序劃線處填入合適的代碼。
def dtob(x):
　 st,r="",0
　 for i in range(4):
　　　 r=x%2
　　　　①　　　　　
　　　　x=x∥2
　　return st
code={'00':'A','01':'B','10':'C','11':'D'}
s=input('請輸入數字字符串:')
result=""
for i in range(len(s)):
　　②　　　　　
　　if "9">=ch>="0":
　　　　ans=dtob(int(ch))
　　　　③　　　　　
　　else:
　　　　break
　　if result!='':
　　　　print('編碼結果為:',result)
　　else:
　　　　print('輸入有誤!')
答案　(1)BBBDADBC
(2)①st=str(r)+st　②ch=s[i]
③result+=code[ans[0:2]]+code[ans[2:4]]或result=result+code[ans[0:2]]+code[ans[2:4]]或result+=code[ans[:2]]+code[ans[2:]]
解析　本題綜合考查了循環結構和分支結構的應用、字符串的切片以及字典的訪問。
(1)按照題意,可以推斷得到5736為BBBDADBC。
(2)通讀程序可得自定義函數的功能是將一個數字轉換為二進制數字,以此作為訪問字典code的鍵,一個數字轉換為四位二進制,前兩位對應一個字符,后兩位對應一個字符,十進制轉換為二進制的方法為除二倒取余,顯然①需要將新產生的余數連接在原有的余數之前,并且r為數字,因此st=str(r)+st,②處后續if語句用到了變量ch進行判斷,因此②對ch進行賦值ch=s[i];③處之前已應用自定義函數得到二進制數字字符串,分為兩部分去得到相應的字符,result+=code[ans[0:2]]+code[ans[2:4]]或其他等價答案。
12.查找與替換。從鍵盤上分別輸入要查找和替換的字符串,對文本文件進行查找與替換,替換后保存到新的文本文件中。
完成查找與替換功能的思路是:首先可從待檢索文本文件“in.txt”逐行讀取文本內容到列表text,然后從鍵盤上輸入查找的字符串key和替換的字符串new,對列表text中的元素逐個進行查找并替換,結果保存到列表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.枚舉算法)。
(2)讀寫文本文件,如下的readfile函數,逐行讀取文本文件數據存入列表并返回。請在劃線處填入合適的代碼。
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文件,代碼略
(3)查找字符串,如下的findstr函數,在字符串line中從begin位置開始查找key在字符串line中的位置,請在劃線處填入合適的代碼。
def findstr(key,line,begin):
　　for i in range(begin, len(line) - len(key) + 1):
　　　　if 　　　　:
　　　　　　return i
　　return -1
(4)替換字符串。如下的replace函數,在字符串line中檢索所有的字符串key并替換為new,請在劃線處填入合適的代碼。
def replace(key,new,line):
　　begin = 0
　　while begin < len(line) - len(key) + 1:
　　　　pos = findstr(key,line,begin)
　　　　if pos == -1:
　　　　　　　　　
　　　　else:
　　　　　　line = line[0:pos] + new + line[pos + len(key) :len(line)]
　　　　　　begin = pos + len(key)
　　return line
答案　(1)B
(2)text
(3)line[i:i+len (key) ]==key
(4)break或begin+=1(共97張PPT)
課時8　解析、枚舉算法及程序實現
第三章　算法的程序實現
1.掌握解析和枚舉算法的基本思想。
2.掌握使用解析和枚舉算法解決實際問題的基本方法,并通過編寫程序實現問題求解。
目 錄
CONTENTS
知識梳理
01
例題精析
02
隨堂檢測
03
鞏固與提升
04
知識梳理
1
一、解析算法的基本思想
解析算法的基本思想是指根據問題的前提條件與所求結果之間的關系,找出求解問題的數學表達式,并通過表達式的計算來實現問題的求解。
二、解析算法解題的基本思路
1.建立正確的數學模型,即得出正確的數學代數式。
2.將數學代數式轉化為Python式子。
三、解析算法程序實現的步驟
1.運用解析算法分析問題,尋找問題中各要素之間的關系,用數學表達式表示它們的關系。
2.寫出解決問題的解析步驟,編寫程序實現,通過運行程序求得問題的正確解。
四、枚舉算法的基本思想
枚舉算法的基本思想是把問題所有可能的解__________,然后判斷每一個列舉出的________是否為正確的解。
枚舉算法常用于解決是否存在或有多少種可能等類型的問題。
五、枚舉算法的基本框架
1.枚舉算法三要素
枚舉范圍、__________、判斷條件。
一一列舉
可能解
枚舉對象
2.基本框架
循環結構
分支結構
枚舉范圍是用來表示枚舉對象存在的一個連續區間,用循環結構語句實現。
判斷條件用來檢測當前枚舉的對象是否為問題的解。
例題精析
2
print(a[v])
A
A.if a[i]==a[i-1]:
　　 c+=1
　　 if c>m:
　　　　m=c
　　　　v=i
　else:
　　 c=1
B.if a[i]==a[i-1]:
　　 c+=1
　　 if c>m:
　　　　m=c
　　　　v=i
　　 else:
　　　　c=1
C.if a[i]==a[i-1]:
　　 c+=1
　else:
　　 if c>m:
　　　　m=c
　　　　v=i-1
　　　　c=1
D.if a[i]==a[i-1]:
　　 c+=1
　else:
　　if c>m:
　　　　m=c
　　　　v=i-1
　　c=1
解析　本題考查一維列表的遍歷和最值的查找。 已排序的列表a有n個整型元素,當條件a[i]==a[i-1]成立時,表示有連續相等的數量c。A選項每找到一個相等的值,求解數量的最大值,并保存此時的索引位置v,若不相等時初始化c的個數為1。B選項初始化c的個數就在兩個不相等的值時。C選項當兩個數相等時進行計數,當兩個數不相等時,進行最值的查找,同時初始c的值為1,但該選項c的初始化發生在找到最大值時。D選項若長度的最大值發生在最后,即該列表最后的幾個數是長度是最大值時,只是在進行計數,并未進行最大值的查找。
例2 某倉庫有一排連續相鄰的貨位,編號依次為0~n-1,用于放置A、B兩種類型的箱子,A型箱子占2個相鄰貨位,B型箱子占1個貨位。編寫程序,根據已完成的放置或搬離操作,輸出空貨位數及還可以放置A型箱子的最多數量(不移動已放置的箱子)。請回答下列問題:
箱子類型 操作類型 貨位編號
B 放置 5
A 放置 2,3
B 放置 0
A 放置 7,8
A 搬離 2,3
(1)若n為10,開始時貨位全空,經過如圖所示的放置或搬離操作后,不移動已放置箱子的情況下,還可放置A型箱子的最多數量為　　　　個。
(2)實現上述功能的部分Python程序如下,請在劃線處填入合適的代碼。
#讀取貨位總數存入n,代碼略。
cnt1=n
lst=[0]*n　#貨位狀態,0表示對應的貨位為空
while True:
　　#讀取本次已描過數據:箱子類型、操作類型、貨位編號起始值存入t,d和s,代碼略
　　if t=="A":
　　　　w=2
　　①　　　　:
　　　　w=1
　　else:　#不是"A"或"B"時退出循環
　　　　break
　　if d== "P":　#d為P時表示放置,否則表示搬離
　　　　②　　　　
　　else:
　　　　cnt1+=w
　　lst[s]=1-lst[s]
　　if t=="A":
　　　　lst[s+1]=1-lst[s+1]
　　i,cnt2=0,0
　　while i< n-1:
　　　　if lst[i]==0 and lst[i+1]== 0:
　　　　　　③　　　
　　　　　　cnt2+= 1
　　　　i+=1
　　print("當前空貨位數",cnt1,",還可放置A型箱子的最多數量:",cnt2)
答案　(1) 2或兩　(2)①elif t=="B"或elif (t=='B')　②cnt1-=w或cnt1=cnt1 - w　③i +=1或i=i+1
解析　本題考查列表的遍歷。(1)經過放置或搬離操作后,索引位置1-4是空的,6和9是空的,因此可以放置A型箱子2個。(2)① w是兩種箱子所占貨位,因此當輸入是B是占位為1。②cnt1是當前空貨位數,d為P時表示放置,否則表示搬離,條件不成立時,空位增加,因此條件成立時,空位減少。③cnt2表示還可放置A型箱子的最多數量,當條件lst[i]==0 and lst[i+1]== 0成立時,表示可以放置A類型,因此下一個貨位要跳過。
例3 快遞分揀機器人會根據指令將快遞送到指定的位置。某款快遞分揀機器人有“東西南北”四個方向移動的指令,比如指令“西1”表示朝西移動1個單位的距離。機器人的起點位置在(0,0),當服務器下達指令“西3”“北2”“東5”“南7”“東3”后,機器人行走路線如圖a所示。
圖a
根據快遞分揀機器人行走規則,小明編寫程序實現功能如下:程序運行時,輸入機器人的起點坐標位置(輸入x坐標和y坐標并以逗號分隔),根據給定的指令模擬機器人行走,依次輸出機器人經過點的坐標位置,最后輸出終點離起點的直線距離并保留兩位小數。
(1)如果機器人的起點坐標位置為(0,0),執行指令“西1”“北1”“東5”“南3”“東2”后,終點z坐標位置為　　　　。
(2)請在劃線處填入合適的代碼。
d = ['西','北','東','南','東']　#行走方向
s = [3,2,5,7,3]　#行走長度
start = input('請輸入起點坐標位置(逗號分隔):')
for i in range(len(start)):
　　if start[i] == ',':
　　　　①　　　
x0 = int(start[0:pos])
y0 = int(start[pos+1:len(start)])
x,y = x0,y0
②　　　
for i in range(n):
　　if d[i] == '東':
　　　　x = x + s[i]
　　elif d[i] == '西':
　　　　x = x - s[i]
　　elif d[i] == '南':
　　　　y = y - s[i]
　　else:
　　　　③　　　
　　print('(', x ,',' , y,')') 　#輸出經過點的坐標
④　　　
dist = round(dist,2)
print('距離起點的直線距離為',dist)
答案　(1)(6,-2)　(2)①pos = i
②n = len (d)
③y = y+s [i]
④dist =((x-x0)**2+(y-y0 )**2)**0.5
解析　本題考查解析算法。(1)依次經過的坐標為(-1,0),(-1,1),(4,1),(4,-2)(6,-2)。(2)①輸入起點坐標位置(逗號分隔),找到逗號位置并賦值給pos。②d表示行走方向,需要行走的步子。③方向依次為東南西北,向北y的值增加,x的值不變。④利用兩點公式計算兩點(x0,y0)、(x,y)之間的距離。
變式訓練1　某Python程序段如下:
info=["男",79,"女",97,"女",94,"男",91,"女",85,"女",100,"男",82]
tot=0
c=0
for i in range(0,len(info),2):
　　if info[i]=="男":
　　　　continue
　　tot+=info[i+1]
　　c+=1
print(round(tot/c,1))
運行該程序段,輸出結果是　　　　。
答案　94.0
解析　本題考查循環中continue的相關知識,程序中用到計數器和累計器。男生跳過循環,那么只統計女生的數值,平均數=總計/數量。
例4 我國《算經》中經典的“百錢買百雞”問題,描述如下:雞翁一值錢五,雞母一值錢三,雞雛三值錢一。百錢買百雞,問雞翁、雞母、雞雛各幾何
現A、B、C三位同學分別編寫了計算機程序解決該問題。程序代碼如下,請回答下列問題。
A同學的程序:
na = 0
for x in range(21):
　　for y in range(34):
　　　　for z in range(101):
　　　　　　na += 1
　　　　　　if ①　　　　:
　　　　　　　　print(x,y,z)
B同學的程序:
nb = 0
for x in range(21):
　　for y in range(34):
　　　　nb += 1
　　　　②　　　
　　　　if x * 5 + y * 3 + z / 3 == 100:
　　　　　　print(x,y,z)
C同學的程序:
nc = 0
for x in range(0,21,③　　　　): #劃線③處要求填入后算法效率最高
　　nc += 1
　　y = 25 - 7 * x ∥ 4
　　z = 100 - x - y
　　if x * 15 + y * 9 + z == 300 and y >= 0:
　　　　print(x,y,z)
(1)A、B、C 三位同學解決“百錢買百雞”問題均使用了　　　　(單選,填字母:A.解析 /B. 枚舉)算法。
(2)請在劃線處填入合適的代碼。
(3)程序運行后,變量 na、nb、nc 的大小關系為　　　　(單選:填字母。選項中的表達式均為數學表達式)
A.na=nb=nc B.na>nb>nc
C.nanc
答案　(1)B　(2)①x+y+z==100 and x*5+y*3+z/3==100或者x+y+z==100 and x*15+y*9+z==300　②z=100-x-y　③4　(3)B
解析　本題考查枚舉算法。(1)對每一種解進行判斷,屬于枚舉算法。(2)表達式y=25-7*x∥4,若要保證y是整數,x必須是4的倍數,因此步長為4。(3)循環次數依次為21*34*101、21*34和6次。
變式訓練2　有Python程序段如下,執行該程序段后,變量sum的值為 (　　)
m="p25y3t12h8n5"
sum=t=0
flag=True
for ch in m:
　　if "0"<=ch<="9":
　　　　t=t*10+int(ch)
　　else:
　　　　if flag==True:
　　　　　　sum+=t
D
　　　　t=0
　　　　flag=not flag
print(sum)
A.53 B.48 C.32 D.11
解析　本題考查循環結構的綜合應用。用ch來便遍歷符串m,用t來存儲數字,當找到第一個非數字字符且flag為True時,將t的值累加入sum,只有當遇到非數字字符時才將數字累加入sum,最終sum的值為11,答案為D。
例5 在“三位一體”招生考試中學考成績占據一定的比例。表1為某高校學考等級成績折算表(學考等級分為A、B、C、D、E),少于5A計0分;表2為某學生的學考等級成績單。
表1　某高校學考等級成績折算表
學業水平考試等級 A B C D
成績折算(分) 10 8 6 4
表2　某學生學考等級成績單
科目 語文 數學 英語 物理 化學 生物 政治 歷史 地理 技術
等級 A A A A A B A C B A
編寫Python程序實現學考成績總分折算。表2學生的折合分數如圖所示。
(1)若輸入的學生學考等級為“AAAABBBBCC”,則折合分數為:　　　　。
(2)實現上述功能的Python程序如下,請在劃線處填入合適的代碼。
s=input("請輸入各學科學考等級:")
num=0
scores=0
for t in ①　　　　:
　　if t=="A":
②　　　
scores+=10
　　elif t=="B":
scores+=8
　　elif t=="C":
scores+=6
　　elif t=="D":　#③
scores+=4
if num<5:
　　print("折合分數為0分")
else:
　　print("折合分數為:",scores)
(3)若將③處代碼改為“else:”,對程序運行結果是否有影響 　　　　(選填文字:是/否);并說明理由_______________________________。
答案　(1)0　(2)①s或其他等價答案
②num+=1或num=num+1　(3)是　無法排除“E”情況,“D”“E”統加4分
解析　本題考查枚舉算法。(1)A等的個數為4,少于5,得分為0。(2)從條件t=="A"來看,t可能是AB等等級名稱,因此t是s中某個字符,①處答案為s。從等級成績折算表來看,A等為10分,scores為折算分。少于5A計0分,結合條件num<5來看,num應為A等的個數,②處統計A等個數。(3)題目中對ABC等級分別進行了賦值,等級還有DE的可能性,若直接用else,對E等也進行了賦值,不正確。
變式訓練3　某密碼強度判斷程序功能如下:將密碼字符分為大寫字母、小寫字母、數字字符以及其他符號四種類型。輸入一串密碼字符,如果該字符串的長度小于8,則輸出“密碼長度不符合要求!”;若該字符串包含三種字符及以上,則輸出“強度:強”;若該字符串包含兩種字符,則輸出“強度:中”;若該字符串僅包含一種字符,則輸出“強度:弱”。
(1)實現上述功能的Python程序如下,請補充完整程序代碼。
r =[0]*4;sum=0
s=input("輸入密碼:")
①　　　　　
if n<8:
　　print("密碼長度不符合要求!");
else:
　　for②　　　　　　:
　　　　ch =s[i]
　　　　if ch>="a" and ch<="z":
　　　　　　r[0]=1
　　　　elif ch>="A" and ch<="Z":
　　　　　　r[1]=1
　　　　 ③　　　　　　:
　　　　　　r[2]=1
　　　　else:
　　　　　　r[3]=1
　　　　sum=r[0]+r[1]+r[2]+r[3]
　　　　if sum>=3:　　
　　　　　　print("強度:強")
　　　　elif④　　　　　　:
　　　　　　print("強度:中")
　　　　else:　　
　　　　　　print("強度:弱")
(2)若輸入的密碼字符串為“Asd 237”,則輸出的結果為　　　　。
答案　(1)①n=len(s)　②i in range(0,n,1)或i in range(0,n)或i in range(n)或i in range(len(s))或其它等價表達式　③elif "0"<=ch<="9"或elif ch>="0" and ch<="9"　④sum==2或sum>1或sum>=2
(2)“密碼長度不符合要求!”(雙引號沒有也正確)
解析　本題考查字符串遍歷和多分支選擇結構。(1)在條件語句if n<8中,將判斷密碼的長度,因此①處答案為n=len(s)。對符合長度的密碼進行遍歷,結合語句ch=s[i]來看,變量i是字符串索引值,因此②處通過循環獲取密碼各個字符的索引位置。密碼字符分為大寫字母、小寫字母、數字字符以及其他符號四種類型,因此③中將判斷該字符ch是否屬于數字字符類型。變量sum表示字符類型的種類數量,密碼強度為中,需包含2種類型的字符,在第二分支中,條件sum>=3已經不成立,即sum的值只要大于1或大于等于2即可。(2)密碼字符串“Asd 237”的長度值為7,屬于密碼長度不符合要求。
隨堂檢測
3
1.有如下Python程序段:
listn=[0]*10
for i in range(len(listn)):
　　if i==0 or i==1:
　　　　listn[i]=1
　　else:
　　　　listn[i]=listn[i-1]+listn[i-2]
執行該程序段后,listn[9]的值為(　　)
A.55 B.34 C.21 D.0
A
解析　本題考查枚舉算法。滿足條件i==0 or i==1,表示列表前兩項的值為1。從第3項開始,為前兩項之和。
2.某Python程序代碼如下:
a=[10,5,2,11,7,6]
c=0
i=0
while i　　if a[i]%2==0:
　　　　c-=a[i]
a[i]∥=2
　　else:
　　　　c+=a[i]
　　　　i=i+1
print(int(c))
程序執行后,輸出的結果是(　　)
A.5 B.14 C.23 D.51
解析　本題考查枚舉算法。將其中的偶數減去a[i],并將a[i]進行折半,加個奇數。
B
3.斐波那契數列(Fibonacci sequence),又稱黃金分割數列、因數學家列昂納多·斐波那契(Leonardoda Fibonacci)以兔子繁殖為例子而引入,故又稱為“兔子數列”,指的是這樣一個數列:1、1、2、3、5、8、13、……,即從數列的第三項開始,當前項
為前兩項之和,編寫程序實現求斐波那契數列的第n項的值。
(1)用Python語言編寫的程序如下,請在劃線處填入合適的代碼,實現程序功能。
n=int(input("輸入n的值:"))
a=b=1
for i in range(3,n+1):
c=a+b
①　　　　　
print("第n項為:"+②　　　　　　)
(2)當輸入n=10,則程序輸出的第n項為　　　　。
答案　(1)①a,b=b,c　②str(c)　(2)55
解析　(1)本題采用迭代法求斐波那契數列,斐波那契數列的規律為:從第三項開始,當前項為前兩項之和,因此求出c后,應更新a、b的值為b、c,以便求解數列的下一項,因此①處代碼為a,b=b,c;第n項的值為c,由于print語句輸出時使用了“+”號,因此需使用str函數將c轉換為字符型,即②處代碼為str(c)。
(2)可以根據斐波那契數列的特點推算出,第10項為55。
4.有如下Python程序段:
count=0
for i in range(100,1000,1):
　　if i% 10==i∥100:
　　　　count+=1
執行該程序段后,count的值為　　　　。
答案　90
5.有如下Python程序段:
s="AAACBBBBCBBB"
count=1;cmax=1;last=s[0]
for i in s[1:len(s)]:
　　if last==i:
　　　　count+=1
　　else:
　　　　last=i
　　　　count=1
　　if cmax　　　　cmax=count
執行該程序段后,cmax的值為　　　　。
答案　4
6.某Python程序實現的功能:運行程序輸入一個四位整數,能夠判斷該四位整數是否存在數字重復的位。程序代碼如下:
n=int(input("請輸入一個四位正整數:"))
f=[0]*10
while n>0:
　　y=n%10
　　①　　　
　　n=n∥10
if ②　　　　:
　　print("有重復的位。")
else:
　　print("沒有重復的位。")
劃線處的代碼應填(　　)
A.①f[y]=1　　 ②sum(f)<4
B.①f[y]+=1 ②sum(f)<4
C.①f[y]=1 ②sum(f)==4
D.①f[y]+=1 ②sum(f)==4
A
解析　本題考查桶的算法思想。表達式n%10的功能是取出個位數,語句n=n ∥ 10的功能是去除個位數。語句f[y]=1的功能是y是否出現過,如果出現為1,沒有出現為0。語句f[y]+=1的功能是統計y出現的次數。sum(f)是統計f列表元素之和。
7.水往低處流,下雨時道路上的低洼地(兩邊高中間低的凹處)總會有積水。例如某地面高度數據為“0,0,2,1,2,0,0,1”,則該地面有 2 處低洼地。實現該算法的程序段如下:
gd=input("請輸入地面高度,以空格間隔開:")
h=list(map(int,gd.split(",")))　#將字符串轉換為列表,例如"1,0,2",轉換為[1,0,2]
cnt=0　　
f=False
for i in range(1,len(h)):
　　if ①　　　　:
　　　　f=True
　　elif h[i-1]　　　　cnt+=1
　　　　②　　　
print("該地面有",cnt,"處低洼地。")
上述代碼中劃線處應填入的代碼是(　　)
A.①h[i]>h[i+1]　②f=False
B.①h[i]>h[i+1]　②f=True
C.①h[i-1]>h[i]　②f=False
D.①h[i-1]>h[i]　②f=True
C
解析　本題考查在一個序列中查找一個下降子序列。flag是下降段的標志,從索引1開始遍歷,若他比他前面的數小,表示處理下降段,將flag置為True。在下降過程中,若他比他前面的數大,表示從該位置開始處理上升段,因此將增加一個下降段,同時將標志設置為False。
8.m錢買n雞問題。用m元買n只雞,公雞5元一只,母雞3元一只,小雞1元3只,輸出用m錢買n雞的所有方案及方案總數。
編寫程序實現上述功能,程序運行效果如圖所示。
請輸入錢:50
請輸入要買的雞的數量:20
方案1:3 11 6
方案2:7 4 9
共有方案數:2
實現上述功能的程序如下,請在劃線處填入合適的代碼。
count=0
m=int(input("請輸入錢:"))
n=int(input("請輸入要買的雞的數量:"))
for i in range(m∥5+1):
　 for j in range(m∥3+1):
　　　k=①　　　　　
　　　if②　　　　　　:
　　　　　 count+=1
　　　　　 print("方案",count,":",i,j,k)
print("共有方案數:",count)
答案　①n-i-j　②5*i+3*j+k/3==m
解析　本題主要考查的是枚舉算法的綜合應用。本題的枚舉對象有兩個,分別是公雞和母雞的數量,i表示公雞的數量,j表示母雞的數量,k表示小雞的數量,已知公雞、母雞和小雞共有n只,因此①處的代碼為n-i-j;如果買公雞、母雞和小雞的錢正好是m元,表示當前的購買方案可行,則進行計數,并輸出購買方案,因此,②處的代碼為5*i+3*j+k/3==m,需注意的是判斷條件不能寫為5*i+3*j+k∥3==m。
4
鞏固與提升
基礎鞏固
能力提升
1.有如下Python程序段:
str1=input("輸入一組由身高和體重構成的有規律字符串:")
hmax=int(str1[0:3])
wmin=int(str1[4:6])
for i in range(0,len(str1),7):
　　h=int(str1[i:i+3])
　　w=int(str1[i+4:i+6])
　　if h>hmax and w　　　　hmax=h
　　　　wmin=w
運行該程序段,輸入"176/65/169/59/180/62/185/63/"(輸入時,不含前后的雙引號),待程序段結束后,變量hmax、wmin的值分別為 (　　)
A.180　62 B.185　63
C.169　59 D.185　59
解析　本題考查枚舉算法。查找一個身高是最高的,同時體重也是最小的。
A
2.現要通過Python程序輸出所有既是對稱數,又是素數的三位數,比如:101、131、727等(對稱數是它的各位數字是左右對稱的數,素數是除了1和它本身以外,不能被其他任何整數整除的數),其功能實現的Python程序如下:
for num in range(100,　(1)　 ,1):
　　flag1=False
　　flag2=True
　　a=num%10
　　b=　(2)　
　　if a==b:
　　　　flag1=True
　　for i in range(2,num,1):
　　　　if num%i==0:
　　　　　　flag2=　(3)　
　　if flag1 and flag2:
　　　　print(num)
上述程序中劃線處可選語句為:
①999　②1000　③num∥100
④num∥10%10　⑤False　⑥True
為了實現題干描述功能,則(1)(2)(3)劃線處語句依次為(　　)
A.①④⑥ B.②④⑤ C.②③⑥ D.②③⑤
D
解析　本題考查枚舉算法。查找一個三位數,因此(1)中應為1000,取到的num最大值為999。(2)處b是最高位,因此需整除100。(3)處素數不能被2至num-1之間的數整除,如果除通,則設計標志為False。
3.有如下Python程序,程序執行,輸入數據k之后輸出的結果不正確的是 (　　)
L=[8,10,9,14,13,4,9,13,10]
k=int(input('請輸入k值:'))
j=0
for i in range(8):
　　if L[i]<=k:
　　　　L[j]=L[i]
　　　　j=j+1
print(L[:j])
A.k=8輸出:[8,4] B.k=9輸出:[8,9,4,9]
C.k=10輸出:[8,10,9,4,9,10] D.k=13輸出:[8,10,9,13,4,9,13]
C
解析　本題考查循環和分支結構的綜合應用。綜合分析程序可得for循環用循環變量i作為位置來遍歷列表L的前八位元素,當相應位置上的值不大于輸入的k值時,將i位置上的元素賦值到j位置上,并且更新j的的值,若是i位置上的值大于輸入的k值,則不做任何處理,因此可以大致得到該程序的作用是將列表L前八位元素中不大于k的值依次前移并且輸出新列表。C選項中最后一個10的索引值為8,訪問不到,因此錯誤。
4.有如下程序段:
s=input("請輸入字符串:")
count=0
for i in s:
　 　if i>="0" and i<="9":
　　　　 count+=1
print(s[count:count+3])
若輸入的字符串為“AB12CCC222GGBD”則程序運行結果為(　　)
A.CCC B.GGBD C.CC2 D.C22
C
解析　本題考查枚舉算法,統計數字的個數,count的值為5,因此從索引5至7的字符串。
5.有下列Python程序段:
s="6p25y3t"
sum,t=0,0
flag=True
for ch in s:
　　if "0"<=ch<="9":
　　　　t=t*10+int(ch)
　　else:
　　　　if flag==True:
　　　　　　sum+=t
　　　　t=0
　　　　flag=not flag
執行該程序段后,變量sum的值為 (　　)
A.6 B.9 C.28 D.34
解析　本題綜合考查了算法的控制結構,特別是分支結構及循環結構的應用。ch作為循環變量遍歷字符串s,分析內部分支結構可知,當ch取到非數字字符時,t歸零,并結合第一個分支的語句塊可得t用于表示當前通過ch遍歷字符串得到的數字,題中分別為6,25,3,找到非數字字符時修改flag的值為not flag,因此flag的變化過程為T,F,T,F,而只有當flag為True時才會將t的值累加如sum,因此sum=0+6+3=9,選擇B。
B
6.在一個包含數字和其他非數字字符混合的原始數據中,提取其中的連續數字,當數據中存在多個數字串,以“,”間隔不同數字串。如字符串China86USA1HK852中包含86,1,852三個數字串。
實現該功能的程序代碼如下,請將空白處填寫完整。
s="China86USA1HK852"
ans="";flag=False
for i in s:
　　if ①　　　　 :
　　　　ans+=i
　　　　②　　　　
　　③　　　　 :
　　　　ans+=","
　　　　flag=False
print("提取的數字有:"+ans)
答案　①"0"<=i<="9"　②flag=True
③elif flag
解析　①遍歷字符串s,如果遍歷到數字。②flag是數字串開始的標志,如果是數字則flag值為True。③若不是數字,分為前面是數字和前面不是數字兩種情況。
7.黑洞數。黑洞數是指這樣的整數:由這個數字每位上的數字組成的最大數減去數字組成的最小數,它們的差等于原來的整數。例如3位黑洞數是495,因為954-459=495,4位數字的黑洞數是6174,因為7641-1467=6174。編寫程序,功能如下:輸入整數n,輸出3位~n位整數中的黑洞數。程序運行效果如圖所示。
實現上述功能的程序如下,請在程序劃線處填入合適的代碼。
n=int(input("輸入n:"))
count=0
for x in range(3,n+1):
　 start=10**(x-1)
　 ①　　　　　
　 for i in range(start,end):
#把數字轉換字符后拼接,并按降序排列
maxnum=".join(sorted(str(i),reverse=True))　
minnum=".join(reversed(maxnum))　#將maxnum中字符升序排列后拼接
②　　　　　
　　　if dis==i:
　　　　　print(i)
　　　　　count=count+1
print("count="+③　　　　　　)
答案　①end=10**x　②dis=int(maxnum)-int(minnum)　③str(count)
解析　根據代碼range(start,end)可知,長度為x位的整數范圍為[start,end-1],因此①處代碼end=10**x;②處代碼的功能是求最大數與最小數的差,根據if語句可知,兩數之差存儲在變量dis中,因為maxnum和minnum是數字字符串,所以在求差之前應將其轉換為整數類型,因此,②處代碼為dis=int(maxnum)-int(minnum);count用來計數,統計黑洞數的個數,由于輸出時使用了“+”后,因此需將count轉換為字符串型,即③處代碼為str(count)。
8.某網站要求新注冊用戶的密碼必須以字母開頭,并且含有字母(區分大小寫)、數字和特殊符號(!、@、#、$、%、&、*,7個符號中只要有一個即可),密碼長度為8~18個字符。
下列程序的功能是判斷用戶輸入的密碼是否合法。
password=input("please input password:")
check1=False　#判斷首字符和長度是否滿足要求
check2=False　#判斷數字
check3=False　#判斷特殊字符
ss="!@　#$%&*"
n=len(password)
①　　　　　
if 7　　check1=True
if check1:
　　for i in range(1,n):
　　　　ch=password[i]
　　　　if "0"<=ch<="9":
　　　　　　check2=True
　　　　elif ②　　　　　　:
　　　　　　check3=True
if　③　　　　　　:
　　print("密碼不合法")
else:
　　print("密碼合法")
請回答下列問題。
(1)若輸入的密碼為“mylo@e9”,則判斷結果為　　　　　　。
(2)請在程序劃線處填入合適的代碼。
答案　(1)不合法　(2)①ch=password[0]
②ch in ss　③not(check1 and check2 and check3)
解析　(1)由于密碼“mylo@e9”的長度只有7位,因此判斷結果為“不合法”。(2)check1的作用是判斷首字符和長度是否滿足要求,密碼串的首字符為字符串password中的第一個字符,即password[0],因此①處代碼為ch=password[0];check3的作用是判斷密碼中是否包含特殊字符,特殊字符串存放在ss中,當前判斷的字符為ch,因此②處代碼為ch in ss;當check1、check2和check3的值均為True時,密碼合法,其他情況均為不合法,根據if下面的print語句可知,if條件為密碼不合法時的情況,因此③處代碼為not(check1 and check2 and check3)。
9.用Python程序實現統計隨機數出現的次數。下面程序的功能是:首先隨機產生30個[10,99]之間的不重復整數,并以每行10個輸出在屏幕上,然后統計[10,19]、[20,29]、…、[90,99]各區間段的整數個數,并輸出統計結果。程序運行效果如圖所示:
實現上述功能的程序如下,回答下列問題。
import random
def check(x):
check=True
if①　　　　　　:
　　　 check=False
　 return check
list1=[]
list2=[0]*10
n=1
while n<=30:
num=random.randint(10,99)
if check(num):
　　　　list1.append(num)
　　　　②　　　　　
　　　　n+=1
print("30個不重復的隨機整數為:")
for i in range(0,30):
　 print(list1[i],end="")
　 if③　　　　　　:
　　 　print()　　　#換行輸出
print("各區間段統計結果為:a")
for i in range(1,10):
　　 if list2[i] =0:
　　 　print(i*10,"-",i*10+9,":",list2[i])
(1)check函數的功能是　。
(2)請在程序劃線處填入合適的代碼。
答案　(1)check函數的功能是檢查整數x是否與列表list1中的元素重復　
(2)①x in list1 ②list2[num∥10]+=1或②list2[num∥10]=list2[num∥10]+1　
③i%10==9
解析　(1)check函數的功能是檢查整數x是否與列表list1中的元素重復,若重復則返回函數值False,否則返回函數值True。根據check函數的功能可知,①處代碼為x in list1;②處循環的功能是統計各區間段中整數的個數,根據程序最后的for循環可知,區間[10,19]內的數統計在list2[1]中,而該區間內的數整除10的值均為1,其他區間的統計也是如此,因此,②處代碼為list2[num∥10]+=1;③處代碼的功能是以每行10個數輸出隨機整數,由于第一個整數的索引號為0,因此③處代碼為i%10==9,而不是i%10==0。
10.某數據壓縮方法描述如下:
①原始數據中,某數不為 0 且相鄰無重復,壓縮數據用該數據表示;②原始數據中,某數為0 且相鄰無重復,壓縮數據用兩個數表示,第 1 個為 0,第 2 個為 0;③原始數據中,某數據相鄰有重復,壓縮數據用 3 個數表示:第 1 個為 0,第 2 個為重復數的個數,第 3 個為該數本身。
根據上述壓縮方法,對應的解壓縮方法示例如圖所示。
壓縮前的代碼存儲在"壓縮數據.txt"文件中,每兩個壓縮數據間用逗號分隔。編寫該文件每行的數據解壓縮的Python程序代碼。
(1)如果壓縮數據為“23,0,21,66,0,0,77,0,5,0”,則解壓縮數據的個數是　　　　 。
(2)實現上述功能的 Python 程序如下。請在劃線處填入合適代碼。
def jy(a):
　　s=""
　　i=0
　　while i　　　　if a[i]=="0":
　　　　　　if ①　　　　:
　　　　　　　　s+="0"+","
　　　　　　　　i+=2
　　　　　　else:
　　　　　　　　for j in range(int(a[i+1])):
　　　　　　　　　　s+=a[i+2]+","
　　　　　　　　②　　　　
　　　　else:
　　　　　　s+=a[i]+","
　　　　　　i+=1
　　return s[:-1]
f=open("壓縮數據.txt","r",encoding="utf-8")
for i in f:
　　s1=i.split(",\n")
　　③　　　　
print(s2)
答案　(1)29　(2)①a[i+1]=="0"　②i+=3　③s2=jy(s1)
解析　(1)解壓縮后為1個23,21個66,1個0,1個77,5個0,數據個數為1+21+1+1+5=29。(2)①從語句s+="0"+","來看,解壓縮為一個0,某數為0 且相鄰無重復,壓縮數據用兩個數表示,第 1 個為 0,第 2 個為 0;②循環for j用于解壓縮多個字符,因此壓縮用3個單位的數據,因此i將加3。③語句s1= i.split(",\n")是對文件中一行按逗號和換行符進行分隔,并把分隔后的內容保存在列表s1中,因此需調用函數來計算解壓縮后的數據。
11.用英文字母A~D數字字符0~9進行編碼,編碼規則如表所示:
例如,數字字符串“718”的編碼為“BDABCA”。
用Python程序實現上述編碼,功能如下:輸入待編碼的一串數字字符,輸出編碼結果,程序運行界面如圖所示。
實現上述功能的Python程序如下,請回答下列問題:
(1)運行該程序,若輸入的數字字符串為“5736”,則輸出的編碼結果為　　　　　　　　。
(2)請在程序劃線處填入合適的代碼。
def dtob(x):
　 st,r="",0
　 for i in range(4):
　　　 r=x%2
　　　　①　　　　　
　　　　x=x∥2
　　return st
code={'00':'A','01':'B','10':'C','11':'D'}
s=input('請輸入數字字符串:')
result=""
for i in range(len(s)):
　　②　　　　　
　　if "9">=ch>="0":
　　　　ans=dtob(int(ch))
　　　　③　　　　　
　else:
　　　　break
　　if result!='':
　　　　print('編碼結果為:',result)
　　else:
　　　　print('輸入有誤!')
答案　(1)BBBDADBC
(2)①st=str(r)+st　②ch=s[i]
③result+=code[ans[0:2]]+code[ans[2:4]]或result=result+code[ans[0:2]]+code[ans[2:4]]或result+=code[ans[:2]]+code[ans[2:]]
解析　本題綜合考查了循環結構和分支結構的應用、字符串的切片以及字典的訪問。
(1)按照題意,可以推斷得到5736為BBBDADBC。
(2)通讀程序可得自定義函數的功能是將一個數字轉換為二進制數字,以此作為訪問字典code的鍵,一個數字轉換為四位二進制,前兩位對應一個字符,后兩位對應一個字符,十進制轉換為二進制的方法為除二倒取余,顯然①需要將新產生的余數連接在原有的余數之前,并且r為數字,因此st=str(r)+st,②處后續if語句用到了變量ch進行判斷,因此②對ch進行賦值ch=s[i];③處之前已應用自定義函數得到二進制數字字符串,分為兩部分去得到相應的字符,result+=code[ans[0:2]]+code[ans[2:4]]或其他等價答案。
12.查找與替換。從鍵盤上分別輸入要查找和替換的字符串,對文本文件進行查找與替換,替換后保存到新的文本文件中。
完成查找與替換功能的思路是:首先可從待檢索文本文件“in.txt”逐行讀取文本內容到列表text,然后從鍵盤上輸入查找的字符串key和替換的字符串new,對列表text中的元素逐個進行查找并替換,結果保存到列表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.枚舉算法)。
(2)讀寫文本文件,如下的readfile函數,逐行讀取文本文件數據存入列表并返回。請在劃線處填入合適的代碼。
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文件,代碼略
(3)查找字符串,如下的findstr函數,在字符串line中從begin位置開始查找key在字符串line中的位置,請在劃線處填入合適的代碼。
def findstr(key,line,begin):
　　for i in range(begin, len(line) - len(key) + 1):
　　　　if 　　　　:
　　　　　　return i
　　return -1
(4)替換字符串。如下的replace函數,在字符串line中檢索所有的字符串key并替換為new,請在劃線處填入合適的代碼。
def replace(key,new,line):
　　begin = 0
　　while begin < len(line) - len(key) + 1:
　　　　pos = findstr(key,line,begin)
　　　　if pos == -1:
　　　　　　　　　
　　　　else:
　　　　　　line = line[0:pos] + new + line[pos + len(key) :len(line)]
　　　　　　begin = pos + len(key)
　　return line
答案　(1)B
(2)text
(3)line[i:i+len (key) ]==key
(4)break或begin+=1課時8　解析、枚舉算法及程序實現
課時目標
1.掌握解析和枚舉算法的基本思想。2.掌握使用解析和枚舉算法解決實際問題的基本方法，并通過編寫程序實現問題求解。
一、解析算法的基本思想
解析算法的基本思想是指根據問題的前提條件與所求結果之間的關系，找出求解問題的數學表達式，并通過表達式的計算來實現問題的求解。
二、解析算法解題的基本思路
1.建立正確的數學模型，即得出正確的數學代數式。
2.將數學代數式轉化為Python式子。
三、解析算法程序實現的步驟
1.運用解析算法分析問題，尋找問題中各要素之間的關系，用數學表達式表示它們的關系。
2.寫出解決問題的解析步驟，編寫程序實現，通過運行程序求得問題的正確解。
四、枚舉算法的基本思想
枚舉算法的基本思想是把問題所有可能的解________________，然后判斷每一個列舉出的________是否為正確的解。
枚舉算法常用于解決是否存在或有多少種可能等類型的問題。
五、枚舉算法的基本框架
1.枚舉算法三要素
枚舉范圍、____________、判斷條件。
2.基本框架
循環結構
分支結構
枚舉范圍是用來表示枚舉對象存在的一個連續區間，用循環結構語句實現。
判斷條件用來檢測當前枚舉的對象是否為問題的解。
例1 已排序的列表a有n個整型元素,現要查找出現次數最多的值并輸出。若出現次數最多的值有多個,則輸出最前面的一個。實現該功能的程序段如下,方框中應填入的正確代碼為 (　　)
c,m,v =1,1,0
for i in range(1,n):
　　　　
print(a[v])
A.if a[i]==a[i-1]:
　　 c+=1
　　 if c>m:
　　　　m=c
　　　　v=i
　else:
　　 c=1
B.if a[i]==a[i-1]:
　　 c+=1
　　 if c>m:
　　　　m=c
　　　　v=i
　　 else:
　　　　c=1
C.if a[i]==a[i-1]:
　　 c+=1
　else:
　　 if c>m:
　　　　m=c
　　　　v=i-1
　　　　c=1
D.if a[i]==a[i-1]:
　　 c+=1
　else:
　　if c>m:
　　　　m=c
　　　　v=i-1
　　c=1
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
例2 某倉庫有一排連續相鄰的貨位，編號依次為0～n－1，用于放置A、B兩種類型的箱子，A型箱子占2個相鄰貨位，B型箱子占1個貨位。編寫程序，根據已完成的放置或搬離操作，輸出空貨位數及還可以放置A型箱子的最多數量(不移動已放置的箱子)。請回答下列問題：
箱子類型 操作類型 貨位編號
B 放置 5
A 放置 2，3
B 放置 0
A 放置 7，8
A 搬離 2，3
(1)若n為10,開始時貨位全空,經過如圖所示的放置或搬離操作后,不移動已放置箱子的情況下,還可放置A型箱子的最多數量為　　　　個。
(2)實現上述功能的部分Python程序如下,請在劃線處填入合適的代碼。
#讀取貨位總數存入n,代碼略。
cnt1=n
lst=[0]*n　#貨位狀態,0表示對應的貨位為空
while True:
　　#讀取本次已描過數據:箱子類型、操作類型、貨位編號起始值存入t,d和s,代碼略
　　if t=="A":
　　　　w=2
　　①　　　　:
　　　　w=1
　　else:　#不是"A"或"B"時退出循環
　　　　break
　　if d== "P":　#d為P時表示放置,否則表示搬離
　　　　②　　　　
　　else:
　　　　cnt1+=w
　　lst[s]=1-lst[s]
　　if t=="A":
　　　　lst[s+1]=1-lst[s+1]
　　i,cnt2=0,0
　　while i< n-1:
　　　　if lst[i]==0 and lst[i+1]== 0:
　　　　　　③　　　
　　　　　　cnt2+= 1
　　　　i+=1
　　print("當前空貨位數",cnt1,",還可放置A型箱子的最多數量:",cnt2)
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
例3 快遞分揀機器人會根據指令將快遞送到指定的位置。某款快遞分揀機器人有“東西南北”四個方向移動的指令，比如指令“西1”表示朝西移動1個單位的距離。機器人的起點位置在(0，0)，當服務器下達指令“西3”“北2”“東5”“南7”“東3”后，機器人行走路線如圖a所示。
圖a
根據快遞分揀機器人行走規則，小明編寫程序實現功能如下：程序運行時，輸入機器人的起點坐標位置(輸入x坐標和y坐標并以逗號分隔)，根據給定的指令模擬機器人行走，依次輸出機器人經過點的坐標位置，最后輸出終點離起點的直線距離并保留兩位小數。
請輸入起點坐標位置(逗號分隔)：0，0(－3，0)(－3，2)(2，2)(2，－5)(5，－5)距離起點的直線距離為7.07
(1)如果機器人的起點坐標位置為(0,0),執行指令“西1”“北1”“東5”“南3”“東2”后,終點z坐標位置為　　　　。
(2)請在劃線處填入合適的代碼。
d = ['西','北','東','南','東']　#行走方向
s = [3,2,5,7,3]　#行走長度
start = input('請輸入起點坐標位置(逗號分隔):')
for i in range(len(start)):
　　if start[i] == ',':
　　　　①　　　
x0 = int(start[0:pos])
y0 = int(start[pos+1:len(start)])
x,y = x0,y0
②　　　
for i in range(n):
　　if d[i] == '東':
　　　　x = x + s[i]
　　elif d[i] == '西':
　　　　x = x - s[i]
　　elif d[i] == '南':
　　　　y = y - s[i]
　　else:
　　　　③　　　
　　print('(', x ,',' , y,')') 　#輸出經過點的坐標
④　　　
dist = round(dist,2)
print('距離起點的直線距離為',dist)
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練1　某Python程序段如下：
info=["男",79,"女",97,"女",94,"男",91,"女",85,"女",100,"男",82]
tot=0
c=0
for i in range(0,len(info),2):
　　if info[i]=="男":
　　　　continue
　　tot+=info[i+1]
　　c+=1
print(round(tot/c,1))
運行該程序段,輸出結果是　　　　。
例4 我國《算經》中經典的“百錢買百雞”問題,描述如下:雞翁一值錢五,雞母一值錢三,雞雛三值錢一。百錢買百雞,問雞翁、雞母、雞雛各幾何
現A、B、C三位同學分別編寫了計算機程序解決該問題。程序代碼如下,請回答下列問題。
A同學的程序:
na = 0
for x in range(21):
　　for y in range(34):
　　　　for z in range(101):
　　　　　　na += 1
　　　　　　if ①　　　　:
　　　　　　　　print(x,y,z)
B同學的程序:
nb = 0
for x in range(21):
　　for y in range(34):
　　　　nb += 1
　　　　②　　　
　　　　if x * 5 + y * 3 + z / 3 == 100:
　　　　　　print(x,y,z)
C同學的程序:
nc = 0
for x in range(0,21,③　　　　): #劃線③處要求填入后算法效率最高
　　nc += 1
　　y = 25 - 7 * x ∥ 4
　　z = 100 - x - y
　　if x * 15 + y * 9 + z == 300 and y >= 0:
　　　　print(x,y,z)
(1)A、B、C 三位同學解決“百錢買百雞”問題均使用了　　　　(單選,填字母:A.解析 /B. 枚舉)算法。
(2)請在劃線處填入合適的代碼。
(3)程序運行后,變量 na、nb、nc 的大小關系為　　　　(單選:填字母。選項中的表達式均為數學表達式)
A.na=nb=nc B.na>nb>nc
C.nanc
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練2　有Python程序段如下,執行該程序段后,變量sum的值為 (　　)
m="p25y3t12h8n5"
sum=t=0
flag=True
for ch in m:
　　if "0"<=ch<="9":
　　　　t=t*10+int(ch)
　　else:
　　　　if flag==True:
　　　　　　sum+=t
　　　　t=0
　　　　flag=not flag
print(sum)
A.53 B.48 C.32 D.11
例5 在“三位一體”招生考試中學考成績占據一定的比例。表1為某高校學考等級成績折算表(學考等級分為A、B、C、D、E),少于5A計0分;表2為某學生的學考等級成績單。
表1　某高校學考等級成績折算表
學業水平考試等級 A B C D
成績折算(分) 10 8 6 4
表2　某學生學考等級成績單
科目 語文 數學 英語 物理 化學 生物 政治 歷史 地理 技術
等級 A A A A A B A C B A
編寫Python程序實現學考成績總分折算。表2學生的折合分數如圖所示。
(1)若輸入的學生學考等級為“AAAABBBBCC”,則折合分數為:　　　　。
(2)實現上述功能的Python程序如下,請在劃線處填入合適的代碼。
s=input("請輸入各學科學考等級:")
num=0
scores=0
for t in ①　　　　:
　　if t=="A":
②　　　
scores+=10
　　elif t=="B":
scores+=8
　　elif t=="C":
scores+=6
　　elif t=="D":　#③
scores+=4
if num<5:
　　print("折合分數為0分")
else:
　　print("折合分數為:",scores)
(3)若將③處代碼改為“else:”,對程序運行結果是否有影響 　　　　(選填文字:是/否);并說明理由_______________________________。
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練3　某密碼強度判斷程序功能如下:將密碼字符分為大寫字母、小寫字母、數字字符以及其他符號四種類型。輸入一串密碼字符,如果該字符串的長度小于8,則輸出“密碼長度不符合要求!”;若該字符串包含三種字符及以上,則輸出“強度:強”;若該字符串包含兩種字符,則輸出“強度:中”;若該字符串僅包含一種字符,則輸出“強度:弱”。
(1)實現上述功能的Python程序如下,請補充完整程序代碼。
r =[0]*4;sum=0
s=input("輸入密碼:")
①　　　　　
if n<8:
　　print("密碼長度不符合要求!");
else:
　　for②　　　　　　:
　　　　ch =s[i]
　　　　if ch>="a" and ch<="z":
　　　　　　r[0]=1
　　　　elif ch>="A" and ch<="Z":
　　　　　　r[1]=1
　　　　 ③　　　　　　:
　　　　　　r[2]=1
　　　　else:
　　　　　　r[3]=1
　　　　sum=r[0]+r[1]+r[2]+r[3]
　　　　if sum>=3:　　
　　　　　　print("強度:強")
　　　　elif④　　　　　　:
　　　　　　print("強度:中")
　　　　else:　　
　　　　　　print("強度:弱")
(2)若輸入的密碼字符串為“Asd 237”,則輸出的結果為　　　　。
1.有如下Python程序段:
listn=[0]*10
for i in range(len(listn)):
　　if i==0 or i==1:
　　　　listn[i]=1
　　else:
　　　　listn[i]=listn[i-1]+listn[i-2]
執行該程序段后,listn[9]的值為 (　　)
A.55 B.34 C.21 D.0
2.某Python程序代碼如下:
a=[10,5,2,11,7,6]
c=0
i=0
while i　　if a[i]%2==0:
　　　　c-=a[i]
a[i]∥=2
　　else:
　　　　c+=a[i]
　　　　i=i+1
print(int(c))
程序執行后,輸出的結果是 (　　)
A.5 B.14 C.23 D.51
3.斐波那契數列(Fibonacci sequence),又稱黃金分割數列、因數學家列昂納多·斐波那契(Leonardoda Fibonacci)以兔子繁殖為例子而引入,故又稱為“兔子數列”,指的是這樣一個數列:1、1、2、3、5、8、13、……,即從數列的第三項開始,當前項
為前兩項之和,編寫程序實現求斐波那契數列的第n項的值。
(1)用Python語言編寫的程序如下,請在劃線處填入合適的代碼,實現程序功能。
n=int(input("輸入n的值:"))
a=b=1
for i in range(3,n+1):
c=a+b
①　　　　　
print("第n項為:"+②　　　　　　)
(2)當輸入n=10,則程序輸出的第n項為　　　　。
4.有如下Python程序段:
count=0
for i in range(100,1000,1):
　　if i% 10==i∥100:
　　　　count+=1
執行該程序段后,count的值為　　　　。
5.有如下Python程序段:
s="AAACBBBBCBBB"
count=1;cmax=1;last=s[0]
for i in s[1:len(s)]:
　　if last==i:
　　　　count+=1
　　else:
　　　　last=i
　　　　count=1
　　if cmax　　　　cmax=count
執行該程序段后,cmax的值為　　　　。
6.某Python程序實現的功能:運行程序輸入一個四位整數,能夠判斷該四位整數是否存在數字重復的位。程序代碼如下:
n=int(input("請輸入一個四位正整數:"))
f=[0]*10
while n>0:
　　y=n%10
　　①　　　
　　n=n∥10
if ②　　　　:
　　print("有重復的位。")
else:
　　print("沒有重復的位。")
劃線處的代碼應填 (　　)
A.①f[y]=1　　 ②sum(f)<4
B.①f[y]+=1 ②sum(f)<4
C.①f[y]=1 ②sum(f)==4
D.①f[y]+=1 ②sum(f)==4
7.水往低處流,下雨時道路上的低洼地(兩邊高中間低的凹處)總會有積水。例如某地面高度數據為“0,0,2,1,2,0,0,1”,則該地面有 2 處低洼地。實現該算法的程序段如下:
gd=input("請輸入地面高度,以空格間隔開:")
h=list(map(int,gd.split(",")))　#將字符串轉換為列表,例如"1,0,2",轉換為[1,0,2]
cnt=0　　
f=False
for i in range(1,len(h)):
　　if ①　　　　:
　　　　f=True
　　elif h[i-1]　　　　cnt+=1
　　　　②　　　
print("該地面有",cnt,"處低洼地。")
上述代碼中劃線處應填入的代碼是 (　　)
A.①h[i]>h[i+1]　②f=False
B.①h[i]>h[i+1]　②f=True
C.①h[i-1]>h[i]　②f=False
D.①h[i-1]>h[i]　②f=True
8.m錢買n雞問題。用m元買n只雞,公雞5元一只,母雞3元一只,小雞1元3只,輸出用m錢買n雞的所有方案及方案總數。
編寫程序實現上述功能,程序運行效果如圖所示。
請輸入錢:50請輸入要買的雞的數量:20方案1:3 11 6方案2:7 4 9共有方案數:2
實現上述功能的程序如下,請在劃線處填入合適的代碼。
count=0
m=int(input("請輸入錢:"))
n=int(input("請輸入要買的雞的數量:"))
for i in range(m∥5+1):
　 for j in range(m∥3+1):
　　　k=①　　　　　
　　　if②　　　　　　:
　　　　　 count+=1
　　　　　 print("方案",count,":",i,j,k)
print("共有方案數:",count)

展開更多......

收起↑