【全球独家】宁波市2022学年第一学期选考模拟卷第16题解析
新教材怎么教,取决于新高考怎么考。新高考的题目类型如何分布?题目难度如何?一直是老师们最为关心的问题。
(资料图)
在仅有课标和教材,没有考纲和样卷的情况下,各类名校和联盟的命题老师们认真思考、努力探索,为大家提供了多份质量上乘、极具参考价值的联考模拟卷。
认真研究这些模拟卷,分析它们的命题思路和解题方法,总结题型和算法框架,不仅有利于高考备考,对新课教学也有很大的借鉴意义。
宁波市2022学年第一学期选考模拟卷第16题
一题目16. 魔术师预先将一副牌中的13张黑桃(A为1,J为11,Q为12,K为13)排好后叠在一起,牌面朝下。他将最上面的那张牌翻过来,正好是黑桃A。将黑桃A放在桌子上,然后按顺序从上到下数手上的余牌:第二次数1、2,将数到的第一张牌放在这叠牌的下面,将第二张牌翻过来,正好是黑桃2,将它放在桌子上;第三次数1、2、3,将前面两张依次放在这叠牌的下面,再翻第三张牌,正好是黑桃3,放在桌子上。这样依次进行,将13张牌全翻出来,最后桌子上牌的顺序是A、2、...... K。问魔术师手中的牌原始顺序是怎样的?小王和小李对问题进行了分析与算法设计,写了Python函数way()正确解答了问题,请回答下列问题。(1)原来牌的顺序中,黑桃3放在自上向下第(填阿拉伯数字)个位置。(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())二考查知识点模拟算法、一维数组和队列基本操作,要求学生理解使用循环队列模拟数牌过程的算法,掌握一维数组和队列基本操作,深切理解数组下标从0开始。
三解析题目考查循环队列基本操作。循环队列与队列的区别在于队头指针和队尾指针加1以后要对13求余数,以实现循环出入队列的功能。我们依次把牌面值添加到数组b中,可以发现第一轮(红色字体)分别翻出牌面值为1、2、3、4的牌,它们所处位置分别是第1、3、6、10张牌,故第(1)题答案为6。翻牌问题其实是约瑟夫环问题的一个变形,每张牌的位置就相当于每个人所站的位置,牌可以被拿走,但位置编号(取值范围1-13)一开始就确定了,并存储在数组a中,将元素值减1,则恰好对应其下标。程序使用数组b存储牌面的原始顺序,故我们可以用b[a[i]-1]表示位置a[i]处的牌面,这是第③空的算法依据。设置变量i作为牌的编号(牌面值),外层循环让i从1开始依次递增。循环体内模拟数数过程,cnt为计数器,while循环重复(i-1)次,通过出队和入队操作,把上方的(i-1)张牌转移到下方,故第①空答案为a[head],第②空答案为cnt += 1。第③空的作用是从循环队列中取出队头元素a[head],此时翻出的牌面值为i,其在数组b中的下标恰好为(a[head]-1),故第③空答案为b[a[head]-1] = i。本题程序使用循环队列模拟数牌过程,把每张牌的位置存储在队列a中。通过出队和入队操作,把上方的牌转移到下方;被翻出的牌则只出队不入队,并设置翻牌处的牌面值为i。算法逻辑清晰,代码实现简明,问题难度适中,是一道经典的好题。四答案(1)6
(2)① a[head]
② cnt += 1
③ b[a[head]-1] = cnt 或 b[a[head]-1] = i
五拓展思考题目程序使用队列a存储了每张牌的位置(取值范围1-13),需要将元素值减1后才能对应数组b的下标,稍微绕了一点弯路;我们可以直接在队列a中存储数组b的下标。此外,题目程序默认总共有13张牌,数据量稍微有些大;我们可以将程序推广到n张牌的情形。例如当n=4时,牌的编号依次为1,4,2,3。翻牌问题其实是约瑟夫环问题的一个变形,它将原问题的固定报数上限改成从1到n逐次递增,返回被翻牌的位置编号,并为该位置设置牌面值。解决约瑟夫环问题(翻牌问题)的方法很多,常用一维数组、循环单链表或循环队列来存储位置编号。可以把题目修改如下:已知有n张牌依次编号为1-n,洗牌后叠在一起,牌面朝下。现在按规则翻牌,翻开第1张牌,牌面恰好为1,将它放在桌子上;第二次边拿牌边数数,将数到的第一张牌放在这叠牌的下面,将第二张牌翻过来,牌面恰好为2,将它放在桌子上;第三次数1、2、3,将前面两张依次放在这叠牌的下面,再翻第三张牌,牌面恰好为3,放在桌子上。以此规则继续翻牌,直至将n张牌全翻出来,依次翻出牌的顺序是1、2、...... n。请问原来n张牌从上到下牌面值依次为多少?参考样例:当n=4时,牌面值依次为1,4,2,3;当n=5时,牌面值依次为1,3,2,5,4。(1)当n=6时,牌面值依次为 。(2)下面分别使用自定义函数way_1(),way_2(),way_3()实现设置牌面值功能,请将缺失的代码补充完整: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 = ②
③# 设置a[i]处的牌面为m
a[i] = -1 # 标记a[i]被删除
return b
def way_2(n):
a = [[i, i+1] for i in range(n)]
a[n-1][1] = 0 # 构造循环单链表
b = [0] * n # 0代表牌面未定
pre = n - 1 # 指向头节点的前驱节点
for m in range(1,n+1):
for j in range(m-1): # 依次将m-1张牌放到牌堆底部
pre = ④
p = a[pre][1] # 指向翻牌位置
⑤# 设置翻牌位置的牌面为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
# 主函数部分
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
写在后面为了保证解析的原创性和思维的独特性,我都是独立解题后,先不看答案(除非题目不会做),直接把解析写好,再去看答案。
当然,如果发现参考答案有更好的思路,我还是很乐于学习和借鉴的。同时,由于本人水平有限,解析中难免出现疏漏甚至错误之处,敬请谅解。
无论是赞同还是反对我的看法,都请你给我留言。如果你有新的想法,千万不要憋在心里,请发出来大家一起讨论。让我们相互学习,共同进步!
需要本文word文档、源代码和课后思考答案的,可以加入“Python算法之旅”知识星球参与讨论和下载文件,“Python算法之旅”知识星球汇集了数量众多的同好,更多有趣的话题在这里讨论,更多有用的资料在这里分享。
我们专注Python算法,感兴趣就一起来!
相关优秀文章:
阅读代码和写更好的代码
最有效的学习方式
Python算法之旅文章分类
相关阅读
-
世界热推荐:今晚7:00直播丨下一个突破...
今晚19:00,Cocos视频号直播马上点击【预约】啦↓↓↓在运营了三年... -
NFT周刊|Magic Eden宣布支持Polygon网...
Block-986在NFT这样的市场,每周都会有相当多项目起起伏伏。在过去... -
环球今亮点!头条观察 | DeFi的兴衰与...
在比特币得到机构关注之后,许多财务专家预测世界将因为加密货币的... -
重新审视合作,体育Crypto的可靠关系才能双赢
Block-987即使在体育Crypto领域,人们的目光仍然集中在FTX上。随着... -
简讯:前端单元测试,更进一步
前端测试@2022如果从2014年Jest的第一个版本发布开始计算,前端开发... -
焦点热讯:刘强东这波操作秀
近日,刘强东发布京东全员信,信中提到:自2023年1月1日起,逐步为...