圆圈报数游戏-第13届蓝桥杯国赛Python真题解析

文摘   教育   2024-07-04 20:45   湖北  

[导读]:超平老师的Scratch蓝桥杯真题解读系列在推出之后,受到了广大老师和家长的好评,非常感谢各位的认可和爱。作为回馈,超平老师计划推出《Python蓝桥杯真题解析100讲》,这是解读系列的第94讲。

圆圈报数游戏,本题是2022年5月29日举办的第13届蓝桥杯青少组Python编程国赛真题编程部分第3题。题目要求编程模拟圆圈报数游戏,男生X人女生Y人围成一圈,从1开始报数,报K的同学退圈,直到所有女生退圈,请计算男生应该分别排在什么位置并输出。

先来看看题目的要求吧。

01
题目说明 

时间限制:3000MS

内存限制:589824K8

编程实现:

某班级男生人数为X人,女生人数为Y人,现全班同学围成一个圆圈,并按照顺时针方向为每名同学编号(从1到X+Y)。

现给出一个正整数K[ 2 < K <(X + Y)],从编号为1的同学开始顺时针方向报数,报到K的同学退出圆圈,下一名同学继续从1报数,再次报到K的同学退出圆圈。如此循环,直到剩余人数为X时游戏结束。

请你计算出游戏开始时X名男生分别应该排在什么位置,才能保证每次离开的都是女生,游戏结束时剩余X人都是男生,并将游戏开始时每名男生的位置编号按照从小到大的顺序输出。

例如:X = 5,Y = 3,K = 3,8名同学按照如下顺序排列,可以使3轮报数过后最后剩余的5名同学都为男生(蓝色为男生位置,红色为女生位置)。

故5名男同学的编号分别为2, 4, 5, 7, 8。

输入描述:

输入三个正整数,X, Y, K(3  ≤ X  ≤ 100,3  ≤  Y  ≤ 100,2  ≤ K  ≤ (X + Y)),X表示男生,Y表示女生,报数为K的同学退出圆圈,三个正整数之间以一个空格隔开

输出描述:

将每名男生位置编号按照从小到大的顺序输出,编号之间以一个空格隔开

样例输入:

5 3 3

样例输出:

2 4 5 7 8

评分标准:

  • 10分:能正确输出一组数据;

  • 10分:能正确输出两组数据

  • 15分:能正确输出三组数据

  • 15分:能正确输出四组数据。
02
思路分析 

这是一道简单的算法题,涉及的知识点包括循环、条件、列表和模拟算法等。

又是经典的约瑟夫报数问题,之前有过详细的分析,可以参考《报数游戏-第12届蓝桥杯选拔赛Python真题精选》这篇教程。
既然是相同的问题,解决方案也基本一样,也就是模拟算法。所不同的是,本题最后要留下来的X个男生,其数量通常是多个。
针对本题,仍然给出两种解法:
  • 列表模拟法
  • 队列模拟法
1. 列表模拟法
使用列表模拟时,为了让大家更好理解这个过程,可以先假定所有人都是男生,以x = 5,y =3 ,k = 3为例,创建列表如下:
['男','男','男','男','男','男','男','男']
同时使用变量i表示每个人的编号,num表示要报的数字。
接下来循环遍历列表模拟每个人的报数情况,需要处理如下3个关键点:
1). 当numk时,将对应的列表项改为'女',然后将num重新设置为从1开始报数;
2). 当i超出列表范围时,需要将i设置为0,重新开始报数;
3). 当女生人数等于y时,结束循环;
循环结束,列表如下所示:
['女','男','女','男','男','女','男','男']
然后再遍历列表,获取列表项为'男'的编号2、4、5、7、8,这就是我们要的结果。
2. 队列模拟法

队列是指一种特殊的列表,其特殊之处在于它只允许队头进行删除操作,通常称为出队,而在队尾进行插入操作,通常称为入队。

