資源簡介

專題13　簡單算法程序實現
學習目標　1. 基于生活中的問題設計情境，掌握分析問題、抽象建模、設計算法、編寫程序的過程；
2.掌握利用算法解決問題的思維能力構建.
抽象和建模是用程序實現算法前的重要步驟，抽象找出影響問題的主要因素，明確已知什么和求什么。建模是描述主要因素之間的關系，一是明確方法，往往采用遍歷列表的方法；二是明確步驟，往往是求符合條件的和、個數、最值和平均值。枚舉算法簡稱枚舉法，也稱為列舉法、窮舉法，是暴力策略的具體體現，又稱為蠻力法，在遍歷過程中求值與條件進行比對的過程。枚舉法的基本思想是：逐一列舉問題所涉及的所有情形，并根據問題提出的條件檢驗哪些是問題的解，哪些應予排除。
(2023年6月浙江省選考)某倉庫有一排連續相鄰的貨位，編號依次為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　單元素遍歷
遍歷是按照一定的規則和次序訪問數據元素中的所有節點，使得每個節點都被訪問一次且僅被訪問一次。相同類型的數據往往保存在數組中，數組的特點是按照索引位置依次存放數據，若只有一個數組，可以通過按值訪問的方法，對所有數據進行求和、計數、求平均值和求最大值或最小值等操作。若多個數組，他們擁有相同的索引，可以通過索引位置依次訪問數據。
例題 根據某場館一天中每位參觀者的進館和出館時間，可統計該場館當天人流量的分布情況。每個人進、出館的時間用一個長度為11的字符串表示，例如“08：05－08：45”表示進館時間為8點5分，出館時間為8點45分。現要求統計當天館內人數超過指定人數的總時長。
(1)8點01分到8點08分的進出館人數如表所示：
分鐘 01 02 03 04 05 06 07 08
進館 人數 5 0 4 2 1 3 1 2
出館 人數 0 1 1 1 6 3 2 2
館內大于4人的時長為________分鐘。
(2)每個參觀者進入場館和出館時間保存在“參觀記錄.txt”文件中，編寫Python程序，請將程序補充完整。
a＝[]
f＝open(″參觀記錄.txt″，encoding＝″utf－8″)
for i in f：
　 t＝i.find(″－″)
　 a.append(i[：t]＋″in″)
　 a.append(①________＋″out″)
#對列表a按時間進行升序排列，代碼略。
sp ＝int(input(″請輸入指定人數″))
t ＝ －1 ; cnt ＝ 0 ; sum ＝ 0
for i in a：
　 mts ＝int(i[：2])*60＋int(i[3：5])
　 if i[5：]＝＝″in″：
　 cnt＋＝1
　 else：
　 ②________
　 if cnt>sp：
　 if t＝＝－1：
　　　 t＝mts
　 elif t>－1：
　 ③________
　 t＝－1
print(″超過指定人數的總時長：″ ＋ str(sum) ＋″分鐘″)
變式 每個人進、出館的時間用一個長度為11的字符串表示，例如“08：05－08：45”表示進館時間為8點05分，出館時間為8點45分。現要求統計當天館內人數超過指定人數的總時長，當天在館人數最多時刻及在館人數。
(1)8點01分到8點08分的進出館人數如表所示：
分鐘 01 02 03 04 05 06 07 08
進館人數 5 0 4 2 1 3 1 2
出館人數 0 1 1 1 6 3 2 2
在館人數最多時刻為________。
(2)每個參觀者進入場館和出館時間保存在“參觀記錄.txt”文件中，編寫Python程序，請將程序補充完整。
rs＝[0]*540　#存儲早上8點至下午5點每分鐘的在館人數
f＝open(″參觀記錄.txt″，encoding＝″utf－8″)
n＝0
for sj in f ：
　 m1＝int(sj[：2])*60＋int(sj[3：5])－480　#將入館時間轉換為上午8點以后的分鐘數
　 m2＝int(sj[6：8])*60＋int(sj[9：11])－480
　 rs[m1]＋＝1
　 ①________
sp ＝int(input(″請輸入指定人數：″))
totrs＝imax＝sumrs＝0
itime＝″″
for i in range(540)：
　 ②________
　 if totrs>sp：
　　　③________
　 if totrs>imax：
　　　imax＝totrs
　　　itime＝str(i∥60＋8)＋″：″＋str(i%60)
print(″超過指定人數的總時長：″ ＋ str(sumrs) ＋″分鐘″)
print(″在館人數最多時刻為：″ ＋ itime ＋″，共″ ＋ str(imax) ＋″人″)
重難點2　連續多個元素遍歷
在一個序列中遍歷元素可以分為兩種情況，一是對單個元素進行遍歷，如對字符串進行加密、壓縮算法。二是要找出序列中一個連續的子序列，如找一個依次相連的子串，找一個連續遞增或遞減的子序列。在第二種情況中，將涉及該元素與他前面或后面元素的關系，因此需與他們依次進行比較，比較總次數比元素的個數少1個。
例題 現有一個文檔“壓縮前.txt”中保存了大量的小寫字母和數字，小明發現文檔中有很多字母或數字是連續的，就想設計一個算法將字符串中連續的字母或數字進行壓縮，如連續字符“abcd”可壓縮為“a－d”，不連續的字符維持原狀，例如，字符串“abcde1255hij”可壓縮為“a－e1－255h－j”，并將壓縮后的結果輸出保存到“壓縮后.txt”中。
該算法的部分Python代碼如下：
def writedata(data)：
#將數據 data 輸入到″壓縮后.txt″中，代碼略
fp＝open(″壓縮前.txt″)
lines＝fp.readlines()
fp.close()
for line in lines:
　 flag＝False
　 ans＝″″
　 for i in range(len(line)－1)：
　 if ：
　　　 ans＋＝line[i]＋″－″
　　　 flag＝True
　 elif ord(line[i＋1])！＝ord(line[i])＋1：
　　　 ①________
　　　 flag＝False
　 ans＋＝line[i＋1]
　 ②________
(1)執行程序后，當輸入字符串s 的值為″efg1234345hijk″時， 壓縮后的字符串為________。
(2)請在劃線處填入合適的代碼。
(3)程序中加框處代碼有誤，請改正。
變式 老年機因其較大的按鍵，很適合老年人使用，但其中英文字母的輸入方式比較麻煩，導致很多老年人不太會用。如圖是一款老年機的鍵盤，其字母的輸入方式如下：
(1)若要輸入英文字母“A”，則2鍵按1下；若要輸入“B”，則2鍵按兩下；其他英文字母的輸入方式同理。
(2)若連續輸入的英文字母在同一數字鍵中，則在輸入下一個英文字母前，需先按下1鍵以表示確定；若連續輸入的英文字母不在同一數字鍵中，則不需要按1鍵，直接按所要輸入英文字母對應的數字鍵即可。
(3)若要輸入空格，則按0鍵。
王老師依據該手機的字母輸入規則，設計了一個 Python 程序。實現輸入按鍵被點擊的順序，顯示手機中輸入的英文內容的功能。程序運行界面如圖所示：
>>> 輸入按鍵編號順序：7999844666166 輸出的內容是：PYTHON >>>
實現該功能的程序代碼如下：
keyboard＝{″0″：″″，″2″：″ABC″，″3″：″DEF″，″4″：″GHI″，″5″：″JKL″，″6″：″MNO″，″7″：″PQRS″，″8″：″TUV″，″9″：″WXYZ″}
yw＝input(″輸入按鍵編號順序：″)
①________
i＝k＝1
result＝″″
while i　 if yw[i]＝＝key：
k＝k＋1
　　else：
if yw[i]＝＝″1″：
　　　 ②________
result＋＝keyboard[key][k－1]
key＝yw[i]
③________
　　 i＝i＋1
result＋＝keyboard[key][k－1]
print(″輸出的內容是：″，result)
請回答下列問題：
(1)若按鍵點擊的順序是“616661666166”，則手機中輸入的英文是________。
(2)要實現程序的功能，請完善劃線處的代碼。
重難點3　雙重遍歷
當一個集合或兩個集合中元素進行組合時，往往需要對這些集體遍歷多次。可能發生的情景有：①對一個過程重復多次，如在二維表中，重復讀取一行數據，并對一行數據進行分解處理，即一個集合有多個元素，每個元素有多個數據項。還有讀取一個多行的文本文件，處理每行數據，對一個DataFrame對象進行遍歷，查詢數據項的過程等等；②在一個集合中，找出兩個數據的組合，如統計一個數據的排名，各種排序算法，冒泡、插入排序等，還可以是一個連續段的開始位置和結束位置。③在兩個集合中各取一個元素進行組合，把每一種組合遍歷一次。
例題 挖金礦游戲。在一個8行8列的矩陣中，礦工位于第1行第1列的格子，n個金礦隨機分布在第1行下面的各個格子中，每個金礦的橫坐標依次保存x數組，縱坐標保存在y數組。礦工收集金礦方法：先確定每行最左邊和最右邊金礦的坐標，對于同一行的金礦，礦工先移動到最左邊金礦正上方，再執行向下x步的指令進行挖礦，接著從該行左邊第2個金礦開始一直挖到最右邊。該行完成后，再依次挖下方各行的金礦。
如圖a所示的金礦(圖中黑色方塊)分布圖，按右側所示的指令，可以收集全部金礦。
(1)現有4*4的金礦分布圖如圖b所示，礦工在左上角位置，寫出礦工按規則獲得所有金礦的指令(指令之間用逗號或空格隔開)_____________________________。
(2)編寫程序，按順序輸出指令，使礦工按照規則得到所有金礦，將空白處填寫完整。
x＝[2，2，5，5，5，8]　#各金礦行號，從小到大升序排列
y＝[1，2，4，5，8，6]　#各金礦列號，同一行金礦，列號從小到大升序排列
n＝len(x)　#金礦數量
px＝py＝1　#礦工初始位置行號和列號
i＝0
while i　 beg＝i
　　while i　 i＋＝1
　　if y[beg]　 print(″左″＋str(py－y[beg]))
　　elif y[beg]>py：
　 print(″右″＋str(①________))
　　　 print(″下″＋str(x[beg]－px))
　　　 print(″挖礦″)
　　　 for k in range(②________)：
　 print(″右″＋str(y[k]－y[k－1]))
　 print(″挖礦″)
px＝x[beg]
③________
i＋＝1
變式 某物品柜有5層，每層有10個格子，每個格子只能放一個物品。輸入一組物品的高度值(按降序排列)，將這些物品放在同一層的連續格子中。第一步：查找存放物品的格子。從第1層開始查找，若該層物品柜連續空格數量小于物品數量，則查找下一層。查找5層后還是不能找到連續存放位置，輸出“不能連續存放”。若在某一層中找到符合要求的連續空格子，則進行第二步：將物品按中間高兩端低的原則存放物品。先將高度最高的物品存放在連續空格的中間位置(若空格數量為偶數，則放在中間靠左位置)，接著依次將物品按先右后左的順序依次存放。如輸入物品高度為8，5，2，1，則依次放在第1排的第5，6，4，7的位置。第一排各個格子存放物品高度如圖所示，其中0表示未存放物品。
0 0 0 2 8 5 1 0 0 0
(1)輸入第1組物品高度依次為8，5，2，第2組依次為9，6，3，1，則高度為3的物品存放在第1排第________(填數字)個格子中。
(2)實現該功能的Python程序段如下，將空白處填寫完整。
#將已經存放的物品高度存儲在數組a中，如：
[[0，9，6，2，8，5，1，0，0，0]，[0，0，1，7，10，9，2，0，0，0]，……]，代碼略。
s＝input(″輸入一組降序的物品高度，用逗號分開：″)
wp＝list(map(int，s.split(″，″)))　#輸入的數字轉換成列表
flag＝False；i＝0
while i <5 and not flag：
　 beg＝0
　　for j in range(10)：
　　　 if a[i][j]＝＝0：　#物品柜格子為0表示沒有存放物品
　　　 if j－beg＋1>＝len(wp)：
　　　　　　 hang＝i；end＝j；flag＝True
　　　 else：
　　　 if flag：
　　　　　　 break
　　　 ①________
　　　i＋＝1
if flag：
　　　②________
　　　a[hang][wz]＝wp[0]
　　　i＝1
　　　while i　　　 if ③________：
　　　 wz－＝i
　 else：
　　　 wz＋＝i
　　　 a[hang][wz]＝wp[i]
　　　 i＋＝1
else：
　　print(″不能連續存放″)
#輸出物品柜的存放情況，代碼略
重難點1　單元素遍歷
1.某智能貨架有一排貨位，貨位號從 0 開始編號，每個貨位等寬。貨架上可放置不同寬度(占 1～3 個貨位)的箱子，箱子從左往右連續相鄰擺放。每次放置箱子時，只能在貨架上最后一個箱子的右側放置新箱子。可以搬離中間的某個箱子，但該箱右側所有箱子被自動左移。編寫程序，模擬搬離或放置操作，操作結束后，輸出當前貨架上所有箱子的起始位置。
請回答下列問題：
(1)若貨架有5個箱子，狀態如圖所示，搬離第2個箱子后，當前貨架上最后一個箱子的起始位置是________。
(2)實現上述功能的部分 Python 程序如下，請在劃線處填入合適的代碼。
#共有n 個箱子供操作，代碼略
lst＝[－1]*n
st＝m＝0
while True：
　　'''操作序列如[″P1″，″M0″，……. ，″E″]，依次讀取序列元素，存入變量op，″P1″表示放置寬度為 1 的箱子，″M0″表示搬離第 1 個箱子，代碼略'''
　　if op[0] ＝＝″P″：
　 w ＝ int(op[1：])　#表示箱子的寬度為w
　 lst[m]＝st
　　　 st＝st＋w
　 ①________
　　elif op[0]＝＝″M″：
　 i ＝ int(op[1：])　#表示第 i＋1 個箱子將被搬離
　 if lst[i＋1] ！＝ －1：　#計算移動的距離
　　　 dis＝②________
　 else：
　　　 dis＝st－lst[i]
　 while lst[i＋1]！＝ －1:
　　　 lst[i]＝lst[i＋1]－dis
　　　 i＝i＋1
　 lst[i] ＝ －1
　 st＝③________
　 m ＝m － 1
　 else：
　 break
#輸出當前貨架上所有箱子的起始位置，代碼略
2.實現第1題程序功能的程序代碼還可以如下：
#共有n個箱子供操作，代碼略
lst＝[－1]*n
wd＝[0]*n
st＝m＝0
while True：
　　'''操作序列如[″P1″，″M0″，……. ，″E″]，依次讀取序列元素，存入變量op，″P1″表示放置寬度為 1 的箱子，″M0″表示搬離第 1 個箱子，代碼略'''
　　if op[0] ＝＝″P″：
　 w ＝ int(op[1：])　#表示箱子的寬度為 w
　 lst[m]＝st
　 ①________
　 st＝st＋w
　 m＋＝1
　　elif op[0]＝＝″M″：
　 i ＝ int(op[1：])　#表示第 i＋1 個箱子將被搬離
　 t＝wd[i]
　 while ：
　　　 ②________
　　　 wd[i]＝ wd[i＋1]
　　　 i＝i＋1
　 ③________
　 st＝st－t
　 m ＝m － 1
　　else：
　 break
#輸出當前貨架上所有箱子的起始位置，代碼略
(1)將程序空白處填寫完整。
(2)實現加框處功能的語句還可以是________。
3.在一條寬度為L的直線小河中，一只青蛙想沿著直線從河的左側跳到右側。小河中有n片位置互不相同的荷葉，青蛙必須跳到荷葉上過河，否則會掉入水中。開始時青蛙站在河的左側(坐標為0)，接著不停地向右側跳躍，每次跳躍的距離不超過W，當青蛙跳到或跳過河的右側(坐標為L)時，青蛙完成過河。根據小河的長度，青蛙每次跳躍的最大長度和荷葉位置，求至少需要增加的荷葉數。
hl＝32　#小河的長度
w＝4　#青蛙每次跳躍的最大長度
a＝[0，2，9，11，17，24，30]
a.append(hl)　#起點為a[0]，終點為河長hl，把該位置加入數組a中
p＝1　#第1片荷葉的初始索引位置
d＝tot＝0　#d表示青蛙的位置
while d　　if　①______________：
　　　 d＝ a[p]
　　　 ②______________
　　else:
　　　 tot＋＝1
　　　 ③______________
print(″至少需要增加的荷葉數為：″ ＋ str(tot))
4.某平臺新上架影片推薦度的計算方式為：由5位專業評審與5位大眾評審給影片評分，評分區間為[1，10]，將專業評審均分的60%與大眾評審均分的40%進行求和并取整，根據得分確定等級(分值與等級的關系如圖a所示)。評委打分情況如圖b所示，“A”表示專業評審，“B”表示大眾評審，“A4－10”表示第4位專業評審給出10分。
分值 等級
1－2 ★
3－4 ★★
5－6 ★★★
7－8 ★★★★
9－10 ★★★★★
圖a
圖b
請回答下列問題：
(1)若專業評審均分為6，大眾評審均分為7，則該影片等級為________(填數字)顆星。
(2)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
f＝open(″dc.txt″，encoding＝″utf－8″)
line＝f.readline()　#讀取第一行，保存在字符串line中
pro，pub＝0，0
while line：　#當line非空
　　①________
　　t＝int(line[3：])
　　if x＝＝″A″：
　 pro＋＝t
　　：
　 ②________
　　line＝f.readline()　#繼續讀取一行
score＝int(pro/5*0.6＋pub/5*0.4)
grade＝③________
print(″推薦度為：″，″★″*grade)
(3)若“dc.txt”文件中無異常數據，寫出與加框處代碼功能相同的語句________。
(注：只需寫出一條語句，多于一條的以第1條語句為準)
5.某小區停車場停車使用車位鎖，其中私家車車位，車主可將感應器插在私家車的USB電源接口上，感應器在30～50米內發出高頻信號(如圖a)，當私家車靠近，車位鎖自動降下解鎖，車離開(20秒后)車位鎖自動升起上鎖。其余為收費車位，可掃描二維碼控制車位鎖并收費(如圖b)。
收費車位計費規則如下：停車時長不到半小時按2元計費；半小時及以上則按每小時5元計費；超過整小時部分，不足半小時的時長不計費，半小時及以上則按一小時計費。該停車場當日的停車記錄存儲在“parking.txt”文件中，文件內容如圖c所示，每一行共有4項數據，用逗號分隔，每項數據分別為進(出)場時間、車牌號、進出場狀態(0表示進場，1表示出場)、車位狀態(0表示私家車位，1表示收費車位)。小林編寫了Python程序，從該文本文件中讀取所有數據，并計算該停車場當日的總收入。請完成下列問題：
圖a　私家車位
圖b　收費車位
圖c
(1)私家車控制車位鎖需要安裝感應器，據題意，此感應器屬于________(單選，填字母：A.距離傳感器 / B.無源電子標簽 / C.有源電子標簽 / D.紅外傳感器)。
(2)程序代碼如下所示，加框處代碼有錯誤，請改正。
(3)請將劃線處代碼補充完整。
def calT(Tin，Tout)：
　 t1 ＝ int(Tin[11：13])*60 ＋ int(Tin[14：16])
　 t2 ＝ int(Tout[11：13])*60 ＋ int(Tout[14：16])
　 return t2－t1
f ＝ open('parking.txt'，'r')
line ＝ f.readline()
dic ＝ {}
price ＝ 5; total ＝ 0
while line：　#當 line 非空(從文件讀取到了數據)
　　car ＝ line.strip().split('，')
　　if car[2]＝＝'0' and car[3]＝＝'1':
　 dic[car[1]] ＝ car[0]
　　：
　 T ＝①________
　 if T < 30：
　　　 fee ＝ 2
　 else：
　　　 fee ＝②________
　 total ＝ total ＋ fee
　　line ＝ f.readline()
f.close()
print(″本日停車費總收入為：″， total)
重難點2　連續多個元素遍歷
1.隨機生成一個僅由大寫字母″X″″Y″″Z″組成長度為 n 的字符串，消除該字符串連續3個及以上的相同字符。例如，字符串″XZZYYYYZYZ″，第一步：消除字符4個″Y″，得到新字符串″XZZZYZ″；第二步：消除3個字符″Z″，得到新字符串″XYZ″。實現上述功能的Python程序如下，請回答下列問題：
(1)如有字符串“XYYYXXZZY”，則消除后，字符串為：________。
(2)請在程序劃線處①②③④填入合適的代碼，實現程序功能。
import random
def left(s，x)：　#查找與s[x]連續相同的最左邊位置
　 while ①________________________：
　 x＝x－1
　 return x
def right(s，x): 　#查找與s[x]連續相同的最右邊位置
　 while __②________________________ ：
　　　 x＋＝1
　 return x
n＝int(input(″請輸入字符串的長度：″))
s＝″″
for i in range(n)：　#隨機生成一個長度為n 的字符串
　 m＝random.randint(0, 2)　#
　 ③________________________
print(″生成的字符串為：″，s)
i＝0
while i　　L＝left(s，i)
　　R＝right(s，i)
　　if　④______________________ ：
　 s＝s[：L]＋s[R＋1：]
　 ⑤__________________
　 else：
　 i＋＝1
print(″最后的字符串為：″，s)
2.某酒店的房間編號為1到1000，對于空余的房間的記錄，采用連續空房間的起始房間編號和連續空房間數量進行記錄，例如：有空房間1、2、3、6、7、9號時，記錄的方法為：(1，3)，(6，2)，(9，1)，共3條記錄。當有人退房時，一般出現4種情況：
·若退出房間號為4時，屬于“上靠”情況，則第1條記錄修改為(1，4)；
·若退出房間號為5時，屬于“下靠”情況，則第1條記錄修改為(5，3)；
·若退出房間號為8時，屬于“上下靠”情況，則第2條、第3條記錄合并，修改為(6，4)；
·若退出房間號為12時，屬于“不靠”情況，則新增1條記錄為(12，1)。
請回答下列問題：
(1)當已有的空房間記錄為(3，5)，(9，5)，(16，3)，(30，2)，當退出房間號為8時，空房間記錄修改為________。
(2)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
″″″
讀入已有的空房間記錄，個數為n，這些記錄已按房間起始號升序排好，每條記錄的房間起始號存入數組room，對應的連續空房間的個數存入數組num，下標均為0到n－1
″″″
x＝int(input(″請輸入退出房間號：″))
pos＝0
while　①________：
　 pos＋＝1
if pos>0 and pos<＝n－1 and room[pos－1]＋num[pos－1]＝＝x and x＋1＝＝room[pos]：
　 ②________
　 for i in range(pos，n－1)：
num[i]＝num[i＋1]
room[i]＝room[i＋1]
　 n－＝1
elif pos>0 and room[pos－1]＋num[pos－1]＝＝x:
　 num[pos－1]＋＝1
elif ③________：
　 room[pos]＝x
　 num[pos]＋＝1
else：
　 for i in range(n－1，pos－1，－1):
　 room[i＋1]＝room[i]
　 num[i＋1]＝num[i]
　 room[pos]＝x
　 num[pos]＝1
　 ④________
for i in range(n)：
　 print(room[i]，″″，num[i])
3.對某二值圖像(顏色編號只有0、1)按如下規則對其進行數據壓縮：
(1)記錄原數據第1個位置的顏色編號；
(2)從左往右依次掃描顏色編號，統計并記錄連續出現的相同顏色編號個數：
例如：圖像的顏色編號壓縮結果為“0，9，8，3”(用逗號分隔)
請回答下列問題：
(1)若某二值圖像按此規則壓縮的結果為“1，1，3，5，6”，則該圖像的顏色數據中有________個1。
(2)定義如下jys(s)函數，參數s存儲壓縮結果，為字符串類型，如“0, 9, 8, 3”。函數功能是實現數據解壓縮，函數以字符串類型返回原數據。請在劃線處填入合適的代碼。
def jys (s)：
　 d ＝ {″1″：″0″，″0″：″1″}
　 ①________
　 ns ＝″″；p ＝ s[0] ; i ＝ 2
　 while i < n：
num＝0
while ②________：
　　　　　 num ＝ num*10 ＋ int(s[i])
　　　　　 i ＋＝ 1
i ＋＝ 1
for j in range (num) ：
　　　　 ③________
p ＝ d[p]
　　return ns
4.非空字符串s由互不相同的n個英文小寫字母按升序排列而成，可將其中連續的多個字母縮寫(如“abcd”縮寫為“a～d”，“ab”寫作“a～b”)。例如字符串“abcghijkmnopqsvwxyz”可縮寫為“a～cg－km～qsv～z”。對于s，每當輸入一個小寫字母c時，若c已存在于s中，則視為從s中刪掉此字母；否則將c插入到s中，并保持字母升序，輸出更新s后對應的縮寫字符串。請回答下列問題：
(1)如圖所示，初始時字符串為“abcghijkmnopqsvwxyz”，依次輸入“d”、“z”、“o”，在當前狀態下，更新字符串縮寫為________。
原字符串縮寫為：a～cg－km－qsv～2 →請輸入一個小寫字母：d 更新字符串縮寫為：a～dg－km～qgv～z →請輸入一個小寫字母：2 更新字符串縮寫為：a－dg－km～qsv～y →請輸入一個小寫字母：o 更新字符串縮寫為：
(2)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
def compress(s)：
　 s＋＝″～″
　 news ＝″″
　 cl＝s[0]
　 n＝len(s)
　 cnt＝1
　 for i in range(1，n)：
　 if　ord(s[i])＝＝ord(s[i－1])＋1：
　　　　 cnt＋＝1
　 else：
　　　　 if cnt ＝＝1：
　　　　 news＋＝cl
　　　　 else：
　　　　 news＋＝cl＋″～″＋s[i－1]
　　　　 ①________
　　　　 cnt＝1
　 return news
#每當輸入一個字母后，更新字符串并輸出相應的縮寫字符串
s＝″abcghijkmnopqsvwxyz″
print(″原字符串縮寫為：″，compress(s))
while True：
　 n＝len(s)
　　c＝input(″請輸入一個小寫字母：″)　#輸入一個小寫字母
　　pos ＝0
　　while ②__________：
　　　 pos ＋＝1
　　if pos＝＝n：
　　　 s＋＝c
　　elif c！＝s[pos]：
　　　 ③________
　　else：
　　　 s＝s[：pos]＋s[pos＋1：]
print(″更新字符串縮寫為：″，compress(s))
5.某商場對所有商品按價格升序排序，按相同價格劃分成一段的方式，將數據分割成若干段，對每段數據進行壓縮，最后存儲為一個數字序列，壓縮規則如下：
①使用兩個整數x，y對一段連續相同的價格數據進行壓縮。其中x為當前段表示的商品的價格較前一段商品的價格的增值(若為第1段，則x為第1段的價格數據)，y表示當前段的數據個數(其中0≤x，y≤1000，且均為正整數)。
②將各段價格數據壓縮的結果通過“，”連接。
例如，各商品價格為“1，1，3，3，3，5，8，9，9，9，9，10”，先將連續相同的各段數據進行壓縮，然后連接各段壓縮的結果，如圖所示。
(1)已知升序的商品價格數據為“2，2，2，5，5，7，7，7，7，”，則壓縮結果為________。
(2)根據上述壓縮算法，設計一個對應的解壓縮程序，用于求解壓縮前的價格數據，其Python代碼如下，請在劃線處填入合適的代碼。
s＝input()　#輸入待解壓的字符串
a＝[0]*1000　#用于存儲各商品的價格
f＝False；tmp＝0；k＝1
for i in range(len(s))：
　 if ″0″<＝s[i]<＝″9″：
　 ①________
　 else：
　 if f＝＝False：
　　　 a[k]＝a[k－1]＋tmp
　　　 k＋＝1
　 else：
　　　 for j in range(tmp－1):
　　　　 ②________
　　　　 k＋＝1
　 f＝ ③________
　 tmp＝0
print(a[1：k])
(3)現有m元資金，希望從商場中購買兩個商品，請根據上題中求解的商品價格(升序)，統計使用現有資金能購買兩個商品的方案數，實現上述功能的Python代碼如下。
m＝int(input())　#輸入現有的資金數量
ans＝0
i＝1; j＝k－1
while i　 if a[i]＋a[j]>m:
　 j－＝1
　 else：
　 ________
　 i＋＝1
print(ans)
劃線處應填入的代碼是________。
(4)執行以上程序后，若解壓后存入列表a中的價格數據為[0，22，22，24，55，76，77]，輸入m＝100后輸出的結果為11，則上述代碼中的“else”分支執行了________次。
重難點3　雙重遍歷
1.數據在網絡傳輸中，帶寬是寶貴的資源，通過壓縮傳輸的字符串，可以減少數據量，從而加快傳輸速度，節省帶寬資源。現有一種字符壓縮方法描述如下：對于連續的若干個相同的子串“X”會壓縮為“[DX]”的形式(D是一個整數且1≤D≤99)，如字符串“ABABABAB”就壓縮為“[4AB]”或者“[2[2AB]]”，類似于后面這種壓縮之后再壓縮的稱為二重壓縮。如果是“[2[2[2AB]]]”則是三重的。現給出一串壓縮后的結果，并對其進行解壓縮。
思路：先找出每個左括號的位置，然后從后往前枚舉，找出每一個括號內要解壓的子串以及要解壓的次數，將子串解壓后得到一個新串，重復操作，得到最終的解壓縮結果。
例如：[2[2[2AB]]]→[2[2ABAB]]→[2ABABABAB]→ABABABABABABABAB。
(1)已知采用上述壓縮方法得到的壓縮結果是“[2Z[2DB]]”，則解壓縮結果為________。
(2)根據上述描述，小明利用 Python 設計了一個解壓縮程序，請在劃線處填入合適的代碼。
start ＝ []
s＝input(″請輸入壓縮結果：″)
for i in range(len(s))：
　 if s[i]＝＝″[″：
　 start.append(i)
for i in range(len(start)－1，－1，－1):
　 num＝0；temp＝″″
　 ①________
　 while j　　　if ″0″<＝s[j]<＝″9″：
　　　 num＝num*10＋int(s[j])
　　　else：
　　　 ②________
　　　j＋＝1
　 ans＝ num*temp
　 s＝s[：start[i]]＋③________　#重新構造字符串
print(″解壓結果為：″＋s)
2.有m個人結伴旅行(m<＝9，每人用整數1～m編號)。期間既有全員參與的集體活動，也有自主參與的小團隊活動。每項活動的消費由參與人平均分攤，其中一人先行墊付并記錄。記錄內容包括該項活動的人均消費金額(元)、參與人。每項活動的參與人用字符串表示，墊付人排在第1位。如″25134″表示2、5、1、3、4號參與該項活動，其中2號是墊付人。旅行活動結束依據所有活動的消費記錄進行結算。要求輸出轉賬明細。(編號小的付款人優先轉賬給編號小收款人)
(1)若有4個人參加3項活動，每項活動的參與人分別是“31”，“124”，“23”，每項活動的平均消費金額分別為50元，100元，300元， 則3號人員應還款項為________元。
(2)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
a＝['315', '523', '25134', '345', '41', '13524', '513', '451', '153']
x＝[50, 60, 30, 120, 75, 35, 95, 55, 30]
n＝len(a)
m＝5
#讀取所有消費記錄，顯示在屏幕中，如圖1所示，代碼略
#計算每個人員的應還款額、輸出轉賬明細
b＝[0 for i in range(m＋1)]　#保存應還款數據
for i in range(n)：　#根據消費記錄計算應還款
　 p＝int(a[i][0])
　 b[p]－＝(len(a[i])－1)*x[i]
　 for j in range(1，len(a[i]))：
　 p＝int(a[i][j])
　 ①________________
print('人員 應還款項')
c＝0
for i in range(1，m＋1)：　#統計需要還款人的人數c
　 print(f' {i}{b[i]}')
　 if b[i]>0：
　 ②____________
print(“轉賬人 接收人 金額”)
i＝j＝1　#根據應還款數據計算轉賬明細
while c>0：
　 while b[i]<＝0：　#找第一個大于0的
　 i＋＝1
　 while b[j]>＝0：　#找第一個小于0的
　 j＋＝1
　 ③____________________
　 if w>0：
　 v＝b[i]－w
　 else：
　 v＝b[i]
　 c－＝1
　 b[i]－＝v
　 b[j]＋＝v
　 print(i，“→”，j , v)
3.編排試場。每個試場有30個座位，試場號、座位號和班內序號均從1開始。對n個班級的學生編排試場，要求連續分配座位的兩個學生不屬于同一個班級。
分配方法：按班級人數降序排列，每次編排第1個班級的學生，完成一個學生考號的編排后，先將第1和第2個班級互換，再從第2個班級開始排序，當班級人數小于等于后面班級人數時，依次交換。如1班至3班的人數為36，35，35，第1試場座位號1的學生為1班學生，交換并排序后的班級依次為2，3，1，每班人數均為35人，座位號為2的學生是第1個班級(2班)。
(1)若1班至4班的人數分別38，36，36，36，則第1試場座位號為5的班級是________。
(2)實現上述功能的部分 Python 程序如下，請在劃線下填入合適的代碼。
num＝[42，43，44，41，40，41，38]　#每個班級的人數
bj＝[3, 2, 1, 4, 6, 5, 7]　#每個班級的班號
n＝len(num)　#總共班級數量
bnxh＝[1 for i in range(n)]　#每個班級的班內序號
zwh＝sch＝1
scbp＝[]
while num[0]！＝0：
　 #準考證號格式為“入學年份(4位)＋班號(2位)＋班內序號(2位)”
　 s1＝″0″＋str(bj[0])；s2＝″0″＋str(bnxh[bj[0]－1])
　 s＝″2021″＋s1[－2：]＋s2[－2：]
　 scbp.append([sch，zwh，s]) #完成一個學生的編排，格式為：試場號，座位號，準考證號
　 ①________
　 zwh＋＝1
　 bnxh[bj[0]－1]＋＝1
　 if zwh＝＝31：
　 ②________
　 zwh＝1　
　 num[0]，num[1]＝num[1]，num[0]
　 bj[0]，bj[1]＝bj[1]，bj[0]
　 j＝1
　 while ③________：
　 num[j]，num[j＋1]＝num[j＋1]，num[j]
　 bj[j]，bj[j＋1]＝bj[j＋1]，bj[j]
　 j＋＝1
#輸出編排的試場信息，代碼略。
重難點1　單元素遍歷
1.猜數游戲。游戲規則如下：設定一個秘密數，每猜錯一次會得到格式為“iAjB”的提示，其中“iA”表示數字猜對且位置也猜對的數有i個，“jB”表示數字猜對但位置沒猜對的數有j個。例如秘密數為“2507”時，若猜測數為“1702”，則提示是“1A2B”。
(1)現已知秘密數為“37692”，猜測數為“79612”，則提示是________。
(2)上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
#將設定的秘密數存放于變量s中
while True：
　 g＝input()
　　if g ＝＝ s:
　 print(″猜對了″)；break
　　i＝A＝B＝0
　　cnt1, cnt2 ＝ [0] * 10, [0] * 10
　　while i　 if　①________ ：
　　　 A＋＝1
　 else：
　　　 cnt1[int(s[i])]＋＝1
　　　 ②________
　 i＋＝1
　for j in range(10)：
　 m＝ min(cnt1[j]，cnt2[j])
　 ③________
　print(″提示：″，str(A)＋″A″＋str(B)＋″B″)
2.機器人移動路線管理。機器人在一平面內按照程序預置數據來完成移動操作(如圖a所示)，規則如下：①只能水平或垂直方向移動，方向取值：上：U、下：D、左：L、右：R，不能走斜線；每次移動1－5單位距離；②從起點出發，經過若干步后，盡可能返回到起點，如不能自動返回，則計算剩余移動次數。請完成劃線處代碼。
圖a
圖b
(1)解決上述問題的主程序如下：
bp＝startpos()　#輸入起點坐標
dirt＝[]　#移動方向
step ＝[]　#移動距離
readdata()　#從data.csv文件中讀取移動數據
pos＝[bp]　#從起點開始存儲所有經過點的x、y坐標
for i in range(0，len(dirt))：　#利用預置數據移動
　 tmp ＝ move(pos[i]，dirt[i]，step[i])
　 pos.append(tmp)
　 print(″經過的位置點如下所示：″，″n″， pos)
if tmp＝＝________：　#判斷能否返回起點
　 print(″可以直接返回起點位置！″)
else：
　　print(″不能直接返回起點位置！″，end＝″″)
　　stpx＝gettimes(pos[0][0], pos[－1][0])
　　stpy＝gettimes(pos[0][1], pos[－1][1])
　　print(″至少需要移動″＋str(stpx＋stpy)＋″次才能返回起點位置！″)
(2)編寫函數startpos()，功能為輸入起點坐標，返回坐標的值，返回值類型為列表。代碼如下：
def startpos()：
　 x＝int(input('輸入起點的x坐標：'))
　 y＝int(input('輸入起點的y坐標：'))
　 return ________
(3)編寫readdata()函數，功能為從csv文件中讀取預置的移動數據。代碼如下：
def readdata()：
　 import csv
　 f＝open(″data.csv″ ，″r″， encoding＝″utf－8″)
　 f_csv ＝ csv.reader(f)
　 title ＝ next(f_csv)　#讀取標題行
　 for line in f_csv：
　 dirt.append(line[0])
　 step.append(__________)
　 f.close()
(4)編寫位置移動函數move()，實現計算移動到的新位置。代碼如下：
def move(pos, dr, lg)：　#位置移動
　 new_pos ＝[0，0]
　 if dr ＝＝″U″：
　 x＝0；y ＝1
　 elif dr＝＝″D″：
　 x＝0；y＝－1
　 elif dr ＝＝″L″：
　 x＝－1；y ＝0
　 elif dr＝＝″R″：
　 x＝1；y＝0
　new_pos[0]＝pos[0]＋x*lg
　________________
　return new_pos
(5)編寫函數gettimes()，計算剩余移動次數。代碼如下：
def gettimes(p1, p2)：
　 p＝abs(p1 － p2)∥5
　 if abs(p1－p2)%5！＝0：
　 ________
　 return p
3.搶紅包游戲：微信搶紅包游戲成為一代人的經典回憶，游戲將總金額為n的“紅包”隨機分配給m個玩家，紅包的分配需同時滿足以下規則：①所有人搶到的金額總和跟總金額n相等；②每個人至少搶到1分錢；③每個人搶到的金額隨機；④每個人搶到金額大小的概率平等。
滿足以上規則的最簡單算法可描述為：假設總金額為n元，為使問題簡單化，將總金額乘以100，此時的單位為分，使得問題在整數范圍內解決。假設分發給m個人，則只需在[1，100*(n－1)]長度的范圍內隨機生成m－1個不重復的點，這些點將長為100*n的線段劃分為m個段，每一段長度即可表示紅包金額，再將每一段長度數據除以100換算為單位元輸出。程序運行的結果如圖所示。
輸入紅包金額：100 輸入紅包數量：5 紅包金額：54.4，11.59，28.09，4.09，1.84 手氣最佳：54.4
實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
import random
n＝int(input(″輸入紅包金額：″))*100
m＝int(input(″輸入紅包數量：″))
if m>n：
　 print(″游戲無法繼續，結束！″)
else：
　 f＝[False]*(n＋1)
　 for i in range(①________)：
　 t＝random.randint(1, n－1)
　 while f[t]：
　　　 t＝random.randint(1, n－1)
　 f[t]＝True
　 ②________
　 p＝0
　 amax＝0
　 s＝″″
　 for i in range(1，n＋1)：
　 if f[i]：
　　　　③________
　　　　s＋＝str(red/100)＋″，″
　　　　if red>amax：
　　　　 amax＝red
　　　　p＝i
print(″紅包金額：″＋s[：－1])
print(″手氣最佳：″ ＋ str(amax / 100))
4.有n名同學參加春游，已知現有公用經費total元，同時每位同學又隨身攜帶一些現金，用數組cash存儲。春游地點有不同類型自行車若干輛供游客租用，每種類型的自行車按租金從高到低存儲在數組info中。info[i]表示某類型自行車信息，包含租金和數量。其中，info[i][0]表示該類型自行車租金，info[i][1]表示該類型自行車數量。
每位同學優先使用自己攜帶的現金租車，現金不夠時可使用公用經費補足費用。為方便財務管理，規定每位同學只能為自己租用自行車，且不會相互借錢。請編寫程序計算這n個同學是否能夠全部租到自行車。
(1)若人數n＝5，total＝80，cash＝[21，15，10，8，5]，info＝[[60，1]，[50，2]，[35，2]，[25，3]]，判斷這5個同學是否都能租到自行車________(單選，填字母：A.是/B.否)。
(2)完善程序，將①②處代碼補充完整。
(3)將加框處代碼換成i＝＝m，是否影響判斷結果的準確性？________(單選，填字母：A.影響/B.不影響)
#total存儲公用經費，info存儲每種自行車的租金及庫存，代碼略
#讀取n個同學現金數量，存儲在數組cash中，并將cash降序排序，代碼略
bike＝[]　#bike存儲每輛自行車的租金
n＝len(cash)
for i in range(len(info))：
　 for j in range(info[i][1])：
　 bike.append(info[i][0])
m＝len(bike)
i＝①________
j＝0
while i＝0：
　 if bike[i]>cash[j]：
　 ②________
　 i＋＝1; j＋＝1
if ：
　　print(″能夠滿足全部同學租用自行車″)
else：
　　print(″資金不足， 無法滿足″)
5.輸入一個1－99999之間正整數金額，轉換成相應的大寫人民幣形式，處理的方式：
1)人民幣大寫形式分″零壹貳叁肆伍陸柒捌玖″共10個數字和″拾佰仟萬″4個單位。
2)從左向右向后處理每一位數字，同時讀取該位數后面的一個數字。對當前數字分0和非0兩個情況進行處理，若當前位為0，不加″拾佰仟萬″等單位，如102轉換為壹佰零貳元。
3)最后一位數單獨處理，若為0，直接在轉換后的字符串后加上“元”，否則加上對應的大寫數字和文字“元”。
實現該功能的程序代碼如下，請將劃線處填寫完整。
sn＝″零壹貳叁肆伍陸柒捌玖拾佰仟萬″
s＝input(″輸入一個大于0但小于10萬的正整數：″)
ans＝″″
for i in ①________：
　 t1＝int(s[i])
　 t2＝int(s[i＋1])
　 if t1 ！＝0：
　 jedx＝sn[len(s)－2＋10－i]
　 ans＋＝sn[t1]＋ jedx
　 ②________：
　 ans＋＝sn[0]
③________
if t1！＝0：
　 ans＋＝sn[t1]
print(″轉換的大寫形式為：″＋ans＋″元″)
重難點2　連續多個元素遍歷
1.現有一個由n位大寫字母組成的密碼串，將其分成m段長度相同的子密碼串，已知n是m的倍數。小明編寫了一個Python程序，輸入密碼串和正確的子密碼串，檢查這m段子密碼串的正確情況。若子密碼串與正確的子密碼串不完全相同，則該子密碼串錯誤，需指出錯誤字符在該子密碼串中的位置。例如，密碼串為“ABCDEFGABBDKFGABCDEFKABCDGFG”，正確的子密碼串為“ABCDEFG”，則檢查結果如圖a所示，程序運行界面如圖b所示。
圖a
圖b
(1)密碼串為“ACDEFACDEEABDEFACDFF”，正確的子密碼串為“ACDEF”，則有________段子密碼串錯誤。(填：阿拉伯數字)
(2)實現上述功能的Python程序如下，請在程序劃線處填入合適的代碼。
pwst＝input(″請輸入密碼串：″)
pwsubst＝input(″請輸入正確的子密碼串：″)
n＝len(pwst)
p＝len(pwsubst)
m＝n∥p
errinfo＝[″″]*m
cnt＝0
for i in range(m):
　 j＝0
　 ①________
　 flagp＝0；info＝″″
　 while ②________：
if pwst[k]！＝pwsubst[j]:
　　　 flagp＋＝1
　　　 info＝info＋″″＋str(j＋1)
j＋＝1
k＋＝1
if flagp>0：
③________＝″第″＋str(i＋1)＋″段錯誤！錯誤位置：″＋info
cnt＋＝1
print(″共有″，cnt，″段錯誤″)
for i in range(cnt):
　 print(errinfo[i])
2.在僅包含星號*和小寫字母的字符串中，可以對星號進行消除。若字符串中含有除星號和小寫字母以外的其他字符，則輸出無法消除；否則按如下規則進行消除：
①從左向右依次消除一個星號，直至消除所有的星號。
②一次消除時，需要同時消去星號及星號前的一個字母，若星號前無字母，則僅消除該星號。
如對字符串″pyt**ho*n″的消除過程為：
第1次消除″t*″，字符串變為″py*ho*n″第2次消除″y*″，字符串變為″pho*n″，第3次消除″o*″，字符串變為″phn″，消除完成，結果字符串為″phn″。
(1)對字符串″*fightin**g*″消除后的結果為________。
(2)編寫程序實現上述消除，代碼如下，請完成劃線處的代碼。
s＝input(″請輸入一個字符串：″)
i＝0; flag＝True
while ①________：
　 if s[i]＝＝″*″：
　　　if i＝＝0：
　　　 s＝s[1：]
　　　 i－＝1
　　　else：
　　　 s＝②________
　　　 i－＝2
　 elif ③________：
　　　flag＝False
　 ④________
if flag：
　 print(″消除*后為：″，s)
else：
　 print(″含有其他字符，無法消除″)
3.如果連續數字之間的差嚴格地在正數和負數之間交替，則該序列稱為擺動序列。第一個差(如果存在的話)可能是正數或負數。僅有一個元素或者含兩個不等元素的序列也視作擺動序列。對于不是擺動序列的序列，可刪除其中的部分元素，剩余元素順序不變，從而得到符合要求的擺動子序列。
例如，[1，7，4，9，2]是一個5個數字的擺動序列，因為差值[6，－3，5，－7]為正負交替出現，如圖a所示。但是[2，5，8，2，5]和[2，5，3，3，6]不是擺動序列，其中[2，5，8，2，5]的前兩個差值都為正數，如圖b所示，而[2，5，3，3，6]的倒數第二個差值為0，如圖c所示。圖b中②－⑤為遞增，⑤－⑧不為遞減，因此②－⑤－⑧中需要刪除一個數，此外圖c中⑤－③為遞減，③－③不為遞增，因此⑤－③－③中需要刪除一個元素。擺動子序列的長度均為4。
編寫程序，隨機生成n個元素的序列，輸出該序列中刪除元素后最長擺動子序列的長度。
　　　 圖a　　　　圖b　　　　　圖c
(1)若序列為[3，6，4，4，2，5，7]，則該序列刪除元素后的最長擺動子序列的長度為________。
(2)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
import random
n＝int(input())
a＝[]
for i in range(①________):
　 a.append(random.randint(1，10))
print(a)　#輸出隨機生成的 n 個元素的序列
pre＝0
②________
for i in range(0，n－1):
　 cur＝a[i＋1]－a[i]
　 if pre<＝0 and cur>0 or ③________：
　 cnt＋＝1
　 pre＝cur
print(cnt)
4.某公路由于長期沒有維修，路上出現了很多個坑。為了盡快填補好這些坑，交通管理部門決定對m處地段采取交通管制。將該公路看成一條直線，坑就是直線上的坐標點，坑所在的路段需要封控管制。例如某管制路段2～4，需封控2、3、4路段。交管部門為了減少管制路段的長度，希望將這n個坑分成m段(一段可以只有一個坑)，使得這m段公路的總長度最小。請你根據n個坑的位置(位置已按照從小到大進行排序)，計算管制路段最小的總長度。代碼運行效果如圖所示。
路段數量：4 坑的坐標依次為：3，4，6，8，14，15，16，17，21，25，26，27，30，31，40，41，42，43 維修管制的路段依次為： 3～8 14～17 21～31 40～43 管制總長度為25
請回答下列問題：
(1)上圖所示的例子中，若將路段數量修改為5，則管制路段總長度為________。
(2)實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
m ＝ int(input(″路段數量：″))
s ＝ input(″坑的坐標依次為：″).split('，')
n ＝ len(s)
for i in range(n):
　 s[i] ＝ int(s[i])
flag ＝ [False] * (n－1)
for i in range(1, m)：
　 k ＝ －1
　 for j in range(n－1)：
　 if ①________：
　　　 if k ＝＝ －1 or s[j＋1]－s[j] > s[k＋1]－s[k]:
　　　　　 k ＝ j
flag[k] ＝ True
print(″維修管制的路段依次為：″)
dis, t ＝ 0, 0
for i in range(n－1):
　 if flag[i]：
　 print(s[t]，″～″，s[i])
　 dis ＋＝ s[i]－s[t]＋1
　 ②________
print(s[t]，″～″，s[n－1])
dis ＝③________
print(″管制總長度為″，dis)
5.小明編寫一個 Python 程序，實現找到字符串 s1 和 s2 中相同的最長子串s，并定位子串在字符串 s2 中出現的位置，運行結果如圖所示。
s1：Python s2：thanks tnanks thanks 最長共同子串：　th 子串出現位置： 0/7/14/
(1)如輸入s1和s2分別為“hello”和“hi”(不含引號)，輸出最長共同子串是________。
(2)定義longstr函數，功能是找到字符串s1和s2中相同的最長子串，請在劃線處填入合適的代碼。
def longstr(s1, s2)：
　 m ＝ [[0] * (1 ＋ len(s2)) for i in range(1 ＋ len(s1))]
　 t, h ＝ 0, 0
　 for i in range(1, 1 ＋ len(s1))：
　 for j in range(1, 1 ＋ len(s2))：
　　　　 if　①________：
　　　　 m[i][j] ＝ m[i － 1][j － 1] ＋ 1
　　　　 if m[i][j] > t：
　　　　　　 t ＝ m[i][j]
　　　　　　 ②__________
　　　　else：
　　　　 m[i][j] ＝ 0
　　return s1[h － t：h]
(3)定義pos函數，功能是定位子串在字符串s2中出現的位置，請在劃線處填入合適的代碼。
def pos(st，s2)：
　 print(″子串出現位置：″)
　 start ＝ 0
　 if len(st) > 0：
　 while True：
　　　　 start ＝ s2.find(st, start)　#返回字符串s2中子串st出現的首字符索引，從索引start開始找，若找不到，則輸出－1
　　　　 if start ＝＝ －1:
　　　　 break
　　　　 print(start, end＝″/″)
　　　　 ______________
(4)主程序，請在劃線處填入合適的代碼。
s1 ＝ input(″s1：″)
s2 ＝ input(″s2：″)
s ＝　____________
print(″最長共同子串：″， s)
pos(s，s2)
重難點3　雙重遍歷
1.每個人有智商qa和體力qb值，從n個申請人中挑選2人組隊參加某挑戰賽。條件一是2人的智商qa值都必須大于指定參數h；條件二是2人的體力qa值之差(較大值減較小值)小于h。在滿足上述兩個條件的所有2人組合中，挑選體力qb值之和最大的一個組合，若有多個相同最大的組合一并輸出。(qa、qb和h的值均為正整數)
(1)實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
(2)程序中加框處代碼有誤，請改正。
#讀入qa和qb的值，依次保存在列表中，代碼略
h＝int(input(″請輸入參數h：″))
imax＝0；s＝[]; n＝len(qa)
for i in range(n－1)：
　 if ①________：
　 continue
　 for j in range(②________)：
　 if ③________：
　　　 if　qb[i]＋qb[j]>imax：
　　　　　 imax＝qb[i]＋qb[j]
　　　　　 s＝[qa[i]，qb[i]，qa[j]，qb[j]]
　　　 ：
　　　　　 s.append([qa[i]，qb[i]，qa[j]，qb[j]])
#輸出最佳組合，代碼略。
2.現代詩的連排格式為各句以“/”分開，例如余光中先生的《鄉愁》的部分內容為：″小時候/鄉愁是一枚小小的郵票/我在這頭/母親在那頭/長大后/鄉愁是一張窄窄的船票/我在這頭/新娘在那頭″，現以右起豎式形式打印這部分內容，如圖所示。請回答下列問題：
(1)若按照右起豎式對“ABC/CBDA”進行打印，打印內容的第三行為________。
(2)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
#讀取連排格式的現代詩內容，存入poem，代碼略
s ＝ []; t ＝″″
poem ＋＝″/″
for c in poem：
　 if c ！＝″/″：
　 ①________
　 else：
　 s.append(t)　#列表s末尾追加一個元素
　 t ＝″″
maxlen ＝ 0
②________
for i in range(n)：
　 if len(s[i]) > maxlen：
　 maxlen ＝ len(s[i])
for i in range(maxlen)：
　 t ＝″″
　 for j in range(n)：
　 if　③________ ：
　　　 t ＝ s[j][i] ＋ t
　 else：
　　　 t ＝″″ ＋ t
　 print(t)
3.有n列磚組成的一面磚墻，每列磚由數量不等的磚塊組成，每塊磚的長寬高都為1。小明為了美化這面墻，需要在這面墻中找到一塊面積最大的矩形用于涂鴉。如圖a所示，有6列高度依次為2、1、5、6、2、3組成的磚墻，圖b和圖c是其中的兩種方案。編寫Python程序，找出面積最大的矩形，并輸出其位置和面積。
(1)結合圖 a，這面墻中可用于涂鴉的最大的矩形面積為________
(2)實現上述功能的Python代碼如下，請在劃線處填上合適的代碼。
#數組num中依次存放各列磚墻的高度，代碼略
maxs ＝ 0
n ＝ len(num)
for i in range(n):
　 minh＝num[i]
　 for j in ①________：
　 if minh > num[j]：
　　　 minh ＝ num[j]
　 ②________
　 if　s>maxs：
　　　　 ③________
　　　　 start ＝ i＋1
　　　　 end ＝ j＋1
print(″起止磚列編號為：″，start, end，″，最大面積為：″，maxs)
4.某影平臺上架新影片時，需要先確定該影片的類型，如喜劇片、動作片、愛情片。確定某影片的類型，可根據已有的樣本數據(如圖a所示)進行分類。
某分類算法如下：計算該影片與樣本中各影片分鏡頭的相似度，相似度可用距離公式來表示，例如“美人魚”各分鏡頭數據如圖b所示，其與“寶貝當家”影片的距離為。用該方法計算出“美人魚”與樣本中所有影片的距離，選取前k個最近距離的影片，統計出現頻次最多的影片類型，即為該影片的類型。
電影名稱 搞笑鏡頭 擁抱鏡頭 打斗鏡頭 影片類型
寶貝當家 45 2 9 喜劇片
唐人街探案 23 3 17 喜劇片
我的特 工爺爺 6 4 21 動作片
…… …… …… …… ……
泰坦尼克號 9 39 8 愛情片
羅馬假日 9 38 2 愛情片
新步步驚心 8 34 17 愛情片
圖a
電影名稱 搞笑鏡頭 擁抱鏡頭 打斗鏡頭 影片類型
美人魚 19 18 5 ？
圖b
距離最近的前5部影片為： 唐人街探案19.62，羅馬假日 22.56，新步步驚心 22.83, 泰坦尼克號 23.45，我的特工爺爺 24.92
圖c
請回答下列問題：
(1)與《美人魚》距離最近的前5部影片如圖c所示，則該影片屬于________(單選，填字母：A.喜劇片 /B.動作片 /C.愛情片)。
(2)定義如下mvmin(result，flag)函數，參數result列表存儲距離，flag列表存儲標記。若result＝[43，33，18，25，65]，flag＝[False，False，True，True，False]，則函數的返回值為________。
def mvmin(result，flag)：
　 mv＝10000　#假定result列表元素值不超過10000
　 for i in range(len(result))：
　 if mv>result[i] and flag[i]＝＝False：
　　　 mv＝result[i]
　　　 pos＝i
　 return pos
(3)實現電影分類的部分Python程序如下，請在劃線處填入合適的代碼。
'''
讀取樣本影片的鏡頭數據，存儲在data中，每個元素包含5個數據項，分別對應電影名稱、搞笑鏡頭、打斗鏡頭、擁抱鏡頭、影片類型。
如data＝[[″寶貝當家″，45，2，9，″喜劇片″]，……]，代碼略。
'''
x＝[″美人魚″，19，18，5]
dic＝{″喜劇片″：0，″動作片″：0，″愛情片″：0}
k＝5
result＝[0]*len(data)
for i in range(len(data))：
　 d＝0
　 for j in range(1，4)：
　 tmp＝①________
　 d＋＝tmp**2
　 result[i]＝round(d**0.5，2)　#結果保留2位小數
flag＝[False]*len(result)
print(″距離最近的前″，k，″部影片為：″)
while k>0：
　 p＝mvmin(result，flag)
　　flag[p]＝True
　　②________
　　print(data[p][0]，result[p]，end＝″，″)
　　③________
#統計前k個最近距離的影片中出現頻次最多的類型，并輸出該影片類型，代碼略
5.某校圖書館提供 3 類自習室，A 類最多容納 2 人，B 類最多容納 4 人，C 類最多容納 8 人，以 1 小時為單位進行預約，每人每天只能預約一次，每次預約僅限個人，規定預約時間結束之前必須離開。圖書館每天 6 點開館，22 點閉館。編寫程序，輸入某自習室號牌，根據已預約情況，輸出該自習室還能被預約的時間段。例：讀取“A102”已預約情況[[6，11], [15，18], [8，12], [15，22]]，其中“A102”表示為 A 類 102 號自習室，[6，11]表示某個人預約 6：00 開始，11：00 前必須離開，時間占用如圖所示，則該自習室還能預約的時間段為[[6，8]，[11，15]，[18，22]]。請回答下列問題：
)
(1)若“B101”的已預約情況為[[6，11]，[8，12]，[8，11]，[6，12]]，則該自習室還能預約的時間段是________。(時間段格式參照題中樣例)
(2)實現上述功能的部分Python代碼如下，請在劃線處填入合適的代碼。
r ＝ input(″輸入自習室號牌：″)
#根據自習室號牌 r，獲取該自習室可容納的人數上限和預約情況分別存入 ceil 和 time 中，代碼略
#如 time ＝ [[6，11]，[15，18]，[8，12]，[15，22]]
bucket ＝ [0]*24　#記錄該自習室每個時刻被預約的人數
for period in time：
　 for i in range(period[0]，①________):
　 bucket[i]＋＝ 1
ans ＝ []; rec ＝ []
for i in range(6，22)：
　 if bucket[i]　 rec.append(i)
　 if len(rec)＝＝0：
　 print(″該自習室目前沒有可預約時段″)
　 else：
　 left，right ＝0，0
　 i＝1
　 while i　　　 if rec[i]＝＝rec[i－1]＋1：
　　　　　 ②________
　　　 else：
　　　　　　 ans.append([rec[left]，rec[right]＋1])
　　　　　　 left，right＝i，i
　　　 ③________
ans.append([rec[left], rec[right]＋1])
print(r，″可預約的時間：″， ans)
6.上城小學將在本學期開展趣味運動會，一(10)班的班主任邀請你為他們設計一個Python程序，用于挑選參加集體項目的選手。挑選規則為：當班級有足夠候選人員時，進行隨機挑選，并輸出人員名單；若無足夠人員時，提示“無足夠候選人員參加比賽！”，并規定每個學生最多參加一個集體項目。程序要求用戶按照規范輸入比賽項目及相關人員要求，例如輸入“投籃：8，2”即籃球項目要求男生8人，女生2人。該程序的運行效果如圖所示：
請輸入比賽項目及相關人員要求：跳繩：5，5， 趕豬：15，15；投籃：8，2 跳繩項目： 男：艾震宇　蔡溫淼　葉埕奇　王子碩 女：王曉清　黃鑫櫞　陳佳妮　陳昱彤　陳奕臻 趕豬項目： 無足夠侯選人員參加比賽！ 投籃項目： 男：陳展驄　李俊翰　張子俊　劉泓成　胡海偉　王子涵　葉賽特　伍越 女：賈熙　錢梓涵
(1)實現挑選集體項目選手的Python代碼如下，程序中用到的列表函數與方法如表所示，請在劃線處填入合適代碼。
函數與方法 功能
w.append(x) 在列表w末尾添加元素x
x＝w.pop(i) 將列表w末尾下標為i的元素賦值給x，并將其從w中刪除
(2)程序加框處代碼有誤，請改正。
from random import shuffle
def disp(inf)：
　 #將輸入的字符串整理為指定格式，當輸入字符串為″跳繩：10，10；投籃：8，2″，則將其調整為{″跳繩″： [10, 10]，″投籃″： [8, 2]}并返回。
def player(x，n): #輸出列表前n個元素，并刪除這些元素，返回刪除后的新列表
　 for i in range(n):
　 ①________
　 print(xm，end＝″″)
　 return x
c＝[[″陳浩琦″，″男″]，[″王慧敏″，″女″], [″王子涵″，″男″], …]　#班級學生名單
ctemp＝[[]，[]]　#根據學生性別分別存儲男生和女生名單
for ②________ in c:
　 if p[1]＝＝″男″：
　 ctemp[0].append(p[0])　#append()函數的功能為在列表末尾插入新元素
　 else：
　 ctemp[1].append(p[0])
inf＝input(″請輸入比賽項目及相關人員要求：″)
s＝[″男″，″女″]
sj＝disp(inf)
for t in sj：　#變量遍歷字典中的每個鍵
　 if sj[t][0]<＝len(ctemp[0]) and sj[t][1]<＝len(ctemp[1]):
　 print(t＋″項目：″)
　 for i in ③________：
　　　　 print(s[i]，end＝″：″)
　　　　 shuffle(ctemp[i])　#shuffle用于將序列的所有元素進行隨機排序
　　　　
　　　　 print()
　　　 else：
　 print(t＋″項目：\\n無足夠候選人員參加比賽！″)
7.某校舉行趣味運動賽，共有n個比賽項目，每班派n位學生參加，每位同學分別參加一個項目。某班有n位選手報名參加比賽，現需要依據他們平時練習中各個項目的平均得分，找出最佳參賽組合，查找規則為各項目得分總和最大，例如：圖a所示的數據中，最佳參賽組合是“唐昌新：跳繩，胡鵬：飛鏢，楊勝超：顛球，陳偉：套圈”。完成下劃線的代碼。
圖a
最佳參賽組合： 唐昌新　跳繩 胡鵬　 飛鏢 楊勝超 　顛球 陳偉　 套圈
圖b
def check(s)：#　判斷s中是否有重復值
　 f＝[0]*len(s)
　 for i in s：
　 ①____________
　 if f[i]>1：
　　　　return False
　 return True
a＝[]
f＝open(″cj.txt″，″r″)
title＝f.readline().split()　#讀取標題行
for line in f.readlines()：
　 line＝line.split()
　 a.append(line)
n＝len(a)；max＝0
for i in range(0，n**n)：
　 k＝i；s＝[0]*n；p＝0
　 while k！＝0：
　　　 s[p]＝k%n
　　　 k＝ ②________
　　　 p＝p＋1
　　if check(s)＝＝True：
　　　 sum＝0
　　　 for j in range(len(s)):
　　　　 sum＋＝int(③________)
　　　 if sum>max：
　　　　 ④__________
　　　　 ss＝s
print(″最佳參賽組合：”)
for i in range(n)：
　 print(a[i][0]，title[ss[i]＋1 ])
8.某影廳共12排，每排10座。座位編號以排號＋座號來命名，如第10排3座，編號命名為103。某一時刻，該影廳的最佳觀影區為方框內的座位如圖所示，即第5排3座～第10排8座的矩形位置。0表示該座位可選，非0表示已售(1表示系統推薦，2表示手工選擇)
座位推薦算法：
(Ⅰ)只推薦最佳觀影區的座位，并且所有座位號要連號。
(Ⅱ)優先選擇最佳觀影區內最中間的位置(若空位數為偶，則選擇中間靠左)，若中間位置相同，則以靠前位置為佳。
(Ⅲ)若在最佳觀影區內未找到可以推薦的座位時，系統將提示手工選擇。
(1)如圖所示的座位中，若要購買2張票，則推薦的排號是________
(2)實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
#產生一個12行10列的二維數組，并隨機產生座位情況，代碼略
k＝int(input(″請輸入購票數：″))
kwz＝0；wz＝[]
m＝12；n＝10
for i in range(4，10)：　#尋找中間空的座位，并把座位號保存到數組wz中。
　 for j in range(2，8)：
　 if a[i][j]＝＝0：
　　　　①________
　　　　wz.append(i*n＋j＋1)
#輸出中間空位，代碼略
minx＝n；s＝0；p＝0；x＝0
while p＋k－1　　if ②________
　 x＝abs(n∥2－(wz[p]＋wz[p＋k－1]))∥2%n　#計算中間位置
　 if x　　　 x＝minx
　　　 ③________
　　p＋＝1
ans＝″″
if s＝＝0：
　 ans ＝″未能推薦座位，請手工選座″
else：
　 for i in range(s，s＋k)：
　 ans ＝ ans ＋″第″ ＋ str(wz[i]∥n＋1) ＋″排″ ＋ str(wz[i] %n＋1) ＋″座″
print(ans)
9.某網約巴士，車上最初有12個空座位，從起點站向終點站行駛，不允許掉頭或改變方向，現有新的訂單，請判斷其是否能預約成功。請回答下列問題：
(1)若網約巴士已預約成功的數據為：[2，1，5]，[1，3，7]，[3，2，8]，[2，4，7]，[3，5，10]，其中每個元素有3個數據項，分別表示預約人數、出發站點和到達站點，當前接到訂單[4，5，8]，________(選填：能/不能)預約成功。
(2)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
#數組trips存儲預約信息，trips[i]＝[num，start，end]表示第i個預約信息有num個乘客，出發站點為start，到達站點為end，站點編號為1～10。
total＝12　#空座位總數
stations＝10　#站點總數
diff＝[0]*(stations＋1)
count＝[0]*(stations)　#存儲站點上下車后的乘客人數
for i in trips：
　 ①________
　 diff[i[2]]－＝i[0]
for j in range(1，stations)：
　for k in range(②________ )：
　 count[j]＋＝diff[k]
num＝int(input(″請輸入乘車人數：″))
start＝int(input(″請輸入出發站點編號：″))
end＝int(input(″請輸入到達站點編號：″))
flag＝True
for i in range(start，end)：
　 if　③________：
　 flag＝False
　 break
if flag：
　　print(″預約成功， 請到站點等候！″)
else：
　　print(″該訂單未能成功預約到即將駛來的 bus！″)
專題13　簡單算法程序實現
學習目標　1. 基于生活中的問題設計情境，掌握分析問題、抽象建模、設計算法、編寫程序的過程；
2.掌握利用算法解決問題的思維能力構建.
抽象和建模是用程序實現算法前的重要步驟，抽象找出影響問題的主要因素，明確已知什么和求什么。建模是描述主要因素之間的關系，一是明確方法，往往采用遍歷列表的方法；二是明確步驟，往往是求符合條件的和、個數、最值和平均值。枚舉算法簡稱枚舉法，也稱為列舉法、窮舉法，是暴力策略的具體體現，又稱為蠻力法，在遍歷過程中求值與條件進行比對的過程。枚舉法的基本思想是：逐一列舉問題所涉及的所有情形，并根據問題提出的條件檢驗哪些是問題的解，哪些應予排除。
(2023年6月浙江省選考)某倉庫有一排連續相鄰的貨位，編號依次為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″或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類型，因此下一個貨位要跳過。
重難點1　單元素遍歷
遍歷是按照一定的規則和次序訪問數據元素中的所有節點，使得每個節點都被訪問一次且僅被訪問一次。相同類型的數據往往保存在數組中，數組的特點是按照索引位置依次存放數據，若只有一個數組，可以通過按值訪問的方法，對所有數據進行求和、計數、求平均值和求最大值或最小值等操作。若多個數組，他們擁有相同的索引，可以通過索引位置依次訪問數據。
例題 根據某場館一天中每位參觀者的進館和出館時間，可統計該場館當天人流量的分布情況。每個人進、出館的時間用一個長度為11的字符串表示，例如“08：05－08：45”表示進館時間為8點5分，出館時間為8點45分。現要求統計當天館內人數超過指定人數的總時長。
(1)8點01分到8點08分的進出館人數如表所示：
分鐘 01 02 03 04 05 06 07 08
進館 人數 5 0 4 2 1 3 1 2
出館 人數 0 1 1 1 6 3 2 2
館內大于4人的時長為________分鐘。
(2)每個參觀者進入場館和出館時間保存在“參觀記錄.txt”文件中，編寫Python程序，請將程序補充完整。
a＝[]
f＝open(″參觀記錄.txt″，encoding＝″utf－8″)
for i in f：
　 t＝i.find(″－″)
　 a.append(i[：t]＋″in″)
　 a.append(①________＋″out″)
#對列表a按時間進行升序排列，代碼略。
sp ＝int(input(″請輸入指定人數″))
t ＝ －1 ; cnt ＝ 0 ; sum ＝ 0
for i in a：
　 mts ＝int(i[：2])*60＋int(i[3：5])
　 if i[5：]＝＝″in″：
　 cnt＋＝1
　 else：
　 ②________
　 if cnt>sp：
　 if t＝＝－1：
　　　 t＝mts
　 elif t>－1：
　 ③________
　 t＝－1
print(″超過指定人數的總時長：″ ＋ str(sum) ＋″分鐘″)
思維點撥
明考向 本題考查枚舉算法、多分支選擇結構
精點撥 (1)第1分鐘5人，第3、4、5分鐘分別在館人數為7，8，3，后面的都沒有超過4人，因此總時長為3分鐘。(2)①把前后兩個時間分開，分別加上in和out來區分。因此要找到“－”的位置t，當條件i[5：]＝＝″in″不成立時，取出出館的時間。②當條件i[5：]＝＝″in″成立時，表示進館，否則表示出館，當前人數cnt應減少一個。③處是一個狀態編程，當t值為－1時，表示還沒有達到目標人數時狀態，條件cnt>sp成立，且t值為－1，表示當前cnt值開始大于目標人數，因此t不是－1時，表示開始時間，當elif t>－1意味著cnt>sp不成立，表示這一段的結束時間，這一段的時間差為mts－t，把這些時間段累加起來
答案　(1)3　(2)①i[t＋1：]或 i[t＋1：len(i)]　②cnt－＝1　③sum＋＝mts－t
變式 每個人進、出館的時間用一個長度為11的字符串表示，例如“08：05－08：45”表示進館時間為8點05分，出館時間為8點45分。現要求統計當天館內人數超過指定人數的總時長，當天在館人數最多時刻及在館人數。
(1)8點01分到8點08分的進出館人數如表所示：
分鐘 01 02 03 04 05 06 07 08
進館人數 5 0 4 2 1 3 1 2
出館人數 0 1 1 1 6 3 2 2
在館人數最多時刻為________。
(2)每個參觀者進入場館和出館時間保存在“參觀記錄.txt”文件中，編寫Python程序，請將程序補充完整。
rs＝[0]*540　#存儲早上8點至下午5點每分鐘的在館人數
f＝open(″參觀記錄.txt″，encoding＝″utf－8″)
n＝0
for sj in f ：
　 m1＝int(sj[：2])*60＋int(sj[3：5])－480　#將入館時間轉換為上午8點以后的分鐘數
　 m2＝int(sj[6：8])*60＋int(sj[9：11])－480
　 rs[m1]＋＝1
　 ①________
sp ＝int(input(″請輸入指定人數：″))
totrs＝imax＝sumrs＝0
itime＝″″
for i in range(540)：
　 ②________
　 if totrs>sp：
　　　③________
　 if totrs>imax：
　　　imax＝totrs
　　　itime＝str(i∥60＋8)＋″：″＋str(i%60)
print(″超過指定人數的總時長：″ ＋ str(sumrs) ＋″分鐘″)
print(″在館人數最多時刻為：″ ＋ itime ＋″，共″ ＋ str(imax) ＋″人″)
答案　(1)8：04　(2)①rs[m2]－＝1　②totrs＋＝ rs[i]
③sumrs＋＝1
解析　本題考查枚舉算法。(1)從8：01點到8：04人數變化情況依次為5，－1，3，1，在8：04分達到8人。(2)①rs存儲早上8點至下午5點每分鐘的在館人數，m2表示出館的時間，rs[m2]表示該時間的在館人數，當有一個人出館時，相應的在館人數減少一人。②從早上8點開始遍歷每分鐘在館人數，并進行累加到變量totrs中。③當累加和超過sp時，相應的時刻增加1個。
重難點2　連續多個元素遍歷
在一個序列中遍歷元素可以分為兩種情況，一是對單個元素進行遍歷，如對字符串進行加密、壓縮算法。二是要找出序列中一個連續的子序列，如找一個依次相連的子串，找一個連續遞增或遞減的子序列。在第二種情況中，將涉及該元素與他前面或后面元素的關系，因此需與他們依次進行比較，比較總次數比元素的個數少1個。
例題 現有一個文檔“壓縮前.txt”中保存了大量的小寫字母和數字，小明發現文檔中有很多字母或數字是連續的，就想設計一個算法將字符串中連續的字母或數字進行壓縮，如連續字符“abcd”可壓縮為“a－d”，不連續的字符維持原狀，例如，字符串“abcde1255hij”可壓縮為“a－e1－255h－j”，并將壓縮后的結果輸出保存到“壓縮后.txt”中。
該算法的部分Python代碼如下：
def writedata(data)：
#將數據 data 輸入到″壓縮后.txt″中，代碼略
fp＝open(″壓縮前.txt″)
lines＝fp.readlines()
fp.close()
for line in lines:
　 flag＝False
　 ans＝″″
　 for i in range(len(line)－1)：
　 if ：
　　　 ans＋＝line[i]＋″－″
　　　 flag＝True
　 elif ord(line[i＋1])！＝ord(line[i])＋1：
　　　 ①________
　　　 flag＝False
　 ans＋＝line[i＋1]
　 ②________
(1)執行程序后，當輸入字符串s 的值為″efg1234345hijk″時， 壓縮后的字符串為________。
(2)請在劃線處填入合適的代碼。
(3)程序中加框處代碼有誤，請改正。
思維點撥
明考向 本題考查一個集合中兩個元素的組合，或者是一段連續區間的開始位置和結束位置的遍歷
精點撥 (1)略。(2)當條件ord(line[i＋1])！＝ord(line[i])＋1成立時，表示連續段已經結束，終點位置是i，因此需將line[i]連接入ans中。②讀取一行數據，處理完后調用writedata函數，將壓縮后的結果輸出保存到“壓縮后.txt”中。(3)找到連續段開始位置。flag是一個是否是頭部的標志，初值為False，找到連續字符串的第1個位置后，flag的值變更為True
答案　(1)e－g1－43－5h－k　(2)① ans＋＝line[i]　②writedata(ans)　(3)ord(line[i＋1])＝＝ord(line[i])＋1 and not flag或ord(line[i＋1])＝＝ord(line[i])＋1 and flag＝＝False
變式 老年機因其較大的按鍵，很適合老年人使用，但其中英文字母的輸入方式比較麻煩，導致很多老年人不太會用。如圖是一款老年機的鍵盤，其字母的輸入方式如下：
(1)若要輸入英文字母“A”，則2鍵按1下；若要輸入“B”，則2鍵按兩下；其他英文字母的輸入方式同理。
(2)若連續輸入的英文字母在同一數字鍵中，則在輸入下一個英文字母前，需先按下1鍵以表示確定；若連續輸入的英文字母不在同一數字鍵中，則不需要按1鍵，直接按所要輸入英文字母對應的數字鍵即可。
(3)若要輸入空格，則按0鍵。
王老師依據該手機的字母輸入規則，設計了一個 Python 程序。實現輸入按鍵被點擊的順序，顯示手機中輸入的英文內容的功能。程序運行界面如圖所示：
>>> 輸入按鍵編號順序：7999844666166 輸出的內容是：PYTHON >>>
實現該功能的程序代碼如下：
keyboard＝{″0″：″″，″2″：″ABC″，″3″：″DEF″，″4″：″GHI″，″5″：″JKL″，″6″：″MNO″，″7″：″PQRS″，″8″：″TUV″，″9″：″WXYZ″}
yw＝input(″輸入按鍵編號順序：″)
①________
i＝k＝1
result＝″″
while i　 if yw[i]＝＝key：
k＝k＋1
　　else：
if yw[i]＝＝″1″：
　　　 ②________
result＋＝keyboard[key][k－1]
key＝yw[i]
③________
　　 i＝i＋1
result＋＝keyboard[key][k－1]
print(″輸出的內容是：″，result)
請回答下列問題：
(1)若按鍵點擊的順序是“616661666166”，則手機中輸入的英文是________。
(2)要實現程序的功能，請完善劃線處的代碼。
答案　 (1)MOON　(2)①key＝yw[0]　②i＝i＋1
③k＝1
解析　(1)鍵6的第1個字母為M，同一數字鍵中，則在輸入下一個英文字母前，需先按下 1 鍵，鍵6的第3個字母為O，第2個字母為N。(2)查找連續相同的鍵的個數。①變量i從1開始遍歷，因此key的初值為yw[0]。若遍歷到″1″，說明是相同兩個鍵的分隔符，i的位置加1。③若不相同，則這個鍵是下一組的第1個鍵。
重難點3　雙重遍歷
當一個集合或兩個集合中元素進行組合時，往往需要對這些集體遍歷多次。可能發生的情景有：①對一個過程重復多次，如在二維表中，重復讀取一行數據，并對一行數據進行分解處理，即一個集合有多個元素，每個元素有多個數據項。還有讀取一個多行的文本文件，處理每行數據，對一個DataFrame對象進行遍歷，查詢數據項的過程等等；②在一個集合中，找出兩個數據的組合，如統計一個數據的排名，各種排序算法，冒泡、插入排序等，還可以是一個連續段的開始位置和結束位置。③在兩個集合中各取一個元素進行組合，把每一種組合遍歷一次。
例題 挖金礦游戲。在一個8行8列的矩陣中，礦工位于第1行第1列的格子，n個金礦隨機分布在第1行下面的各個格子中，每個金礦的橫坐標依次保存x數組，縱坐標保存在y數組。礦工收集金礦方法：先確定每行最左邊和最右邊金礦的坐標，對于同一行的金礦，礦工先移動到最左邊金礦正上方，再執行向下x步的指令進行挖礦，接著從該行左邊第2個金礦開始一直挖到最右邊。該行完成后，再依次挖下方各行的金礦。
如圖a所示的金礦(圖中黑色方塊)分布圖，按右側所示的指令，可以收集全部金礦。
(1)現有4*4的金礦分布圖如圖b所示，礦工在左上角位置，寫出礦工按規則獲得所有金礦的指令(指令之間用逗號或空格隔開)_____________________________。
(2)編寫程序，按順序輸出指令，使礦工按照規則得到所有金礦，將空白處填寫完整。
x＝[2，2，5，5，5，8]　#各金礦行號，從小到大升序排列
y＝[1，2，4，5，8，6]　#各金礦列號，同一行金礦，列號從小到大升序排列
n＝len(x)　#金礦數量
px＝py＝1　#礦工初始位置行號和列號
i＝0
while i　 beg＝i
　　while i　 i＋＝1
　　if y[beg]　 print(″左″＋str(py－y[beg]))
　　elif y[beg]>py：
　 print(″右″＋str(①________))
　　　 print(″下″＋str(x[beg]－px))
　　　 print(″挖礦″)
　　　 for k in range(②________)：
　 print(″右″＋str(y[k]－y[k－1]))
　 print(″挖礦″)
px＝x[beg]
③________
i＋＝1
思維點撥
明考向 本題考查雙重循環結構的應用
精點撥 (1)礦工在左上角位置，下1挖到第2行第1列的礦，下2挖到第4行1列的礦，再向右移動6，挖到第4行第4列的礦。(2)beg表示每一行最左邊金礦的索引，條件x[i]＝＝x[i＋1]成立表示兩個處于同一行的金礦，因此循環結束后，索引i表示當前行最右邊的金礦的列號。①py表示礦工的列號，條件y[beg]>py成立表示最左邊礦位于礦工的右邊，需向右移動y[beg]－py個位置。②當前行可能還有多個金礦，因此當前已經挖了最左邊beg位置上金礦，還需從y[beg＋1]位置挖到第y[i]列，由于range是一個左閉右開的區間，因此值為i＋1。③更新礦工的位置，其列號為最右邊金礦的列號
答案　(1)下1挖礦下2挖礦右3挖礦或下1，挖礦，下2，挖礦，右3，挖礦　(2)①y[beg]－py　②beg＋1，i＋1　③py＝y[i]
變式 某物品柜有5層，每層有10個格子，每個格子只能放一個物品。輸入一組物品的高度值(按降序排列)，將這些物品放在同一層的連續格子中。第一步：查找存放物品的格子。從第1層開始查找，若該層物品柜連續空格數量小于物品數量，則查找下一層。查找5層后還是不能找到連續存放位置，輸出“不能連續存放”。若在某一層中找到符合要求的連續空格子，則進行第二步：將物品按中間高兩端低的原則存放物品。先將高度最高的物品存放在連續空格的中間位置(若空格數量為偶數，則放在中間靠左位置)，接著依次將物品按先右后左的順序依次存放。如輸入物品高度為8，5，2，1，則依次放在第1排的第5，6，4，7的位置。第一排各個格子存放物品高度如圖所示，其中0表示未存放物品。
0 0 0 2 8 5 1 0 0 0
(1)輸入第1組物品高度依次為8，5，2，第2組依次為9，6，3，1，則高度為3的物品存放在第1排第________(填數字)個格子中。
(2)實現該功能的Python程序段如下，將空白處填寫完整。
#將已經存放的物品高度存儲在數組a中，如：
[[0，9，6，2，8，5，1，0，0，0]，[0，0，1，7，10，9，2，0，0，0]，……]，代碼略。
s＝input(″輸入一組降序的物品高度，用逗號分開：″)
wp＝list(map(int，s.split(″，″)))　#輸入的數字轉換成列表
flag＝False；i＝0
while i <5 and not flag：
　 beg＝0
　　for j in range(10)：
　　　 if a[i][j]＝＝0：　#物品柜格子為0表示沒有存放物品
　　　 if j－beg＋1>＝len(wp)：
　　　　　　 hang＝i；end＝j；flag＝True
　　　 else：
　　　 if flag：
　　　　　　 break
　　　 ①________
　　　i＋＝1
if flag：
　　　②________
　　　a[hang][wz]＝wp[0]
　　　i＝1
　　　while i　　　 if ③________：
　　　 wz－＝i
　 else：
　　　 wz＋＝i
　　　 a[hang][wz]＝wp[i]
　　　 i＋＝1
else：
　　print(″不能連續存放″)
#輸出物品柜的存放情況，代碼略
答案　(1)7　(2)①beg＝j＋1　②wz＝(beg＋end)∥2　③i %2＝＝0
解析　本題考查二維數組的遍歷和在一個序列中查找最值。(1)高度8，5，2依次存放第5、6、4的格子中，因此左邊還有3個空格，右邊有4個空格。高度9，6，3，1依次存放第8、9、7、10的格子中。(2)①確定連續空格子的最左邊位置beg，若格子為空，計算連續空格子數量為j－beg＋1，若數量達到存放物品數量時，將flag設置為True。若格子不為空，則下一個空格子的位置只能在當前j的下一個位置。②中間位置的計算方法類似于二分查找，將左右位置相加再整除以2。③語句a[hang][wz]＝wp[0]的功能是放置最中間的物品，接下來放在i為1的物品，在中間的右邊，即wz等于i＋1，當i的值為2時，放在左邊的前面2個位置中，因此通過判斷變量i的奇偶性來決定存放的位置。
重難點1　單元素遍歷
1.某智能貨架有一排貨位，貨位號從 0 開始編號，每個貨位等寬。貨架上可放置不同寬度(占 1～3 個貨位)的箱子，箱子從左往右連續相鄰擺放。每次放置箱子時，只能在貨架上最后一個箱子的右側放置新箱子。可以搬離中間的某個箱子，但該箱右側所有箱子被自動左移。編寫程序，模擬搬離或放置操作，操作結束后，輸出當前貨架上所有箱子的起始位置。
請回答下列問題：
(1)若貨架有5個箱子，狀態如圖所示，搬離第2個箱子后，當前貨架上最后一個箱子的起始位置是________。
(2)實現上述功能的部分 Python 程序如下，請在劃線處填入合適的代碼。
#共有n 個箱子供操作，代碼略
lst＝[－1]*n
st＝m＝0
while True：
　　'''操作序列如[″P1″，″M0″，……. ，″E″]，依次讀取序列元素，存入變量op，″P1″表示放置寬度為 1 的箱子，″M0″表示搬離第 1 個箱子，代碼略'''
　　if op[0] ＝＝″P″：
　 w ＝ int(op[1：])　#表示箱子的寬度為w
　 lst[m]＝st
　　　 st＝st＋w
　 ①________
　　elif op[0]＝＝″M″：
　 i ＝ int(op[1：])　#表示第 i＋1 個箱子將被搬離
　 if lst[i＋1] ！＝ －1：　#計算移動的距離
　　　 dis＝②________
　 else：
　　　 dis＝st－lst[i]
　 while lst[i＋1]！＝ －1:
　　　 lst[i]＝lst[i＋1]－dis
　　　 i＝i＋1
　 lst[i] ＝ －1
　 st＝③________
　 m ＝m － 1
　 else：
　 break
#輸出當前貨架上所有箱子的起始位置，代碼略
答案　(1)5　(2)①m＝m＋1　②lst[i ＋ 1]－ lst[i]　③st－dis
解析　(1)搬離第2個箱子，每個箱子向左移動3個單位，因此起始位置為5。(2)①從語句lst[m]＝st和st＝st＋w來看，m表示箱子索引號，st表示起始位置，起始位置每次增加箱子長度，因此箱子索引也要增加。②計算移動距離，條件lst[i＋1] ！＝ －1表示后面還有箱子，因此移出箱子的距離為前后兩個箱子起始位置的差值。③語句lst[i] ＝ －1更新最后一個箱子往前移動后，少了一個箱子，因此起始位置也要相應往前移動。
2.實現第1題程序功能的程序代碼還可以如下：
#共有n個箱子供操作，代碼略
lst＝[－1]*n
wd＝[0]*n
st＝m＝0
while True：
　　'''操作序列如[″P1″，″M0″，……. ，″E″]，依次讀取序列元素，存入變量op，″P1″表示放置寬度為 1 的箱子，″M0″表示搬離第 1 個箱子，代碼略'''
　　if op[0] ＝＝″P″：
　 w ＝ int(op[1：])　#表示箱子的寬度為 w
　 lst[m]＝st
　 ①________
　 st＝st＋w
　 m＋＝1
　　elif op[0]＝＝″M″：
　 i ＝ int(op[1：])　#表示第 i＋1 個箱子將被搬離
　 t＝wd[i]
　 while ：
　　　 ②________
　　　 wd[i]＝ wd[i＋1]
　　　 i＝i＋1
　 ③________
　 st＝st－t
　 m ＝m － 1
　　else：
　 break
#輸出當前貨架上所有箱子的起始位置，代碼略
(1)將程序空白處填寫完整。
(2)實現加框處功能的語句還可以是________。
答案　(1)①wd[m]＝w　②lst[i] ＝ lst[i＋1]－t
③lst[i] ＝ －1或lst[m－1] ＝ －1　(2)i解析　本題考查列表的遍歷和數據的移動。(1)①記錄當前放置箱子的寬度。②將后面所有箱子向左移動，每個箱子的開始放置位置(共178張PPT)
第二部分　算法與程序設計
專題13　簡單算法程序實現
1. 基于生活中的問題設計情境，掌握分析問題、抽象建模、設計算法、編寫程序的過程；
2.掌握利用算法解決問題的思維能力構建.
目 錄
CONTENTS
體系構建
01
真題再現
02
考點精練
03
當堂檢測
04
課后練習
05
體系構建
1
抽象和建模是用程序實現算法前的重要步驟，抽象找出影響問題的主要因素，明確已知什么和求什么。建模是描述主要因素之間的關系，一是明確方法，往往采用遍歷列表的方法；二是明確步驟，往往是求符合條件的和、個數、最值和平均值。枚舉算法簡稱枚舉法，也稱為列舉法、窮舉法，是暴力策略的具體體現，又稱為蠻力法，在遍歷過程中求值與條件進行比對的過程。枚舉法的基本思想是：逐一列舉問題所涉及的所有情形，并根據問題提出的條件檢驗哪些是問題的解，哪些應予排除。
真題再現
2
(2023年6月浙江省選考)某倉庫有一排連續相鄰的貨位，編號依次為0～n－1，用于放置A、B兩種類型的箱子，A型箱子占2個相鄰貨位，B型箱子占1個貨位。編寫程序，根據已完成的放置或搬離操作，輸出空貨位數及還可以放置A型箱子的最多數量(不移動已放置的箱子)。請回答下列問題：
箱子類型 操作類型 貨位編號
B 放置 5
A 放置 2，3
B 放置 0
A 放置 7，8
A 搬離 2，3
答案　(1) 2或兩　(2)①elif t＝＝'B' 或elif t＝＝″B″或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　單元素遍歷
遍歷是按照一定的規則和次序訪問數據元素中的所有節點，使得每個節點都被訪問一次且僅被訪問一次。相同類型的數據往往保存在數組中，數組的特點是按照索引位置依次存放數據，若只有一個數組，可以通過按值訪問的方法，對所有數據進行求和、計數、求平均值和求最大值或最小值等操作。若多個數組，他們擁有相同的索引，可以通過索引位置依次訪問數據。
例題 根據某場館一天中每位參觀者的進館和出館時間，可統計該場館當天人流量的分布情況。每個人進、出館的時間用一個長度為11的字符串表示，例如“08：05－08：45”表示進館時間為8點5分，出館時間為8點45分。現要求統計當天館內人數超過指定人數的總時長。
(1)8點01分到8點08分的進出館人數如表所示：
分鐘 01 02 03 04 05 06 07 08
進館人數 5 0 4 2 1 3 1 2
出館人數 0 1 1 1 6 3 2 2
館內大于4人的時長為________分鐘。
思維點撥
明考向 本題考查枚舉算法、多分支選擇結構
精點撥 (1)第1分鐘5人，第3、4、5分鐘分別在館人數為7，8，3，后面的都沒有超過4人，因此總時長為3分鐘。(2)①把前后兩個時間分開，分別加上in和out來區分。因此要找到“－”的位置t，當條件i[5：]＝＝″in″不成立時，取出出館的時間。②當條件i[5：]＝＝″in″成立時，表示進館，否則表示出館，當前人數cnt應減少一個。③處是一個狀態編程，當t值為－1時，表示還沒有達到目標人數時狀態，條件cnt>sp成立，且t值為－1，表示當前cnt值開始大于目標人數，因此t不是－1時，表示開始時間，當elif t>－1意味著cnt>sp不成立，表示這一段的結束時間，這一段的時間差為mts－t，把這些時間段累加起來
答案　(1)3　(2)①i[t＋1：]或 i[t＋1：len(i)]　②cnt－＝1　③sum＋＝mts－t
變式 每個人進、出館的時間用一個長度為11的字符串表示，例如“08：05－08：45”表示進館時間為8點05分，出館時間為8點45分。現要求統計當天館內人數超過指定人數的總時長，當天在館人數最多時刻及在館人數。
(1)8點01分到8點08分的進出館人數如表所示：
分鐘 01 02 03 04 05 06 07 08
進館人數 5 0 4 2 1 3 1 2
出館人數 0 1 1 1 6 3 2 2
在館人數最多時刻為________。
(2)每個參觀者進入場館和出館時間保存在“參觀記錄.txt”文件中，編寫Python程序，請將程序補充完整。
rs＝[0]*540　#存儲早上8點至下午5點每分鐘的在館人數
f＝open(″參觀記錄.txt″，encoding＝″utf－8″)
答案　(1)8：04　(2)①rs[m2]－＝1　②totrs＋＝ rs[i] ③sumrs＋＝1
解析　本題考查枚舉算法。(1)從8：01點到8：04人數變化情況依次為5，－1，3，1，在8：04分達到8人。(2)①rs存儲早上8點至下午5點每分鐘的在館人數，m2表示出館的時間，rs[m2]表示該時間的在館人數，當有一個人出館時，相應的在館人數減少一人。②從早上8點開始遍歷每分鐘在館人數，并進行累加到變量totrs中。③當累加和超過sp時，相應的時刻增加1個。
重難點2　連續多個元素遍歷
在一個序列中遍歷元素可以分為兩種情況，一是對單個元素進行遍歷，如對字符串進行加密、壓縮算法。二是要找出序列中一個連續的子序列，如找一個依次相連的子串，找一個連續遞增或遞減的子序列。在第二種情況中，將涉及該元素與他前面或后面元素的關系，因此需與他們依次進行比較，比較總次數比元素的個數少1個。
例題 現有一個文檔“壓縮前.txt”中保存了大量的小寫字母和數字，小明發現文檔中有很多字母或數字是連續的，就想設計一個算法將字符串中連續的字母或數字進行壓縮，如連續字符“abcd”可壓縮為“a－d”，不連續的字符維持原狀，例如，字符串“abcde1255hij”可壓縮為“a－e1－255h－j”，并將壓縮后的結果輸出保存到“壓縮后.txt”中。
思維點撥
明考向 本題考查一個集合中兩個元素的組合，或者是一段連續區間的開始位置和結束位置的遍歷
精點撥 (1)略。(2)當條件ord(line[i＋1])！＝ord(line[i])＋1成立時，表示連續段已經結束，終點位置是i，因此需將line[i]連接入ans中。②讀取一行數據，處理完后調用writedata函數，將壓縮后的結果輸出保存到“壓縮后.txt”中。(3)找到連續段開始位置。flag是一個是否是頭部的標志，初值為False，找到連續字符串的第1個位置后，flag的值變更為True
答案　(1)e－g1－43－5h－k　(2)① ans＋＝line[i]　②writedata(ans)　(3)ord(line[i＋1])＝＝ord(line[i])＋1 and not flag或ord(line[i＋1])＝＝ord(line[i])＋1 and flag＝＝False
變式 老年機因其較大的按鍵，很適合老年人使用，但其中英文字母的輸入方式比較麻煩，導致很多老年人不太會用。如圖是一款老年機的鍵盤，其字母的輸入方式如下：
(1)若要輸入英文字母“A”，則2鍵按1下；若要輸入“B”，
則2鍵按兩下；其他英文字母的輸入方式同理。
(2)若連續輸入的英文字母在同一數字鍵中，則在輸入下一個英文字母前，需先按下1鍵以表示確定；若連續輸入的英文字母不在同一數字鍵中，則不需要按1鍵，直接按所要輸入英文字母對應的數字鍵即可。
(3)若要輸入空格，則按0鍵。
王老師依據該手機的字母輸入規則，設計了一個 Python 程序。實現輸入按鍵被點擊的順序，顯示手機中輸入的英文內容的功能。程序運行界面如圖所示：
>>>
輸入按鍵編號順序：7999844666166
輸出的內容是：PYTHON
>>>
實現該功能的程序代碼如下：
keyboard＝{″0″：″″，″2″：″ABC″，″3″：″DEF″，″4″：″GHI″，″5″：″JKL″，″6″：″MNO″，″7″：″PQRS″，″8″：″TUV″，″9″：″WXYZ″}
yw＝input(″輸入按鍵編號順序：″)
①________
i＝k＝1
請回答下列問題：
(1)若按鍵點擊的順序是“616661666166”，則手機中輸入的英文是________。
(2)要實現程序的功能，請完善劃線處的代碼。
答案　 (1)MOON　(2)①key＝yw[0]　②i＝i＋1 ③k＝1
解析　(1)鍵6的第1個字母為M，同一數字鍵中，則在輸入下一個英文字母前，需先按下 1 鍵，鍵6的第3個字母為O，第2個字母為N。(2)查找連續相同的鍵的個數。①變量i從1開始遍歷，因此key的初值為yw[0]。若遍歷到″1″，說明是相同兩個鍵的分隔符，i的位置加1。③若不相同，則這個鍵是下一組的第1個鍵。
重難點3　雙重遍歷
當一個集合或兩個集合中元素進行組合時，往往需要對這些集體遍歷多次。可能發生的情景有：①對一個過程重復多次，如在二維表中，重復讀取一行數據，并對一行數據進行分解處理，即一個集合有多個元素，每個元素有多個數據項。還有讀取一個多行的文本文件，處理每行數據，對一個DataFrame對象進行遍歷，查詢數據項的過程等等；②在一個集合中，找出兩個數據的組合，如統計一個數據的排名，各種排序算法，冒泡、插入排序等，還可以是一個連續段的開始位置和結束位置。③在兩個集合中各取一個元素進行組合，把每一種組合遍歷一次。
例題 挖金礦游戲。在一個8行8列的矩陣中，礦工位于第1行第1列的格子，n個金礦隨機分布在第1行下面的各個格子中，每個金礦的橫坐標依次保存x數組，縱坐標保存在y數組。礦工收集金礦方法：先確定每行最左邊和最右邊金礦的坐標，對于同一行的金礦，礦工先移動到最左邊金礦正上方，再執行向下x步的指令進行挖礦，接著從該行左邊第2個金礦開始一直挖到最右邊。該行完成后，再依次挖下方各行的金礦。
如圖a所示的金礦(圖中黑色方塊)分布圖，按右側所示的指令，可以收集全部金礦。
思維點撥
答案　(1)下1挖礦下2挖礦右3挖礦或下1，挖礦，下2，挖礦，右3，挖礦　
(2)①y[beg]－py　②beg＋1，i＋1　③py＝y[i]
明考向 本題考查雙重循環結構的應用
精點撥 (1)礦工在左上角位置，下1挖到第2行第1列的礦，下2挖到第4行1列的礦，再向右移動6，挖到第4行第4列的礦。(2)beg表示每一行最左邊金礦的索引，條件x[i]＝＝x[i＋1]成立表示兩個處于同一行的金礦，因此循環結束后，索引i表示當前行最右邊的金礦的列號。①py表示礦工的列號，條件y[beg]>py成立表示最左邊礦位于礦工的右邊，需向右移動y[beg]－py個位置。②當前行可能還有多個金礦，因此當前已經挖了最左邊beg位置上金礦，還需從y[beg＋1]位置挖到第y[i]列，由于range是一個左閉右開的區間，因此值為i＋1。③更新礦工的位置，其列號為最右邊金礦的列號
變式 某物品柜有5層，每層有10個格子，每個格子只能放一個物品。輸入一組物品的高度值(按降序排列)，將這些物品放在同一層的連續格子中。第一步：查找存放物品的格子。從第1層開始查找，若該層物品柜連續空格數量小于物品數量，則查找下一層。查找5層后還是不能找到連續存放位置，輸出“不能連續存放”。若在某一層中找到符合要求的連續空格子，則進行第二步：將物品按中間高兩端低的原則存放物品。先將高度最高的物品存放在連續空格的中間位置(若空格數量為偶數，則放在中間靠左位置)，接著依次將物品按先右后左的順序依次存放。如輸入物品高度為8，5，2，1，則依次放在第1排的第5，6，4，7的位置。第一排各個格子存放物品高度如圖所示，其中0表示未存放物品。
0 0 0 2 8 5 1 0 0 0
(1)輸入第1組物品高度依次為8，5，2，第2組依次為9，6，3，1，則高度為3的物品存放在第1排第________(填數字)個格子中。
(2)實現該功能的Python程序段如下，將空白處填寫完整。
#將已經存放的物品高度存儲在數組a中，如：
[[0，9，6，2，8，5，1，0，0，0]，[0，0，1，7，10，9，2，0，0，0]，……]，代碼略。
s＝input(″輸入一組降序的物品高度，用逗號分開：″)
wp＝list(map(int，s.split(″，″)))　#輸入的數字轉換成列表
flag＝False；i＝0
while i <5 and not flag：
答案　(1)7　(2)①beg＝j＋1　②wz＝(beg＋end)∥2　③i %2＝＝0
解析　本題考查二維數組的遍歷和在一個序列中查找最值。(1)高度8，5，2依次存放第5、6、4的格子中，因此左邊還有3個空格，右邊有4個空格。高度9，6，3，1依次存放第8、9、7、10的格子中。(2)①確定連續空格子的最左邊位置beg，若格子為空，計算連續空格子數量為j－beg＋1，若數量達到存放物品數量時，將flag設置為True。若格子不為空，則下一個空格子的位置只能在當前j的下一個位置。②中間位置的計算方法類似于二分查找，將左右位置相加再整除以2。③語句a[hang][wz]＝wp[0]的功能是放置最中間的物品，接下來放在i為1的物品，在中間的右邊，即wz等于i＋1，當i的值為2時，放在左邊的前面2個位置中，因此通過判斷變量i的奇偶性來決定存放的位置。
當堂檢測
4
重難點1　單元素遍歷
重難點2　連續多個元素遍歷
重難點3　雙重遍歷
1.某智能貨架有一排貨位，貨位號從 0 開始編號，每個貨位等寬。貨架上可放置不同寬度(占 1～3 個貨位)的箱子，箱子從左往右連續相鄰擺放。每次放置箱子時，只能在貨架上最后一個箱子的右側放置新箱子。可以搬離中間的某個箱子，但該箱右側所有箱子被自動左移。編寫程序，模擬搬離或放置操作，操作結束后，輸出當前貨架上所有箱子的起始位置。
答案　(1)5　(2)①m＝m＋1　②lst[i ＋ 1]－ lst[i]　③st－dis
解析　(1)搬離第2個箱子，每個箱子向左移動3個單位，因此起始位置為5。
(2)①從語句lst[m]＝st和st＝st＋w來看，m表示箱子索引號，st表示起始位置，起始位置每次增加箱子長度，因此箱子索引也要增加。②計算移動距離，條件lst[i＋1] ！＝ －1表示后面還有箱子，因此移出箱子的距離為前后兩個箱子起始位置的差值。③語句lst[i] ＝ －1更新最后一個箱子往前移動后，少了一個箱子，因此起始位置也要相應往前移動。
解析　本題考查列表的遍歷和數據的移動。(1)①記錄當前放置箱子的寬度。②將后面所有箱子向左移動，每個箱子的開始放置位置也要發生變動，后一個箱子的開始位置就是當前箱子的結束位置，將該位置減去移動箱子的寬度，就是移動的距離。③將第m個箱子移動后，該位置初始值設置為－1。(2)一共有m個箱子，最后一個箱子的索引為m－1。
答案　(1)①wd[m]＝w　②lst[i] ＝ lst[i＋1]－t
③lst[i] ＝ －1或lst[m－1] ＝ －1　(2)i3.在一條寬度為L的直線小河中，一只青蛙想沿著直線從河的左側跳到右側。小河中有n片位置互不相同的荷葉，青蛙必須跳到荷葉上過河，否則會掉入水中。開始時青蛙站在河的左側(坐標為0)，接著不停地向右側跳躍，每次跳躍的距離不超過W，當青蛙跳到或跳過河的右側(坐標為L)時，青蛙完成過河。根據小河的長度，青蛙每次跳躍的最大長度和荷葉位置，求至少需要增加的荷葉數。
hl＝32　#小河的長度
w＝4　#青蛙每次跳躍的最大長度
a＝[0，2，9，11，17，24，30]
a.append(hl)　#起點為a[0]，終點為河長hl，把該位置加入數組a中
p＝1　#第1片荷葉的初始索引位置
d＝tot＝0　#d表示青蛙的位置
while d答案　①a[p]－d>＝w　②p＝p＋1　③d＋＝w
解析　①變量d表示青蛙所處位置，他可能在荷葉上，也可能在新增加的荷葉上，變量p表示青蛙下一步要到過的荷葉或位置，因此只有滿足條件a[p]－d>＝w才可能到達下一荷葉，若條件為a[p]－a[p－1]>＝w，當青蛙無法一步到達下一張荷葉時，雖然在else增加了荷葉，但a[p－1]的值沒有發生變化，因此還是無法達到下一張荷葉。②更新荷葉的位置。③增加了一張荷葉，更新青蛙可以到過的最大位置。
4.某平臺新上架影片推薦度的計算方式為：由5位專業評審與5位大眾評審給影片評分，評分區間為[1，10]，將專業評審均分的60%與大眾評審均分的40%進行求和并取整，根據得分確定等級(分值與等級的關系如圖a所示)。評委打分情況如圖b所示，“A”表示專業評審，“B”表示大眾評審，“A4－10”表示第4位專業評審給出10分。
分值 等級
1－2 ★
3－4 ★★
5－6 ★★★
7－8 ★★★★
9－10 ★★★★★
圖a
圖b
答案　(1)3　(2)①x＝line[0]　②pub＋＝t　③(socre＋1)∥2或 (socre－1)∥2＋1　(3)else 或 if x＝＝″B″ 或if x！＝″A″ 或elif x！＝″A″ 或其他等價表達式
解析　(1)專業評審均分為6，大眾評審均分為7，將專業評審均分的60%與大眾評審均分的40%進行求和并取整，得到3.6＋2.8＝6.4分，取整后為6，因此為3顆星。(2)①條件x＝＝″A″表示讀取每條記錄的第1個字符，因此x的值為line[0]。②語句score＝int(pro/5*0.6＋pub/5*0.4)計算綜合得分，因此pub為大眾評審，因此該值將增加1。③socre值的范圍為1－10，分為1至5共5個等級，將socre的值加1，其范圍為2至11，整除2后的值為1至5。或者將socre的值減去1，其范圍為0至9，整除2后的值為0至4，再加上1，其值范圍為1至5。
5.某小區停車場停車使用車位鎖，其中私家車車位，車主可將感應器插在私家車的USB電源接口上，感應器在30～50米內發出高頻信號(如圖a)，當私家車靠近，車位鎖自動降下解鎖，車離開(20秒后)車位鎖自動升起上鎖。其余為收費車位，可掃描二維碼控制車位鎖并收費(如圖b)。
收費車位計費規則如下：停車時長不到半小時按2元計費；半小時及以上則按每小時5元計費；超過整小時部分，不足半小時的時長不計費，半小時及以上則按一小時計費。該停車場當日的停車記錄存儲在“parking.txt”文件中，文件內容如圖c所示，每一行共有4項數據，用逗號分隔，每項數據分別為進(出)場時間、車牌號、進出場狀態(0表示進場，1表示出場)、車位狀態(0表示私家車位，1表示收費車位)。小林編寫了Python程序，從該文本文件中讀取所有數據，并計算該停車場當日的總收入。請完成下列問題：
圖a　私家車位
圖b　收費車位
圖c
答案　(1)C　(2)elif car[3]＝＝'1'
(3)①calT(dic[car[1]]，car[0])
②(T＋30)∥ 60 *price或int(T/60＋0.5)*price
解析　(1)接USB口能獲取電源，并能主動發送信息，因此屬于有源電子標簽。(2)car[2]進出場狀態，car[3]表示車位狀態，當進場狀態為0且為收費車牌時，在字典dic創建一個車牌號碼為鍵，進場時間為值的鍵值對，只有收費車牌時才計算費用，而私家車是不用計費的。①調用函數計算停車費用。calT函數的第1個參數為入場時間，第2個參數為出場時間，入場時間在dic字典中獲取，出場時間為當前記錄的時間。②計算費用。超過整小時部分，不足半小時的時長不計費，半小時及以上則按一小時計費，四舍五入計算整小時數，并按每小時5元計費。
答案　(1)ZZY　(2)①x－1>＝0 and s[x]＝＝s[x－1]　②x＋1<＝len(s)－1 and s[x]＝＝s[x＋1] ③s＋＝chr(ord(″X″)＋m)　④R－L>＝2 ⑤i＝L
解析　(1)消除過程：XYYYXXZZY→XXXZZY→ZZY。(2)①從右向左查找相鄰的兩個位置x和他前一個位置x－1是否相同，注意邊界問題。②從左向右查找相鄰的兩個位置x和他后一個位置x＋1是否相同，注意邊界問題。③隨機生成一個僅由大寫字母″X″″Y″″Z″組成長度為 n 的字符串。④向左查找的最左邊界為L，向右查找相同的最右邊界為R，消除該字符串連續3個及以上的相同字符，則R－L＋1需大于等于3。⑤消除后，i要退回到L的位置重新判斷。
2.某酒店的房間編號為1到1000，對于空余的房間的記錄，采用連續空房間的起始房間編號和連續空房間數量進行記錄，例如：有空房間1、2、3、6、7、9號時，記錄的方法為：(1，3)，(6，2)，(9，1)，共3條記錄。當有人退房時，一般出現4種情況：
·若退出房間號為4時，屬于“上靠”情況，則第1條記錄修改為(1，4)；
·若退出房間號為5時，屬于“下靠”情況，則第1條記錄修改為(5，3)；
·若退出房間號為8時，屬于“上下靠”情況，則第2條、第3條記錄合并，修改為(6，4)；
·若退出房間號為12時，屬于“不靠”情況，則新增1條記錄為(12，1)。
請回答下列問題：
(1)當已有的空房間記錄為(3，5)，(9，5)，(16，3)，(30，2)，當退出房間號為8時，空房間記錄修改為________。
(2)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
″″″
讀入已有的空房間記錄，個數為n，這些記錄已按房間起始號升序排好，每條記錄的房間起始號存入數組room，對應的連續空房間的個數存入數組num，下標均為0到n－1
″″″
x＝int(input(″請輸入退出房間號：″))
pos＝0
while　①________：
答案　(1)(3，11)，(16，3)，(30，2) (2)①pos < n and x > room[pos]
②num[pos － 1] ＋＝ 1 ＋ num[pos] ③x＋1＝＝room[pos]　④n ＋＝ 1
解析　 本題考查數組元素的插入和刪除。(1)退房前的空房間情況為3－7，9－13，8號房間退出，符合上下靠的情況，更改為3－13，16－18，30－31。(2)①找到起始空房間號room[pos]大于x房間號，為pos確保是有效索引，加上條件pos < n。②由條件“room[pos－1]＋num[pos－1]＝＝x and x＋1＝＝room[pos]”可知是屬于上下靠的情況，連續空房間數量為兩處數量之和再加1，合并操作會導致空房間記錄總數減少，for循環是將后面空房間數據前移動。③由語句room[pos]＝x; num[pos]＋＝1可知是下靠的情況。④else表示剩下是不靠的情況，需要新增一條記錄，為了保持空房間記錄的有序性，需要在pos索引處插入新記錄，故在插入前將n－1到pos的所有記錄后移一位(for循環實現)，新增記錄后，空房間記錄總數增加1。
答案　(1)6　(2)①n＝len(s)　②i解析　 (1)第1個1表示代碼以1開頭，第2個1，表示1的個數，因此有1＋5＝6個1。(2)①對n賦值為s的長度。②不斷地向后查找數字。③num表示壓縮的數的個數，將這些數解壓縮并存在ns中。
4.非空字符串s由互不相同的n個英文小寫字母按升序排列而成，可將其中連續的多個字母縮寫(如“abcd”縮寫為“a～d”，“ab”寫作“a～b”)。例如字符串“abcghijkmnopqsvwxyz”可縮寫為“a～cg－km～qsv～z”。對于s，每當輸入一個小寫字母c時，若c已存在于s中，則視為從s中刪掉此字母；否則將c插入到s中，并保持字母升序，輸出更新s后對應的縮寫字符串。請回答下列問題：
(1)如圖所示，初始時字符串為“abcghijkmnopqsvwxyz”，依次輸入“d”、“z”、“o”，在當前狀態下，更新字符串縮寫為________。
原字符串縮寫為：a～cg－km－qsv～2
→請輸入一個小寫字母：d
更新字符串縮寫為：a～dg－km～qgv～z
→請輸入一個小寫字母：2
更新字符串縮寫為：a－dg－km～qsv～y
→請輸入一個小寫字母：o
更新字符串縮寫為：
答案　(1)a～dg～km～np－qsv～y　(2)①c1＝s[i]　②pos解析　(1)輸入“d”， “abc”更新為“a～d”，輸入“z” “o”，該字符已存在，刪除該字符。(2)①c1是連續子串的最左邊的字母，當相鄰的兩個字母不相連時，更新c1。②在一個升序的子串中查找是否存在字符c，同時注意邊界問題。③若c不在字符串中，將c插入到pos的位置中。
5.某商場對所有商品按價格升序排序，按相同價格劃分成一段的方式，將數據分割成若干段，對每段數據進行壓縮，最后存儲為一個數字序列，壓縮規則如下：
①使用兩個整數x，y對一段連續相同的價格數據進行壓縮。其中x為當前段表示的商品的價格較前一段商品的價格的增值(若為第1段，則x為第1段的價格數據)，y表示當前段的數據個數(其中0≤x，y≤1000，且均為正整數)。
②將各段價格數據壓縮的結果通過“，”連接。
例如，各商品價格為“1，1，3，3，3，5，8，9，9，9，9，10”，先將連續相同的各段數據進行壓縮，然后連接各段壓縮的結果，如圖所示。
答案　(1)2，3，3，2，2，4, 　(2)①tmp ＝ tmp * 10 ＋ int(s[i])或tmp ＝ tmp*10＋ord(s[i])－ord('0')　 ②a[k] ＝ a[k － 1]　③not f　(3)ans ＋＝ j － i 或 ans ＝ ans ＋ j － i　(4)3
解析　(1)3個2表示為2，3，2個5(增量3)表示為3，2，4個7(增量2)表示為2，4，壓縮結果為2，3，3，2，2，4。(2)①變量tmp表示連續取出的數據或數據的個數，由于其值可能大于9，因此①表示取出是數字時，每次擴大10倍并加當前值計入tmp。②變量f為是否是數據的標志，值為False時表示數據，值為True時，表示數據的個數。k的初值為1，a[1]為a[0]加上第1個數據，因此a[1]存儲第1個數據。同理a[k]表示連續多個數據的第1個數據。當f值為True時，還需在數組a中添加tmp－1個數據。③f設置為False和True之間的輪流變化。(3)每次找一個最小價格和最大價格，先找到一個最大價格，保證這兩個價格之和要小于資金數量。若能找到，以最小價格購買第1個商品，另一個商品為最小價格之后到最大價格之間所有商品之一，方案數ans為兩個價格的長度減1。(4)前兩次，購買第1個商品價格為22，最大價格77，兩者和小于100。第3次，購買第1個商品價格為24，最大價格76。若購買第1個商品價格為55，另外的商品加起來超過100。
1.數據在網絡傳輸中，帶寬是寶貴的資源，通過壓縮傳輸的字符串，可以減少數據量，從而加快傳輸速度，節省帶寬資源。現有一種字符壓縮方法描述如下：對于連續的若干個相同的子串“X”會壓縮為“[DX]”的形式(D是一個整數且1≤D≤99)，如字符串“ABABABAB”就壓縮為“[4AB]”或者“[2[2AB]]”，類似于后面這種壓縮之后再壓縮的稱為二重壓縮。如果是“[2[2[2AB]]]”則是三重的。現給出一串壓縮后的結果，并對其進行解壓縮。
思路：先找出每個左括號的位置，然后從后往前枚舉，找出每一個括號內要解壓的子串以及要解壓的次數，將子串解壓后得到一個新串，重復操作，得到最終的解壓縮結果。
例如：[2[2[2AB]]]→[2[2ABAB]]→[2ABABABAB]→ABABABABABABABAB。
(1)已知采用上述壓縮方法得到的壓縮結果是“[2Z[2DB]]”，則解壓縮結果為________。
答案　(1)ZDBDBZDBDB　(2)①j＝start[i]＋1　②temp＋＝s[j]　
③ans ＋s[j＋1：]
解析　本題考查連續多個元素的遍歷。(1)解壓的過程為[2Z[2DB]] →[2Z[DBDB]] →[2ZDBZDB] →[ZDBZDBZDBZDB]。(2)①遍歷壓縮結果s，將每個″[″字符的索引位置記入start列表中。根據壓縮規則，從最內層的″[″開始解壓縮，因此需倒著遍歷start。變量j初始值為每一層最左邊位置，即″[″后面的位置。②取出每一層的數字num和子串temp，遍歷到非數字時，將字符連接到temp中。③while循環結束后，s[j]的值為″]″，在重新構造字符串過程中，只是去除當前這層中的″[″和″]″，把ans連接入新的字符串s中，因此前半部分″[″前面的字符串s[：start[i]]，后半部分為″]″后的右中括號s[j＋1：]。
2.有m個人結伴旅行(m<＝9，每人用整數1～m編號)。期間既有全員參與的集體活動，也有自主參與的小團隊活動。每項活動的消費由參與人平均分攤，其中一人先行墊付并記錄。記錄內容包括該項活動的人均消費金額(元)、參與人。每項活動的參與人用字符串表示，墊付人排在第1位。如″25134″表示2、5、1、3、4號參與該項活動，其中2號是墊付人。旅行活動結束依據所有活動的消費記錄進行結算。要求輸出轉賬明細。(編號小的付款人優先轉賬給編號小收款人)
(1)若有4個人參加3項活動，每項活動的參與人分別是“31”，“124”，“23”，每項活動的平均消費金額分別為50元，100元，300元， 則3號人員應還款項為________元。
(2)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
a＝['315', '523', '25134', '345', '41', '13524', '513', '451', '153']
x＝[50, 60, 30, 120, 75, 35, 95, 55, 30]
n＝len(a)
m＝5
#讀取所有消費記錄，顯示在屏幕中，如圖1所示，代碼略
答案　(1)250　(2)①b[p]＋＝x[i]　②c＋＝1　③w＝b[i]＋b[j]
解析　(1) 活動1：3號墊付－50元，1號應付50元；活動2：1號墊付－200元，2、4號應付100元；活動3：2號墊付－300元， 3號應付300元，因此3號應付款項－50＋300＝250。(2)①計算每個活動第2個開始的成員應付款項，x[i]表示每個活動的平均費用。②統計需要還款人的人數c，需要還款人的應付金額大于0。
③該空與變量w相關，當w大于0時，v的值為b[i]－w，同時b[i]更新為原值減去v，b[i]是大于0的，是需要轉賬的，而b[j]是小于0的，是接收轉賬的，因此w是兩者之和。
3.編排試場。每個試場有30個座位，試場號、座位號和班內序號均從1開始。對n個班級的學生編排試場，要求連續分配座位的兩個學生不屬于同一個班級。
分配方法：按班級人數降序排列，每次編排第1個班級的學生，完成一個學生考號的編排后，先將第1和第2個班級互換，再從第2個班級開始排序，當班級人數小于等于后面班級人數時，依次交換。如1班至3班的人數為36，35，35，第1試場座位號1的學生為1班學生，交換并排序后的班級依次為2，3，1，每班人數均為35人，座位號為2的學生是第1個班級(2班)。
(1)若1班至4班的人數分別38，36，36，36，則第1試場座位號為5的班級是________。
答案　(1)4　(2)①num[0]－＝1　②sch＋＝1 ③j解析　(1)座位1號分配后，人數為36，37，36，36；座位2號分配后，人數為37，36，36，35；座位3號分配后，人數為36，36，36(1班)，35(2班)，接著4班的學生。(2)①總是分配人數最多的班級bj[0]，因此分配后該班人數num[0]將減少一個。②每個試場有30個座位，到了第31人，試場數將增加一個。③與后面的數進行比較，如果小于或等于后面的班級人數，進行交換。
課后練習
5
重難點1　單元素遍歷
重難點2　連續多個元素遍歷
重難點3　雙重遍歷
答案　(1)2A2B或″2A2B″　(2)①s[i]＝＝g[i] ②cnt2[int(g[i])]＋＝1或cnt2[int(g[i])]＝cnt2[int(g[i])]＋1　③B＝B＋m或B＋＝m
解析　(1)數字位置均正確的有2個，數字對位置錯的有兩個。(2)①檢測數字s[i]和猜的數字位置g[i]是否正確，變量A為數字位置正確的個數。②cnt1用于統計s中相應數字出現的次數，cnt2用于統計猜數g中相應數字出現的次數。
③數字位置均正確的沒有統計在cnt1和cnt2中。若m＝0，說明該數字或者沒有出現過，或者只在g或s某一個出現過，此時應不計數；若m＝1，說明這個數字在g和s中均出現了1次，但沒有被統計到A中，即數字正確而位置不正確有1；若m＝2，說明數字正確而位置不正確，依次類推。
2.機器人移動路線管理。機器人在一平面內按照程序預置數據來完成移動操作(如圖a所示)，規則如下：①只能水平或垂直方向移動，方向取值：上：U、下：D、左：L、右：R，不能走斜線；每次移動1－5單位距離；②從起點出發，經過若干步后，盡可能返回到起點，如不能自動返回，則計算剩余移動次數。請完成劃線處代碼。
圖a
圖b
答案　(1)pos[0]或bp　(2)[x，y]　(3)int(line[1])
(4)new_pos[1]＝pos[1]＋y*lg　(5)p＝p＋1
解析　(1)起點坐標保存在列表bp索引為零的位置。(2)功能為輸入起點坐標，返回坐標[x，y]的值，返回值類型為列表。(3)函數調用代碼move(pos[i]，dirt[i]，step[i]), step[i]對應參數lg，lg是一個整數。(4)new_pos[0]是橫坐標，new_pos[1]是縱坐標。(5)根據returnp，可知變量p保存的是移動次數。根據p＝abs(p1－p2)∥5，如果條件語句不滿足(能整除5)，函數值就直接返回p了。
3.搶紅包游戲：微信搶紅包游戲成為一代人的經典回憶，游戲將總金額為n的“紅包”隨機分配給m個玩家，紅包的分配需同時滿足以下規則：①所有人搶到的金額總和跟總金額n相等；②每個人至少搶到1分錢；③每個人搶到的金額隨機；④每個人搶到金額大小的概率平等。
滿足以上規則的最簡單算法可描述為：假設總金額為n元，為使問題簡單化，將總金額乘以100，此時的單位為分，使得問題在整數范圍內解決。假設分發給m個人，則只需在[1，100*(n－1)]長度的范圍內隨機生成m－1個不重復的點，這些點將長為100*n的線段劃分為m個段，每一段長度即可表示紅包金額，再將每一段長度數據除以100換算為單位元輸出。程序運行的結果如圖所示。
輸入紅包金額：100
輸入紅包數量：5
紅包金額：54.4，11.59，28.09，4.09，1.84
手氣最佳：54.4
答案　①m－1　②f[n]＝True　③red ＝ i － p
解析　本題考查迭代的算法思想。 把一個長度為n*100的線段分成m段，所有線段之和為一個定值n*100，每個線段的長度代表了紅包的金額，線段長度越長，金額越大。因此先產生m－1個線段，因此①處答案為m－1。每個線段的終點位置t取到，則f[t]的值為True，最后一個線段的終點必須是n，否則金額的總和不等于n，因此②處答案為f[n] ＝ True。③p是每段的開始，初值為0，下段的起點是該段的終點，因此該段的計算方法是i － p。
4.有n名同學參加春游，已知現有公用經費total元，同時每位同學又隨身攜帶一些現金，用數組cash存儲。春游地點有不同類型自行車若干輛供游客租用，每種類型的自行車按租金從高到低存儲在數組info中。info[i]表示某類型自行車信息，包含租金和數量。其中，info[i][0]表示該類型自行車租金，info[i][1]表示該類型自行車數量。
每位同學優先使用自己攜帶的現金租車，現金不夠時可使用公用經費補足費用。為方便財務管理，規定每位同學只能為自己租用自行車，且不會相互借錢。請編寫程序計算這n個同學是否能夠全部租到自行車。
(1)若人數n＝5，total＝80，cash＝[21，15，10，8，5]，info＝[[60，1]，[50，2]，[35，2]，[25，3]]，判斷這5個同學是否都能租到自行車________(單選，填字母：A.是/B.否)。
答案　(1)B　(2)①m－n　②total－＝bike[i]－cash[j]　(3)A
解析　(1)優先安排租便宜的自行車，一共5人，需要租3輛25元的和2輛35元的，共需要25*3＋35*2＝145元，但是公用經費和每位同學自己帶的錢共80＋21＋15＋10＋8＋5＝139元，不足以租5輛自行車。(2)info存儲每種自行車的租金及庫存，兩個for循環在bike數組中添加了總共可以租的車輛m和每個車的租金。租金從高到低排列，資金能滿足租借最便宜的車子就可以了。①變量i從租金最少的第m－n開始遍歷。②現金cash[j]不夠時可使用公用經費total補足費用。(3)可以租借時，租借的車輛從m－n到m，共有n個學生借到了自行車。
5.輸入一個1－99999之間正整數金額，轉換成相應的大寫人民幣形式，處理的方式：
1)人民幣大寫形式分″零壹貳叁肆伍陸柒捌玖″共10個數字和″拾佰仟萬″4個單位。
2)從左向右向后處理每一位數字，同時讀取該位數后面的一個數字。對當前數字分0和非0兩個情況進行處理，若當前位為0，不加″拾佰仟萬″等單位，如102轉換為壹佰零貳元。
3)最后一位數單獨處理，若為0，直接在轉換后的字符串后加上“元”，否則加上對應的大寫數字和文字“元”。
實現該功能的程序代碼如下，請將劃線處填寫完整。
sn＝″零壹貳叁肆伍陸柒捌玖拾佰仟萬″
s＝input(″輸入一個大于0但小于10萬的正整數：″)
ans＝″″
for i in ①________：
答案　①range(len(s)－1)　②elif t2 ！＝0　③t1＝int(s[－1])
解析　①最后一位數單獨處理，因此先處理前面的數字。②分3種情況，當前數字0和非0，當前數字0及后面數字是0和非0。該處應填寫后面數字非0的情況。③取出最后一個數字。
1.現有一個由n位大寫字母組成的密碼串，將其分成m段長度相同的子密碼串，已知n是m的倍數。小明編寫了一個Python程序，輸入密碼串和正確的子密碼串，檢查這m段子密碼串的正確情況。若子密碼串與正確的子密碼串不完全相同，則該子密碼串錯誤，需指出錯誤字符在該子密碼串中的位置。例如，密碼串為“ABCDEFGABBDKFGABCDEFKABCDGFG”，正確的子密碼串為“ABCDEFG”，則檢查結果如圖a所示，程序運行界面如圖b所示。
圖a
圖b
(1)密碼串為“ACDEFACDEEABDEFACDFF”，正確的子密碼串為“ACDEF”，則有________段子密碼串錯誤。(填：阿拉伯數字)
答案　(1)3　(2)①k＝i*p　②j

