說在前面

新教材怎么教，取決于新高考怎么考。新高考的題目類型如何分布？題目難度如何？一直是老師們最為關(guān)心的問題。

在僅有課標(biāo)和教材，沒有考綱和樣卷的情況下，各類名校和聯(lián)盟的命題老師們認(rèn)真思考、努力探索，為大家提供了多份質(zhì)量上乘、極具參考價值的聯(lián)考模擬卷。

【資料圖】

認(rèn)真研究這些模擬卷，分析它們的命題思路和解題方法，總結(jié)題型和算法框架，不僅有利于高考備考，對新課教學(xué)也有很大的借鑒意義。

寧波市2022學(xué)年第一學(xué)期選考模擬卷第16題

一題目16. 魔術(shù)師預(yù)先將一副牌中的13張黑桃（A為1，J為11，Q為12，K為13）排好后疊在一起，牌面朝下。他將最上面的那張牌翻過來，正好是黑桃A。將黑桃A放在桌子上，然后按順序從上到下數(shù)手上的余牌：第二次數(shù)1、2，將數(shù)到的第一張牌放在這疊牌的下面，將第二張牌翻過來，正好是黑桃2，將它放在桌子上；第三次數(shù)1、2、3，將前面兩張依次放在這疊牌的下面，再翻第三張牌，正好是黑桃3，放在桌子上。這樣依次進(jìn)行，將13張牌全翻出來，最后桌子上牌的順序是A、2、...... K。問魔術(shù)師手中的牌原始順序是怎樣的？小王和小李對問題進(jìn)行了分析與算法設(shè)計，寫了Python函數(shù)way()正確解答了問題，請回答下列問題。（1）原來牌的順序中，黑桃3放在自上向下第（填阿拉伯?dāng)?shù)字）個位置。（2）請在劃線處填入合適的代碼。def way(): a = [i for i in range(1, 14)] b =[0]*13 # 0代表牌面未定 head = 0; tail = 0 for i in range(1, 14): cnt = 1 while cnt < i: a[tail] = ① head = (head + 1) % 13 tail = (tail + 1) % 13 ② ③ head = (head + 1) % 13 return bprint(way())二考查知識點

模擬算法、一維數(shù)組和隊列基本操作，要求學(xué)生理解使用循環(huán)隊列模擬數(shù)牌過程的算法，掌握一維數(shù)組和隊列基本操作，深切理解數(shù)組下標(biāo)從0開始。

三解析題目考查循環(huán)隊列基本操作。循環(huán)隊列與隊列的區(qū)別在于隊頭指針和隊尾指針加1以后要對13求余數(shù)，以實現(xiàn)循環(huán)出入隊列的功能。我們依次把牌面值添加到數(shù)組b中，可以發(fā)現(xiàn)第一輪（紅色字體）分別翻出牌面值為1、2、3、4的牌，它們所處位置分別是第1、3、6、10張牌，故第（1）題答案為6。翻牌問題其實是約瑟夫環(huán)問題的一個變形，每張牌的位置就相當(dāng)于每個人所站的位置，牌可以被拿走，但位置編號（取值范圍1-13）一開始就確定了，并存儲在數(shù)組a中，將元素值減1，則恰好對應(yīng)其下標(biāo)。程序使用數(shù)組b存儲牌面的原始順序，故我們可以用b[a[i]-1]表示位置a[i]處的牌面，這是第③空的算法依據(jù)。設(shè)置變量i作為牌的編號（牌面值），外層循環(huán)讓i從1開始依次遞增。循環(huán)體內(nèi)模擬數(shù)數(shù)過程，cnt為計數(shù)器，while循環(huán)重復(fù)（i-1）次，通過出隊和入隊操作，把上方的（i-1）張牌轉(zhuǎn)移到下方，故第①空答案為a[head]，第②空答案為cnt += 1。第③空的作用是從循環(huán)隊列中取出隊頭元素a[head]，此時翻出的牌面值為i，其在數(shù)組b中的下標(biāo)恰好為（a[head]-1），故第③空答案為b[a[head]-1] = i。本題程序使用循環(huán)隊列模擬數(shù)牌過程，把每張牌的位置存儲在隊列a中。通過出隊和入隊操作，把上方的牌轉(zhuǎn)移到下方；被翻出的牌則只出隊不入隊，并設(shè)置翻牌處的牌面值為i。算法邏輯清晰，代碼實現(xiàn)簡明，問題難度適中，是一道經(jīng)典的好題。四答案

（1）6

（2）① a[head]

② cnt += 1

③ b[a[head]-1] = cnt 或 b[a[head]-1] = i

