今天分享一道非常著名的笔试题，曾经在多个大厂招聘中出现过， 有时在笔试题里面，有时面试环节中。其实主要是考察程序员对这类问题的处理的算法和思路，到底难不难的呢，菜鸟也能手撕这道大厂的题，不信今天我就给大家庖丁解牛看看。
1
硬币分类
题目：
现在我有27枚硬币，其中有一枚假币，假币跟真币长得一摸一样，但是稍微重一些。摆在桌上有一个称重天平，要求用最小的次数找出假币，并写出算法代码。
经常面试的同学是不是有点面熟这道题目，碰到这样的题目，千万不要慌，也不要上来就动笔。正确的姿势是应该先想好算法，再下笔敲键盘。如果你上来都没有思考，就开始胡子眉毛一把抓，一定会自乱阵脚，浪费时间不说，还会败下阵来！
1
算法和思路
首先我们要思考一下这个问题的解法，大部分人一上来想到的都说对开。就是把硬币分成两份，比如假如我们有9个硬币，各4各一份，然后对这个4个硬币进行称重。那么可能有3个结果：
1).运气最好的情况，两份完全相等，剩下的1个就是假币
2).第一组更重，然后继续二分称重
3).第二组更重，然后继续类似上面第二种情况进行称重
我们需要3次才能找到，这个是不是最优的解法呢，显然不是，何况现在的题目是27枚硬币！
正确的姿势是什么的，我们应该采用的是分而治之的方法，我们还是先拿简单的9枚举例，把9枚硬币分成3份，3，3，3，然后称重，应该是3种结果：
1).第一组和第二组一样重，那么假的在第三组里面，再称一次即可找出；
2).第一组更重，那么假的在第一组，再称一次即可;
3).第二组更重，那么假的在第二组，再称一次即可;
这个的算法，看起来更简介，大概需要2次，如果是27枚，只要多分一次9,9,9 ,最后3次即可。
3
算法Python实现
理清了思路，下面就是开始准备写代码了。我们一点一点庖丁解牛似的来写算法，整个算法无非要解决3个问题:
-
第一，把硬币分3组；
-
第二，把分组的硬币称重;
-
第三，遍历寻找最重的里面的假币
整块的问题，我们已经分解成小块的了。下面就是把整个的算法用代码实现，然后串起来即可。
1).分组问题
拿到一串硬币，我们需要分成3等份，直接用切片把列表切割一下即可。
2).硬币称重
两种硬币进行称重对比，这个其实用一行代码也能搞定，但是那样写的话，阅读起来不清洗，其实我个人觉得if/elif/else 蛮好的。
3).寻找假币
这个里面分两步走，第一步先寻找假币，就是给你3组，进行判断
很好理解，如果第一组和第二组对比称重，左边重，那么假币就在第一组中；如果第二组重，就是右边重，那么假币就在第二组重，如果都不是，假币在第三组中。
4).遍历寻找
times 用于记录搜索的次数，而search_list是一个可变的列表，每次称重完了之后，它会变成三分之一的长度，不断的缩小，直到搜索结束。
其实这样分而治之一步一步的解析这道题目，看起来也不是很难的。类似的问题有很多，比如水桶问题，过桥的问题，还有蜡烛烧绳子的问题。这些常见的面试题，对于菜鸟来说一定一定要提前准备，老鸟也能温故而知新。
都说算法是程序的灵魂，要想功力深，先把算法弄成针！加油把，少年！
最后留个彩蛋，悄悄的说一句，上面的代码其实思考不成熟，有一个bug！哪位厉害的同学看出来，可以在留言区吱一声。
<p style="margin-right: 8px;margin-left: 8px;letter-spacing: 0.544px;"><span style="color: rgb(0, 122, 170);font-size: 16px;"><strong>近期热门：</strong></span></p><ul class="list-paddingleft-2" style="width: 577.422px;"><li><section style="margin-right: 8px;margin-left: 8px;letter-spacing: 0.544px;line-height: 1.75em;"><span style="text-decoration: underline;font-size: 16px;"><strong><span style="text-decoration: underline;color: rgb(0, 0, 0);">Github获8300颗星，<strong style="white-space: pre-wrap;color: rgb(63, 63, 63);letter-spacing: 0.544px;"></strong><strong style="white-space: pre-wrap;color: rgb(63, 63, 63);letter-spacing: 0.544px;">用Python开发的命令行版网易云音乐</strong></span></strong><strong>！</strong></span></section></li><li style="font-size: 16px;"><section style="margin-right: 8px;margin-left: 8px;letter-spacing: 0.544px;line-height: 1.75em;"><span style="text-decoration: underline;font-size: 16px;"><strong>这个微信神器厉害了，必须安利<br /></strong></span></section></li><li style="font-size: 16px;"><section style="margin-right: 8px;margin-left: 8px;letter-spacing: 0.544px;line-height: 1.75em;"><span style="text-decoration: underline;font-size: 16px;"><strong>学Python还是Java, 7张漫画带你全面分析<br /></strong></span></section></li><li style="font-size: 16px;"><section style="margin-right: 8px;margin-left: 8px;letter-spacing: 0.544px;line-height: 1.75em;"><span style="text-decoration: underline;font-size: 16px;">太赞了！Python学习宝典，GitHub标星3.9K！223个小例子，一次让你吃个够！<br /></span></section></li></ul><pre style="letter-spacing: 0.544px;line-height: inherit;"><section data-mpa-template="t" mpa-from-tpl="t"><section data-id="94086" data-color="#276ca3" data-tools="135编辑器" mpa-from-tpl="t"><section><section mpa-from-tpl="t"><section style="text-align: center;"><span style="font-size: 16px;color: rgb(255, 41, 65);"><strong>程序员GitHub</strong><br /></span></section><p style="text-align: center;"><img class="rich_pages" data-ratio="1" data-s="300,640" data-type="jpeg" data-w="1280" style="box-sizing: border-box !important;visibility: visible !important;width: 225px !important;" src="https://www.zkxjob.com/wp-content/uploads/2022/05/wxsync-2022-05-bba84664290a01f6369d914188525574.jpeg" /></p><p style="text-align: center;"><span style="font-size: 16px;">菜鸟学Python原班人马打造</span></p><p style="text-align: center;"><span style="font-size: 16px;">专注于分享GitHub上有趣的资源包括</span></p><p style="text-align: center;"><span style="font-size: 16px;">Python，Java，Go语言</span></p><p style="text-align: center;"><span style="font-size: 16px;">前端学习<span style="letter-spacing: 0.544px;">等优质的学习资源</span></span></p><p style="text-align: center;"><span style="font-size: 16px;">分享程序员圈的新鲜趣事，热门干货，职场感悟</span></p><p style="text-align: center;"><br /></p><pre style="letter-spacing: 0.544px;line-height: inherit;"><section data-mpa-template="t" mpa-from-tpl="t"><section data-id="94086" data-color="#276ca3" data-tools="135编辑器" mpa-from-tpl="t"><section style="text-align: right;"><section mpa-from-tpl="t" style="display: inline-block;"><pre style="letter-spacing: 0.544px;line-height: inherit;"><pre data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-style="letter-spacing: 0.544px; background-color: rgb(255, 255, 255); text-align: center; color: rgba(230, 230, 230, 0.9); font-size: 16px; line-height: 25.6px; overflow-wrap: break-word !important;" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgba(230, 230, 230, 0.9)" data-darkmode-original-color-15882396318564="rgba(230, 230, 230, 0.9)" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgba(230, 230, 230, 0.9)" data-darkmode-original-color-15900529136199="rgba(230, 230, 230, 0.9)" class="js_darkmode__5" style="letter-spacing: 0.544px;text-align: center;color: rgba(230, 230, 230, 0.9);line-height: 25.6px;"><section class="js_darkmode__7"><section data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(230, 230, 230)" data-darkmode-original-color-15860613985508="rgb(0, 0, 0)" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(230, 230, 230)" data-darkmode-original-color-15870356070738="rgb(0, 0, 0)" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(230, 230, 230)" data-darkmode-original-color-15870356071023="rgb(0, 0, 0)" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(230, 230, 230)" data-darkmode-original-color-15882384789136="rgb(0, 0, 0)" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(230, 230, 230)" data-darkmode-original-color-15882396318564="rgb(0, 0, 0)" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(230, 230, 230)" data-darkmode-original-color-15900529136199="rgb(0, 0, 0)" style="display: inline-block;clear: both;"><section data-tools="135编辑器" data-id="91842" data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(230, 230, 230)" data-darkmode-original-color-15860613985508="rgb(0, 0, 0)" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(230, 230, 230)" data-darkmode-original-color-15870356070738="rgb(0, 0, 0)" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(230, 230, 230)" data-darkmode-original-color-15870356071023="rgb(0, 0, 0)" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(230, 230, 230)" data-darkmode-original-color-15882384789136="rgb(0, 0, 0)" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(230, 230, 230)" data-darkmode-original-color-15882396318564="rgb(0, 0, 0)" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(230, 230, 230)" data-darkmode-original-color-15900529136199="rgb(0, 0, 0)" style="letter-spacing: 0.544px;border-width: 0px;border-style: none;border-color: initial;"><section data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(230, 230, 230)" data-darkmode-original-color-15860613985508="rgb(0, 0, 0)" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(230, 230, 230)" data-darkmode-original-color-15870356070738="rgb(0, 0, 0)" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(230, 230, 230)" data-darkmode-original-color-15870356071023="rgb(0, 0, 0)" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(230, 230, 230)" data-darkmode-original-color-15882384789136="rgb(0, 0, 0)" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(230, 230, 230)" data-darkmode-original-color-15882396318564="rgb(0, 0, 0)" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(230, 230, 230)" data-darkmode-original-color-15900529136199="rgb(0, 0, 0)" style="display: inline-block;clear: both;"><section data-brushtype="text" data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(230, 230, 230)" data-darkmode-original-color-15860613985508="rgb(0, 0, 0)" data-darkmode-bgimage-15860613985508="1" data-style="padding: 18px 15px 20px 10px; color: rgb(86, 146, 214); text-align: center; letter-spacing: 1.5px; background-image: url('https://www.zkxjob.com/wp-content/uploads/2022/05/wxsync-2022-05-a2a8a5e1e58f30392066a170034ee027.png'); background-size: 100% 100%; background-repeat: no-repeat; overflow-wrap: break-word !important;" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(230, 230, 230)" data-darkmode-original-color-15870356070738="rgb(0, 0, 0)" data-darkmode-bgimage-15870356070738="1" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(230, 230, 230)" data-darkmode-original-color-15870356071023="rgb(0, 0, 0)" data-darkmode-bgimage-15870356071023="1" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(230, 230, 230)" data-darkmode-original-color-15882384789136="rgb(0, 0, 0)" data-darkmode-bgimage-15882384789136="1" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(230, 230, 230)" data-darkmode-original-color-15882396318564="rgb(0, 0, 0)" data-darkmode-bgimage-15882396318564="1" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(230, 230, 230)" data-darkmode-original-color-15900529136199="rgb(0, 0, 0)" data-darkmode-bgimage-15900529136199="1" class="js_darkmode__bg__0 js_darkmode__8" style="padding: 18px 15px 20px 10px;background-size: 100% 100%;background-image: url('https://www.zkxjob.com/wp-content/uploads/2022/05/wxsync-2022-05-a2a8a5e1e58f30392066a170034ee027.png');color: rgb(86, 146, 214);letter-spacing: 1.5px;background-repeat: no-repeat;"><section data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(230, 230, 230)" data-darkmode-original-color-15860613985508="rgb(0, 0, 0)" data-darkmode-bgimage-15860613985508="1" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(230, 230, 230)" data-darkmode-original-color-15870356070738="rgb(0, 0, 0)" data-darkmode-bgimage-15870356070738="1" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(230, 230, 230)" data-darkmode-original-color-15870356071023="rgb(0, 0, 0)" data-darkmode-bgimage-15870356071023="1" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(230, 230, 230)" data-darkmode-original-color-15882384789136="rgb(0, 0, 0)" data-darkmode-bgimage-15882384789136="1" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(230, 230, 230)" data-darkmode-original-color-15882396318564="rgb(0, 0, 0)" data-darkmode-bgimage-15882396318564="1" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(230, 230, 230)" data-darkmode-original-color-15900529136199="rgb(0, 0, 0)" data-darkmode-bgimage-15900529136199="1" style="display: flex;justify-content: center;align-items: center;"><section data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(230, 230, 230)" data-darkmode-original-color-15860613985508="rgb(0, 0, 0)" data-darkmode-bgimage-15860613985508="1" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(230, 230, 230)" data-darkmode-original-color-15870356070738="rgb(0, 0, 0)" data-darkmode-bgimage-15870356070738="1" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(230, 230, 230)" data-darkmode-original-color-15870356071023="rgb(0, 0, 0)" data-darkmode-bgimage-15870356071023="1" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(230, 230, 230)" data-darkmode-original-color-15882384789136="rgb(0, 0, 0)" data-darkmode-bgimage-15882384789136="1" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(230, 230, 230)" data-darkmode-original-color-15882396318564="rgb(0, 0, 0)" data-darkmode-bgimage-15882396318564="1" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(230, 230, 230)" data-darkmode-original-color-15900529136199="rgb(0, 0, 0)" data-darkmode-bgimage-15900529136199="1" style="margin-left: 2px;width: 20px;"></section><section data-brushtype="text" data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(51, 51, 51)" data-darkmode-original-color-15860613985508="rgb(51, 51, 51)" data-darkmode-bgimage-15860613985508="1" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(51, 51, 51)" data-darkmode-original-color-15870356070738="rgb(51, 51, 51)" data-darkmode-bgimage-15870356070738="1" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(51, 51, 51)" data-darkmode-original-color-15870356071023="rgb(51, 51, 51)" data-darkmode-bgimage-15870356071023="1" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(51, 51, 51)" data-darkmode-original-color-15882384789136="rgb(51, 51, 51)" data-darkmode-bgimage-15882384789136="1" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(51, 51, 51)" data-darkmode-original-color-15882396318564="rgb(51, 51, 51)" data-darkmode-bgimage-15882396318564="1" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(51, 51, 51)" data-darkmode-original-color-15900529136199="rgb(51, 51, 51)" data-darkmode-bgimage-15900529136199="1" style="font-size: 14px;color: rgb(51, 51, 51);text-align: right;"><span style="font-family: 楷体, 楷体_GB2312, SimKai;font-size: 16px;">点的“在看”，否则就看不到我了555</span></section><p><br /></p></section></section></section></section></section></section>本篇文章来源于: 菜鸟学Python
本文为原创文章，版权归知行编程网所有，欢迎分享本文，转载请保留出处！
内容反馈