環(huán)球滾動:2022年11月溫州一模第15題解析
隊列和棧是非常重要的兩種數(shù)據結構,教材也安排了大量的篇幅來介紹這兩種數(shù)據結構的基本特征和基本操作,因此它們的基本特征和操作肯定是要考的。
但是如何在編程題中考查隊列和棧的應用?它會考到何種難度?我們該教到何種程度?這就讓老師們犯了難。因為涉及到隊列和棧的算法題都不簡單,一不小心就會進入到廣搜和深搜等較為復雜的領域。
命題老師們一直在模糊的邊界摸索,試圖找到一些既能考查隊列和棧的基本操作,又不涉及復雜算法的案例,絞盡腦汁、用心良苦,為大家在前方趟雷,逐步拓展命題的邊界。
【資料圖】
2022年11月溫州一模第15題
一題目二考查知識點數(shù)組、字典、棧的基本操作,自定義函數(shù)和查找最值算法。要求學生理解字典的表示方法,熟練掌握棧的基本操作。
三解析本題考查了數(shù)組、字典和棧等數(shù)據結構、查找最值算法,綜合性相當強,難度較大。題目的問題是計算拿走幾片圓盤后,能看到的圓盤顏色種數(shù)最多?但程序實現(xiàn)并沒有模擬拿走圓盤的過程,而是逆向思維,觀察從下往上逐漸堆疊圓盤時,最多能看到幾種顏色。
為了找到最優(yōu)解,程序構造了一個棧,用來存儲能夠被看到的圓盤編號,因為圓盤入棧的順序是從下往上,為了確保棧中圓盤都能被看到,則其半徑值必須是一個遞減序列。所以每次將編號為i的圓盤入棧時,必須先將半徑小于r[i]的元素退棧。
此外,因為題目要求的不是最多能看到的圓盤數(shù)量,而是最多能看到的顏色種類,故相同顏色的圓盤只能算1個。為此程序創(chuàng)建了一個字典f,用來存儲某種顏色對應的圓盤數(shù)量。當有元素退棧時,當前可見顏色數(shù)量cnum不一定會減少,只有當某種顏色的圓盤數(shù)量為0時,才將cnum的值減1。這就是第①空的算法原理。
新圓盤入棧后,cnum的值不一定會加1,只有當f中不包含棧頂圓盤顏色時,才將cnum的值加1,否則只讓該顏色對應的圓盤數(shù)量加1。接下來判斷cnum是否為最優(yōu)解,若為最優(yōu)解,則更新存儲最優(yōu)解的變量cmax、res和m——它們分別存儲了最大可見顏色數(shù)量、可見顏色種類及其對應圓盤數(shù)量(注意不能寫作res=f,否則res與f會指向同一對象)和拿走圓盤的數(shù)量。
搞清楚算法原理以后,各問題的答案就呼之欲出了:
圓盤i入棧前,先要將半徑小于r[i]的圓盤出棧,以保持棧中元素的遞減特性。故函數(shù)pop()的作用是將半徑小于rad的圓盤出棧,返回新的棧頂指針(top)和可見的顏色數(shù)量(cnum)。
color[z[top]]表示棧頂圓盤的顏色,圓盤出棧后,其所屬顏色的圓盤數(shù)量要減1,即f[color[z[top]]] -= 1。當該種顏色的圓盤數(shù)量為0時,需要將cnum的值減1。由此得到第①空的答案f[color[z[top]]] == 0。
第②空語句的功能是將編號為i的圓盤入棧,即z[top] = i。
第③空是計算被拿走圓盤的數(shù)量,因為此時疊放的圓盤數(shù)量為(i+1),故m=n-(i+1)。
為代碼添加注釋如下圖所示:
四答案(1)將半徑小于rad的圓盤出棧,返回新的棧頂指針(top)和可見的顏色數(shù)量(cnum)。
(2)① f[color[z[top]]] == 0
② z[top] = i
③ m=n-(i+1)
五拓展思考此題程序采用逆序思維,逐個疊加圓盤數(shù)量,并通過維護一個遞減棧來記錄可見圓盤編號,以便快速計算可見顏色數(shù)量,使用字典f來記錄當前可見顏色種類及其對應圓盤數(shù)量信息,構思非常巧妙。
正因為程序的技巧性太強,引入了較多的變量,代碼實現(xiàn)蜿蜒曲折,不夠直觀,增加了閱讀難度,學生得分率很低。
我們也可以采用正向思維,直接模擬拿走圓盤的過程。計算有哪些圓盤可以看到,就好比尋找一個遞增序列。我們通過遍歷r[i:],尋找以r[i]為首元素的遞增序列;并創(chuàng)建列表c,用c[i]存儲以圓盤i為頂盤時的可見顏色字符串,每當遞增序列中出現(xiàn)一種新顏色的圓盤,將該顏色添加到c[i]中。
當出現(xiàn)最優(yōu)解時,可設置m = i,則不僅可以用m表示拿走圓盤的數(shù)量,還可以用c[m]表示最大可見顏色字符串。
實現(xiàn)相關功能的程序代碼如下,請將缺失的代碼補充完整:
r = [5, 8, 4, 6, 3, 9] # 從上向下依次給圓盤編號0,1,2,...
color = ["紅", "橙", "綠", "藍", "紫", "紅"]
n = len(r)
print("序號\t半徑\t顏色\t")
for i in range(1, n+1):
print(f"{i}\t{r[i-1]}\t{color[i-1]}\t")
c = []# c[i]是一個字符串,記錄了以盤子i為頂盤時的可見顏色
m = 0
for i in range(n):
c.append(color[i]) # 記錄能看見的盤子顏色
p = i # 當前能看見的盤子下標
for j in range(i+1, n):# 尋找以r[i]為首元素的遞增序列
if r[j] > r[p]:
p =①
if②:
c[i] += color[j]
if len(c[i]) > len(c[m]):
m = ③
print("拿走", m, "片后,可看到圓盤的顏色種數(shù)最多,分別為: ", c[m])
六拓展思考答案①j
② color[j] not in c[i]
③ m = i
寫在后面為了保證解析的原創(chuàng)性和思維的獨特性,我都是獨立解題后,先不看答案(除非題目不會做),直接把解析寫好,再去看答案。
當然,如果發(fā)現(xiàn)參考答案有更好的思路,我還是很樂于學習和借鑒的。同時,由于本人水平有限,解析中難免出現(xiàn)疏漏甚至錯誤之處,敬請諒解。
無論是贊同還是反對我的看法,都請你給我留言。如果你有新的想法,千萬不要憋在心里,請發(fā)出來大家一起討論。讓我們相互學習,共同進步!
需要本文word文檔、源代碼和課后思考答案的,可以加入“Python算法之旅”知識星球參與討論和下載文件,“Python算法之旅”知識星球匯集了數(shù)量眾多的同好,更多有趣的話題在這里討論,更多有用的資料在這里分享。
我們專注Python算法,感興趣就一起來!
相關優(yōu)秀文章:
閱讀代碼和寫更好的代碼
最有效的學習方式
Python算法之旅文章分類
相關閱讀
-
世界熱推薦:今晚7:00直播丨下一個突破...
今晚19:00,Cocos視頻號直播馬上點擊【預約】啦↓↓↓在運營了三年... -
NFT周刊|Magic Eden宣布支持Polygon網...
Block-986在NFT這樣的市場,每周都會有相當多項目起起伏伏。在過去... -
環(huán)球今亮點!頭條觀察 | DeFi的興衰與...
在比特幣得到機構關注之后,許多財務專家預測世界將因為加密貨幣的... -
重新審視合作,體育Crypto的可靠關系才能雙贏
Block-987即使在體育Crypto領域,人們的目光仍然集中在FTX上。隨著... -
簡訊:前端單元測試,更進一步
前端測試@2022如果從2014年Jest的第一個版本發(fā)布開始計算,前端開發(fā)... -
焦點熱訊:劉強東這波操作秀
近日,劉強東發(fā)布京東全員信,信中提到:自2023年1月1日起,逐步為...