硬币--翻转 - 文章详情

硬币--翻转

2022-08-19 10:06:22

故事起源

有n个硬币，每个硬币可能正面或者反面朝上。

如果每次翻转一个硬币，在进行一定次数的翻转后，就可以使所有的硬币都正面朝上或者反面朝上，即状态一致。

请问是否存在一个固定的次数k，使得初始时无论是哪种状态，都可以刚好进行k次翻转，以达到全部正面或反面朝上的状态呢？如果存在，那这个小的k是多少？

分析

先从简单的场景开始分析。
如果只有1个硬币，它正面或者反面都可以，因为没有其它可对比的，所以状态都一致，不用翻转，那么小的k就是0。

如果有2个硬币，那么初始时可能有以下3种状态：2个正面，2个反面，1正1反。

针对以上第1、2种状态，不需要翻转，而第3种至少需要翻转1次。如果都翻转一次，前面的2种状态又会不一致，所以无法找到一个固定的翻转次数k。

如果有3个硬币，对于初始状态就一致的就不用再考虑了，小0次。

主要考虑不一致的，例如有1个、2个...m个不一致。

可以看出，如果n个硬币，其中m个正面，那必定有n-m个反面，可以认为它是m个不一致，也可以认为是n-m个不一致，这2种情况是等价的，那就考虑更小的吧，因为更简单。

再回到上面的3个硬币的情况，只需要考虑有1个正面和有2个正面。
如果都翻转1次，可以使所有的一致，但对于初始时全部相同的情况也必须翻转1次，就一定会产生不一致，所以1次不行。

如果都翻转2次，则一定可以。如果1个正面，就翻转另外2个反面；如果2个正面，就直接翻转这2个正面；如果全部相同，则对任何一个翻转2次，依然不改变一致的状态。所以3个硬币的小k就是2。

那到这里你看出规律了吗，先别往下看，思考2分钟，3,2,1...
有不一样的想法可打在下面的评论区

规律

到了开始总结规律、提取特征信息的时候了，不要限制你的想象，发散思维。

1.首先对于任何一个硬币，翻转奇数次一定改变状态，翻转偶数次一定不改变状态。
既然翻转偶数次不变，为啥还要翻转呢，当然是为了凑数，因为要求必须刚好都翻转k次。

2.k必须是偶数。如果初始状态一致，翻转奇数次一定会将某一个状态改变，变成不一致，所以k不可能是奇数。

3.n如果是偶数，则一定找不出来这样的k。
例如下面这种场景，只有1个反面，有n-1个正面。1和n-1都是奇数，所以无论是全部翻转成正面或是反面，都需要奇数次翻转，偶数次不可能一致，所以n为偶数时无解。

4.关键的来了，对于n为奇数时一定有解，那小的k应该是多少呢？
n为奇数，所以正面和反面肯定就是一奇一偶。

考虑这种极端情况，只有1个反面，n-1个正面，这时n-1为偶数。

如果终要全部为正面，则只能一直翻转这1个反面，但翻转偶数次并不变，明显不行。所以只能终全部为反面，那就得翻转剩下的n-1个正面，至少也得n-1次。

好了，规律找到了，接下来开始coding吧。

代码实现

当然这个问题的难点并不在coding，这只是推理成功之后的附属品。

if ((n & 1) == ) printf("No Solution!\n");
    else printf("%d\n", n - 1);

总结

这个问题主要就是要从本质上找出规律，推理了一大堆，结果异常的简单，但这些推理却是绕不开的。其实有很多看似复杂的问题，终的结论都是非常的简单。有个经验分享给大家，如果你发现你解决一个问题时逻辑非常的复杂，要考虑很多分支情况，这时我可以大概率的猜测，90%你的方法是不对的，因为正解永远都是非常优雅简洁的。(如果不优雅，那一定不是正解)

本文原创作者：小K，一个思维独特的写手。
文章平台：微信公众号【小K算法】。

如果喜欢小K的文章，请点个关注，分享给更多的人，小K将持续更新，谢谢啦！

分享好友

分享这个小栈给你的朋友们，一起进步吧。

数据库开发

创建时间：2020-06-17 14:33:07

数据库开发是数据库管理系统(DBMS)和数据库应用软件设计研发的总称，主要是数据运维、参与数据库生产环境的问题优化和解决等方面的事宜

展开

订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅：虚拟交易，一经交易不退款；若特殊情况，可3日内客服咨询

• 专区发布评论属默认订阅所评论专区（除付费小栈外）

技术专家

查看更多

小雨滴
专家