五拓展思考題目程序使用隊列a存儲了每張牌的位置（取值范圍1-13），需要將元素值減1后才能對應(yīng)數(shù)組b的下標(biāo)，稍微繞了一點彎路；我們可以直接在隊列a中存儲數(shù)組b的下標(biāo)。此外，題目程序默認(rèn)總共有13張牌，數(shù)據(jù)量稍微有些大；我們可以將程序推廣到n張牌的情形。例如當(dāng)n=4時，牌的編號依次為1,4,2,3。翻牌問題其實是約瑟夫環(huán)問題的一個變形，它將原問題的固定報數(shù)上限改成從1到n逐次遞增，返回被翻牌的位置編號，并為該位置設(shè)置牌面值。解決約瑟夫環(huán)問題（翻牌問題）的方法很多，常用一維數(shù)組、循環(huán)單鏈表或循環(huán)隊列來存儲位置編號。可以把題目修改如下：已知有n張牌依次編號為1-n，洗牌后疊在一起，牌面朝下。現(xiàn)在按規(guī)則翻牌，翻開第1張牌，牌面恰好為1，將它放在桌子上；第二次邊拿牌邊數(shù)數(shù)，將數(shù)到的第一張牌放在這疊牌的下面，將第二張牌翻過來，牌面恰好為2，將它放在桌子上；第三次數(shù)1、2、3，將前面兩張依次放在這疊牌的下面，再翻第三張牌，牌面恰好為3，放在桌子上。以此規(guī)則繼續(xù)翻牌，直至將n張牌全翻出來，依次翻出牌的順序是1、2、...... n。請問原來n張牌從上到下牌面值依次為多少？參考樣例：當(dāng)n=4時，牌面值依次為1,4,2,3；當(dāng)n=5時，牌面值依次為1,3,2,5,4。（1）當(dāng)n=6時，牌面值依次為 。（2）下面分別使用自定義函數(shù)way_1()，way_2()，way_3()實現(xiàn)設(shè)置牌面值功能，請將缺失的代碼補(bǔ)充完整：

def way_1(n):

a = [i for i in range(n)]

b = [0] * n # 0代表牌面未定

i = 0

for m in range(1,n+1):

cnt = 1

while ① : # 依次將m-1張牌放到牌堆底部

if a[i] >= 0:

cnt += 1

i = (i + 1) % n

while a[i] == -1: # 跳過已刪除元素

i = ②

③# 設(shè)置a[i]處的牌面為m

a[i] = -1 # 標(biāo)記a[i]被刪除

return b

def way_2(n):

a = [[i, i+1] for i in range(n)]

a[n-1][1] = 0 # 構(gòu)造循環(huán)單鏈表

b = [0] * n # 0代表牌面未定

pre = n - 1 # 指向頭節(jié)點的前驅(qū)節(jié)點

for m in range(1,n+1):

for j in range(m-1): # 依次將m-1張牌放到牌堆底部

pre = ④

p = a[pre][1] # 指向翻牌位置

⑤# 設(shè)置翻牌位置的牌面為m

a[pre][1] = ⑥# 刪除a[p]

return b

def way_3(n):

a = [i for i in range(n)]

b = [0] * n # 0代表牌面未定

head = tail = 0

for i in range(1,n+1):

for j in range(i-1): # 依次將i-1張牌放到牌堆底部

a[tail] = ⑦

head = (head + 1) % n

tail = ⑧

⑨

head = (head + 1) % n

return b

# 主函數(shù)部分

n = 6

print(way_1(n))

print(way_2(n))

print(way_3(n))

六拓展思考答案

（1）1, 4, 2, 5, 6, 3

（2）① cnt < m

② (i + 1) % n

③ b[a[i]] = m

④ a[pre][1]

⑤ b[a[p][0]] = m

⑥ a[p][1]或a[a[pre][1]][1]

⑦ a[head]

⑧ (tail + 1) % n

⑨ b[a[head]] = i

寫在后面

為了保證解析的原創(chuàng)性和思維的獨特性，我都是獨立解題后，先不看答案(除非題目不會做)，直接把解析寫好，再去看答案。

當(dāng)然，如果發(fā)現(xiàn)參考答案有更好的思路，我還是很樂于學(xué)習(xí)和借鑒的。同時，由于本人水平有限，解析中難免出現(xiàn)疏漏甚至錯誤之處，敬請諒解。

無論是贊同還是反對我的看法，都請你給我留言。如果你有新的想法，千萬不要憋在心里，請發(fā)出來大家一起討論。讓我們相互學(xué)習(xí)，共同進(jìn)步！

需要本文word文檔、源代碼和課后思考答案的，可以加入“Python算法之旅”知識星球參與討論和下載文件，“Python算法之旅”知識星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。

我們專注Python算法，感興趣就一起來！

相關(guān)優(yōu)秀文章：

閱讀代碼和寫更好的代碼

最有效的學(xué)習(xí)方式

Python算法之旅文章分類

關(guān)鍵詞： 一維數(shù)組 基本操作 從上到下