【算法趣题】 Q03 翻牌

作者：简单的happy    天善智能社区专栏作者

博客地址：https://www.hellobi.com/u/jasmine3happy/articles

前文传送门：

问题描述

有100张写着数字1~100的牌，并按顺序排列着。最开始所有牌都是背面朝上放置。我现在从第2张牌开始，隔一张牌翻牌。然后第2，4，6，...，100张牌就会变成正面朝上。

接下来，你从第3张牌开始，隔2张牌翻牌（原本背面朝上的，翻转成正面朝上；原本正面朝上的，翻转成背面朝上）。再接下来，另一个人从第四张牌开始，隔3张牌翻牌（见下图）。

像这样，从第n张牌开始，每隔n-1张牌翻牌，直到没有可翻动的牌为止。（《程序员的算法趣题》P11）

问题

求当所有牌不再变动时，所有背面朝上的牌的数字。

思路

根据问题描述，按顺序对牌进行翻转处理即可。我们用数组来保存是否正面朝上的状态，分别用0，1表示，即背面朝上为0，正面朝上为1。因此第一步初始化数组，即生成一个长度为100，元素都为0的数组：

s = [0] * 100

假设初始状态所有牌都是背面朝上表示  i=0 的初始状态

从第2张开始翻牌，即第一轮翻牌表示为 i=1 状态，在这一轮里，第2、4、6...100张牌会被翻转过来，按照python里数组的索引来表示，即j = 1、3、5、...、99位上的牌将会被翻转，即满足 (j+1) % (1+1)==0。

当i=2，则从第3张开始翻牌，在这一轮里，索引号j = 2、5、8、...、98位上的牌会被翻转过来，即满足 (j+1) % (2+1)==0。

当i=3，则从第4张开始翻牌，在这一轮里，索引号j = 3、7、11、...、99位上的牌会被翻转过来，即满足 (j+1) % (3+1)==0。

即对于第i轮翻牌时，满足 (j+1)%(i+1)==0 的 j 位置上的牌将会翻转，翻转的含义：

当s[j]=0时，s[j]将会变成1；当s[j]=1时，s[j]将会变成0；

当所有牌不再变动时，所有背面朝上的牌即满足s[j]==0，牌上的数字即为 j+1。

python实现

因此，答案就是1，4，9，16，25，36，49，64，81，100

更多深入思考，你可以试试。

Python爱好者社区历史文章大合集：

福利：文末扫码立刻关注公众号，“Python爱好者社区”，开始学习Python课程：

关注后在公众号内回复“课程”即可获取：

小编的Python入门视频课程！！！

崔老师爬虫实战案例免费学习视频。

丘老师数据科学入门指导免费学习视频。

陈老师数据分析报告制作免费学习视频。

玩转大数据分析！Spark2.X+Python 精华实战课程免费学习视频。

丘老师Python网络爬虫实战免费学习视频。