我们还是以x = 5,y =3 ,k = 3为例,将每个人的编号保存到队列中,如下:
[123456, 7, 8]
然后循环处理,当报到数字k = 3时,将元素出列,否则就将该元素移到队尾,当队列长度为x = 5时,结束循环。
第1个人(队头元素),报数字1,将其移到队尾,如下:
[2, 3, 4, 5, 6, 7, 8, 1]
第2个人(队头元素),报数字2,将其移到队尾,如下:
[3456781, 2]
第3个人(队头元素),报数字3,直接出列,如下:
[4567812]
第4个人(队头元素),报数字1,将其移到队尾,如下:
[5678124]
第5个人(队头元素),报数字2,将其移到队尾,如下:
[67812, 45]
第6个人(队头元素),报数字3,将其出列,如下:
[7812, 4, 5]
第7个人(队头元素),报数字1,将其移到队尾,如下:
[812457]
第8个人(队头元素),报数字2,将其移到队尾,如下:
[124578]
第1个人(队头元素),报数字3,将其出列,如下:
[24578]
此时,队列的长度为5,结束循环,队列中的数字就是所有男生的编号。

思路有了,接下来,我们就进入具体的编程实现环节

03
编程实现 
根据上面的思路分析,我们使用两种方法编写程序:
  • 列表模拟法

  • 队列模拟法

1. 列表模拟法

根据前面的思路分析,我们编写代码如下:

代码不少,说明3点

1). i表示第几个人,初始值从1开始,因此在访问列表时,需要使用i -1;

2). num表示要报的数字,初始值为0,循环时,先将num加1,表示要报的数字,如果数字等于k,则表示该位置应该是女生,修改元素,同时将y减1,num重新设置为0;

3). 第16行注释的代码,可以打印出每个人报的数字,你可以加上,方便测试和查看效果。

2. 队列模拟法

根据前面的分析,编写代码如下:

代码不多,强调4点:

1). 这里使用的是队列的思想,但仍然使用列表来模拟实现,你也可以直接使用队列deque;

2). 由于要报的数字在1 ~ k之间,因此这里使用了取模运算符%;

3). 如果报到数字k,说明是女生,直接将这一项删除,这里的pop(0)就表示删除第一项,也就是所谓的队头元素,如果没有报到数字k,说明是男生,将这一项移到队尾

4). 最后得到的列表,顺序可能不是从小到大,因此需要使用sort函数排序。

至此,整个程序就全部完成了,你可以输入不同的数据来测试效果啦。
04
总结与思考 
本题代码在12 ~ 20行左右,涉及到的知识点包括:
  • 循环语句;

  • 条件语句;

  • 列表操作;

  • 输入输出;

这是本次国赛的第3题,分值为50分,难度中等,关键是如何使用程序来模拟循环报数的过程,尤其是要处理好细节。

Python中的列表是一个动态数组,你可以在任意位置进行插入、删除和访问元素。同时还提供了大量的方法(函数),可以模拟各种数据结构,比如栈、队列,链表等,功能十分强大,一定要熟练掌握。

超平老师给你留一道思考题,如果使用队列deque来实现队列操作,代码该如何实现呢?

你还有什么好的想法和创意吗,也非常欢迎和超平老师分享探讨。

如果你觉得文章对你有帮助,别忘了点赞和转发,予人玫瑰,手有余香😄

需要源码的,可以添加本人微信

另外,超平老师创建了一个蓝桥杯备考交流群,这是专门为老师和家长打造的免费社群,您可以与来自全国各地的老师、家长共同交流经验,分享学习心得。

超平老师也会给大家带来及时的赛事动态,备考攻略,真题资源分享,帮助各位更好备考第15届蓝桥杯赛事,力争取得优异的成绩。

扫码或长按加入微信群

超平的编程课
青少儿编程教育专家,中国人民大学硕士,大学讲师,曾任知名上市机构金牌讲师,16年编程教研经验。大耳猴少儿编程联合创始人,致力于通过编程教育提升孩子的逻辑思维、数学思维和计算思维,迎接AI时代。
 最新文章