解析　(1)略。(2)①m表示子密碼串的個數，每個子串的長度為p，因此每個子串的開始位置為i*p。②j表示子串中的位置，從0開始，到p－1為止，共有p個字符。③將每處錯誤之處記錄到errinfo數組中。
2.在僅包含星號*和小寫字母的字符串中，可以對星號進行消除。若字符串中含有除星號和小寫字母以外的其他字符，則輸出無法消除；否則按如下規則進行消除：
①從左向右依次消除一個星號，直至消除所有的星號。
②一次消除時，需要同時消去星號及星號前的一個字母，若星號前無字母，則僅消除該星號。
如對字符串″pyt**ho*n″的消除過程為：
第1次消除″t*″，字符串變為″py*ho*n″第2次消除″y*″，字符串變為″pho*n″，第3次消除″o*″，字符串變為″phn″，消除完成，結果字符串為″phn″。
(1)對字符串″*fightin**g*″消除后的結果為________。
(2)編寫程序實現上述消除，代碼如下，請完成劃線處的代碼。
s＝input(″請輸入一個字符串：″)
i＝0; flag＝True
while ①________：
答案　(1)″fight″　(2)①i②s[：i－1]＋s[i＋1：]　③not(″a″<＝s[i]<＝″z″)或s[i]<″a″ ors [i]>″z″或s[i]！＝″*″ and (s[i]<″a″ or s[i]>″z″)或not(s[i]＝＝″*″ or ″a″<＝s[i]<＝″z″)或其他等價答案　④i＋＝1
解析　(1)經過4次刪除操作，字符串依次為″fightin**g*″、″fighti*g*″、″fightg*″和″fight″。(2)①遍歷每個字符，且可以對星號進行消除，變量flag為True表示可以消除。②一次消除時，需要同時消去星號及星號前的一個字母，若星號前無字母，則僅消除該星號。
3.如果連續數字之間的差嚴格地在正數和負數之間交替，則該序列稱為擺動序列。第一個差(如果存在的話)可能是正數或負數。僅有一個元素或者含兩個不等元素的序列也視作擺動序列。對于不是擺動序列的序列，可刪除其中的部分元素，剩余元素順序不變，從而得到符合要求的擺動子序列。
例如，[1，7，4，9，2]是一個5個數字的擺動序列，因為差值[6，－3，5，－7]為正負交替出現，如圖a所示。但是[2，5，8，2，5]和[2，5，3，3，6]不是擺動序列，其中[2，5，8，2，5]的前兩個差值都為正數，如圖b所示，而[2，5，3，3，6]的倒數第二個差值為0，如圖c所示。圖b中②－⑤為遞增，⑤－⑧不為遞減，因此②－⑤－⑧中需要刪除一個數，此外圖c中⑤－③為遞減，③－③不為遞增，因此⑤－③－③中需要刪除一個元素。擺動子序列的長度均為4。
編寫程序，隨機生成n個元素的序列，輸出該序列中刪除元素后最長擺動子序列的長度。
　　　 圖a　　　 　 圖b　　　　 　圖c
(1)若序列為[3，6，4，4，2，5，7]，則該序列刪除元素后的最長擺動子序列的長度為________。
(2)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
import random
n＝int(input())
a＝[]
for i in range(①________):
答案　(1)4　(2)①n　②cnt＝1　③pre>＝0 and cur<0
解析　(1)4，其中 6－4－4－2 是一個下降區間，只能保留兩個元素。2－5－7 是一個上升區間，只能保留兩個元素。因此該序列的最長擺動子序列長度為 4。(2)①n，用于隨機生成 n 個元素，需要將 for 循環執行 n 次；②cnt＝1，首個元素一定保留，因此 cnt 的初值為 1；③pre>＝0 and cur<0，只有當前段的單調性 cur 和上一段的單調性 pre 不同時，才可確定增加了一個“擺動”。
4.某公路由于長期沒有維修，路上出現了很多個坑。為了盡快填補好這些坑，交通管理部門決定對m處地段采取交通管制。將該公路看成一條直線，坑就是直線上的坐標點，坑所在的路段需要封控管制。例如某管制路段2～4，需封控2、3、4路段。交管部門為了減少管制路段的長度，希望將這n個坑分成m段(一段可以只有一個坑)，使得這m段公路的總長度最小。請你根據n個坑的位置(位置已按照從小到大進行排序)，計算管制路段最小的總長度。代碼運行效果如圖所示。
路段數量：4
坑的坐標依次為：3，4，6，8，14，15，16，17，21，25，26，27，30，31，40，41，42，43
維修管制的路段依次為：
3～8
14～17
21～31
40～43
管制總長度為25
答案　(1)22　(2)①not flag[j]　②t＝i＋1 ③dis＋s[n－1]－s[t]＋1
解析　(1)若將4段分成5段，只需要其中一段中兩個坑之間間隔最大的分割，在這里最大的為21～25，分割之后長度減少了3，故總長度為22。(2)①根據程序的輸出結果，可知變量dis為最后的總長度，最后一個循環中變量t為每一段起始位置的下標，i為末尾位置的下標，flag[i]表示s[i]與s[i＋1]是否分割。故當輸出每一段之后，dis加上每一段的舉例，變量t要更新為i＋1，故②處填寫t＝i＋1。當結束循環，還有最后一段的長度未加上，最后一段為s[t]～s[n－1]，則③處填寫為dis＋s[n－1]－s[t]＋1。根據flag數組的含義，當flag[k]為True表示s[k]與s[k＋1]已經分割，則下一次找分割位置時，必須為未分割的部分，故①處填寫not flag[j]。
5.小明編寫一個 Python 程序，實現找到字符串 s1 和 s2 中相同的最長子串s，并定位子串在字符串 s2 中出現的位置，運行結果如圖所示。
s1：Python
s2：thanks tnanks thanks
最長共同子串：　th
子串出現位置：
0/7/14/
(4)主程序，請在劃線處填入合適的代碼。
s1 ＝ input(″s1：″)
s2 ＝ input(″s2：″)
s ＝　____________
print(″最長共同子串：″， s)
pos(s，s2)
答案　(1)h　(2)①s1[i － 1] ＝＝ s2[j － 1]　②h ＝ i　(3)start ＋＝ 1　(4)longstr(s1, s2)
解析　(1)只有一個共同字符h。(2)m是一個len(s2)＋1行len(s1)＋1列的二維列表，其每個元素的初值均為0。外循環i遍歷字符串s1，內循環j遍歷字符串s2，當兩個字符串中字符相等時，那么長度是前一次相等的基礎上加1，t表示具有相同字符的最大個數，找到最大個數時，需記錄其位置i。因此①表示兩個位置上字符相等，其索引位置為i－1和j－1。②為最大長度的結束位置h。(3)對st的每個位置start從0開始遍歷，則start不斷地向后移動。(4)longstr函數，功能是找到字符中s1和s2中相同的最長子串，此處調用longstr(s1，s2)函數找出相同的最長字串賦值給變量s，故填longstr(s1，s2)。
答案　(1)①qa[i]<＝h　②i＋1，n
③qa[j]>h and abs(qa[i]－qa[j])(2)qb[i]＋qb[j]＝＝imax
解析　(1)①條件一QA值都必須大于指定參數h，若條件不滿足直接枚舉下一個人。②組合問題，他與后面的所有人員進行組合，保存不會重復，因此i枚舉到n－2，每趟從i＋1開始枚舉到n－1。③檢測j人員是否滿足條件1以及條件2是否滿足。(2)當最大值有兩個或兩個以上的情況。
2.現代詩的連排格式為各句以“/”分開，例如余光中先生的《鄉愁》的部分內容為：″小時候/鄉愁是一枚小小的郵票/我在這頭/母親在那頭/長大后/鄉愁是一張窄窄的船票/我在這頭/新娘在那頭″，現以右起豎式形式打印這部分內容，如圖所示。請回答下列問題：
(1)若按照右起豎式對“ABC/CBDA”進行打印，打印內容的第三行為________。
解析　本題考查字符串遍歷、拼接等相關操作。(1)第三行為“/”分隔的兩部分的第3個字符，即“ABC”中的C和“CBDA”中的D，由于是右起豎式形式，所以D在C的前面。(2)①遍歷字符串poem，將“/”分隔每部分t添加到列表s中，當前字母c不是“/”，將字母c連接到變量t的后面。②找出“/”分隔每部分的最大長度，因此變量n為列表s中字符串數量len(s)。③豎排的最大行數為maxlen，變量i表示行的索引；變量j 的范圍從0到n－1，因此表示列表s每個字符串，當s[j]的長度大于行索引時，就將該字符串第i個索引位置的字母連接到t的前面。
答案　(1)DC 　(2)①t ＝ t ＋ c　②n ＝ len(s)　③len(s[j]) － 1 >＝ i或len(s[j]) > i或等價表達式
3.有n列磚組成的一面磚墻，每列磚由數量不等的磚塊組成，每塊磚的長寬高都為1。小明為了美化這面墻，需要在這面墻中找到一塊面積最大的矩形用于涂鴉。如圖a所示，有6列高度依次為2、1、5、6、2、3組成的磚墻，圖b和圖c是其中的兩種方案。編寫Python程序，找出面積最大的矩形，并輸出其位置和面積。
答案　(1) 10　(2)①range(i，n)　②s ＝ minh*(j－i＋1)　③maxs ＝ s
解析　本題考查根據題意建模，代碼的分析理解能力。(1)由高度5和6組成的矩陣面積為10，達到最大值。(2)①從當前磚頭i開始，不斷地向后遍歷。②矩形面積取決于寬度和高度，變量i，j表示寬度的開始和結束位置，向后查找構成矩形的最小高度minh，根據寬度j－i＋1計算對應的面積；③更新最大面積maxs的值為s。
電影名稱 搞笑鏡頭 擁抱鏡頭 打斗鏡頭 影片類型
寶貝當家 45 2 9 喜劇片
唐人街探案 23 3 17 喜劇片
我的特工爺爺 6 4 21 動作片
…… …… …… …… ……
泰坦尼克號 9 39 8 愛情片
羅馬假日 9 38 2 愛情片
新步步驚心 8 34 17 愛情片
圖a
電影名稱 搞笑鏡頭 擁抱鏡頭 打斗鏡頭 影片類型
美人魚 19 18 5 ？
圖b
距離最近的前5部影片為：
唐人街探案19.62，羅馬假日 22.56，新步步驚心 22.83, 泰坦尼克號 23.45，我的特工爺爺 24.92
圖c
請回答下列問題：
(1)與《美人魚》距離最近的前5部影片如圖c所示，則該影片屬于________(單選，填字母：A.喜劇片 /B.動作片 /C.愛情片)。
答案　(1)C　(2)1　(3)①data[i][j]－x[j]或x[j]－data[i][j]　②dic[data[p][4]]＋＝1　③k－＝1
解析　(1)距離最近的5部影片中，喜劇片1部，愛情片3部，動作片1部，因此該影片類型為愛情片。(2)在存儲標記為False的位置中，查找最小值的索引，43，33，65三個數中最小值索引為1。(3)①遍歷所有的樣本數據data，計算出“美人魚”與樣本中所有影片的距離。data[i][1]、data[i][2]、data[i][3]分別表示樣本數據中搞笑鏡頭、打斗鏡頭、擁抱鏡頭的值，用變量j表示這些下標，計算與x[j]的平方差的和。②調用mvmin函數計算最小距離的索引p，即對應的樣本的索引，在數組元素data[p][4]中存儲的是該影片的類型，需要對該類型的數量增加1。③處理下一個樣本數據。
5.某校圖書館提供 3 類自習室，A 類最多容納 2 人，B 類最多容納 4 人，C 類最多容納 8 人，以 1 小時為單位進行預約，每人每天只能預約一次，每次預約僅限個人，規定預約時間結束之前必須離開。圖書館每天 6 點開館，22 點閉館。編寫程序，輸入某自習室號牌，根據已預約情況，輸出該自習室還能被預約的時間段。例：讀取“A102”已預約情況[[6，11], [15，18], [8，12], [15，22]]，其中“A102”表示為 A 類 102 號自習室，[6，11]表示某個人預約 6：00 開始，11：00 前必須離開，時間占用如圖所示，則該自習室還能預約的時間段為[[6，8]，[11，15]，[18，22]]。請回答下列問題：
答案　(1)[[6，8], [11，22]]　(2)①period[1]　②ringt＝i或right＋＝1　③i＋＝1或i＝i＋1
解析　(1)[6，11]表示某個人預約6：00開始，11：00前必須離開，因此6－7點還可以容納2人，8－10點已經約了4人，11點還可以容納2人，12－22點還可以容納4人。(2)①遍歷各個預約時間段，將各個預約時刻記錄到預約的人數bucket數組中，period表示每個預約時間段，period[0]是預約的開始時間，period[1]是預約的離開時間。②條件bucket[i]6.上城小學將在本學期開展趣味運動會，一(10)班的班主任邀請你為他們設計一個Python程序，用于挑選參加集體項目的選手。挑選規則為：當班級有足夠候選人員時，進行隨機挑選，并輸出人員名單；若無足夠人員時，提示“無足夠候選人員參加比賽！”，并規定每個學生最多參加一個集體項目。程序要求用戶按照規范輸入比賽項目及相關人員要求，例如輸入“投籃：8，2”即籃球項目要求男生8人，女生2人。該程序的運行效果如圖所示：
請輸入比賽項目及相關人員要求：跳繩：5，5，
趕豬：15，15；投籃：8，2
跳繩項目：
男：艾震宇　蔡溫淼　葉埕奇　王子碩
女：王曉清　黃鑫櫞　陳佳妮　陳昱彤　陳奕臻
趕豬項目：
無足夠侯選人員參加比賽！
投籃項目：
男：陳展驄　李俊翰　張子俊　劉泓成　胡海偉　王子涵　葉賽特　伍越
女：賈熙　錢梓涵
(1)實現挑選集體項目選手的Python代碼如下，程序中用到的列表函數與方法如表所示，請在劃線處填入合適代碼。
函數與方法 功能
w.append(x) 在列表w末尾添加元素x
x＝w.pop(i) 將列表w末尾下標為i的元素賦值給x，并將其從w中刪除
解析　本題考查列表的方法實現。(1)①自定義函數player的功能是輸出列表前n個元素，并刪除這些元素。表中所示x＝w.pop(i)將列表w末尾下標為i的元素賦值給x，并將其從w中刪除，因此下標i的值為0。②ctemp數組存儲男生和女生名單，因此需遍歷c數組的每個元素p，并根據p[0]的值進行相應的處理。③分別處理男生和女生的情況，因此需重復2次。(2)player函數是處理一個一維數組，即分別處理男生和女生的名單。
答案　(1)①xm＝x.pop(0)　②p
③range(len(ctemp))或range(2)
(2)ctemp[i]＝player(ctemp[i]，sj[t][i])
7.某校舉行趣味運動賽，共有n個比賽項目，每班派n位學生參加，每位同學分別參加一個項目。某班有n位選手報名參加比賽，現需要依據他們平時練習中各個項目的平均得分，找出最佳參賽組合，查找規則為各項目得分總和最大，例如：圖a所示的數據中，最佳參賽組合是“唐昌新：跳繩，胡鵬：飛鏢，楊勝超：顛球，陳偉：套圈”。完成下劃線的代碼。
圖a
最佳參賽組合：
唐昌新　跳繩
胡鵬　 飛鏢
楊勝超 　顛球
陳偉　 套圈
圖b
答案　①f[i]＋＝1　②k∥n　③a[j][s[j]＋1]　④max＝sum
解析　①數組f是一個桶，f[i]用于記錄i的數組，遍歷到i，就對f[i]加1操作，當f[i]大于1，說明有重復。②共有n個比賽項目，每班派n位學生參加，每位同學分別參加一個項目。參加為1，不參加為0，可以看成是n位二進制數，每一位代表一位同學，有兩種可能性。因此有n**n種可能性，將k轉換成對應的二進制數。③將n位選手各項成績進行累加。④更新最大值為sum。
8.某影廳共12排，每排10座。座位編號以排號＋座號來命名，如第10排3座，編號命名為103。某一時刻，該影廳的最佳觀影區為方框內的座位如圖所示，即第5排3座～第10排8座的矩形位置。0表示該座位可選，非0表示已售(1表示系統推薦，2表示手工選擇)
座位推薦算法：
(Ⅰ)只推薦最佳觀影區的座位，并且所有座位號要連號。
(Ⅱ)優先選擇最佳觀影區內最中間的位置(若空位數為偶，則選擇中間靠左)，若中間位置相同，則以靠前位置為佳。
(Ⅲ)若在最佳觀影區內未找到可以推薦的座位時，系統將提示手工選擇。
(1)如圖所示的座位中，若要購買2張票，則推薦的排號是________
(2)實現上述功能的Python程序如下，請在劃線處填入合適的代碼。
#產生一個12行10列的二維數組，并隨機產生座位情況，代碼略
k＝int(input(″請輸入購票數：″))
kwz＝0；wz＝[]
m＝12；n＝10
for i in range(4，10)：　#尋找中間空的座位，并把座位號保存到數組wz中。
答案　(1)6　(2)①kwz＋＝1
②wz[p＋k－1]－wz[p] ＝＝ k－1
③ s＝p
解析　本題考查數組的遍歷。按規則，第5排選擇第4、5列，第6排選擇第5、6列，第6排更靠中間。(2)①尋找中間空的座位，并把座位號保存到數組wz中，從條件p＋k－19.某網約巴士，車上最初有12個空座位，從起點站向終點站行駛，不允許掉頭或改變方向，現有新的訂單，請判斷其是否能預約成功。請回答下列問題：
(1)若網約巴士已預約成功的數據為：[2，1，5]，[1，3，7]，[3，2，8]，[2，4，7]，[3，5，10]，其中每個元素有3個數據項，分別表示預約人數、出發站點和到達站點，當前接到訂單[4，5，8]，________(選填：能/不能)預約成功。
(2)實現上述功能的部分Python程序如下，請在劃線處填入合適的代碼。
#數組trips存儲預約信息，trips[i]＝[num，start，end]表示第i個預約信息有num個乘客，出發站點為start，到達站點為end，站點編號為1～10。
total＝12　#空座位總數
stations＝10　#站點總數
diff＝[0]*(stations＋1)
count＝[0]*(stations)　#存儲站點上下車后的乘客人數
答案　(1)不能　(2)①diff[i[1]]＋＝i[0]　②1，j＋1或0，j＋1或j＋1或j，0，－1，或j，－1，－1　③count[i]＋num>total或num>total－count[i]
解析　(1)用如表格的第2－6行表示每個訂單每個站臺的變化人數，最后一行表示該車從該站臺開出時的總人數。
站臺 1 2 3 4 5 6 7 8 9 10
單1 2 2 2 2 －2 　 　 　 　 　
單2 　 　 1 1 1 1 －1 　 　 　
單3 　 3 3 3 3 3 3 　 　 　
單4 　 　 　 2 2 2 －2 　 　 　
單5 　 　 　 　 3 3 3 3 3 －3
人數 2 5 6 8 7 9 3 3 3 －3
站臺6當前有9個，加上4人超出12人。
(2)①遍歷預約信息trips，有num個乘客，出發站點為start，到達站點為end，因此start站要加上num個乘客。②數組diff存儲每站的變化人數，因此每站實際人數統計0至j站的變化人數的累加和。③車上最初有total個座位，當前站總人數為與當前站將要上車人數num之和不能超出座位總數total。

展開更多......

收起↑