我在算法工程师面试中遇到的智力题主要是指涉及到一些数学计算、证明的题目，基本是中小学奥数题。喜欢问这类问题的主要有互联网创业公司或外企，招收数值策划的游戏公司，当然，更多的是金融、投资相关的企业。从题目类型上分，有排列组合题、概率题等。
题目介绍
题目一：给定天平，问要称重1-N N种不同质量，最少需要多少种砝码？
1）砝码只允许放在天平的一端；
2）砝码可以放在天平的两端。
解答：
- 只允许放在一边的情况，开始自己以为是斐波那契数列，不过显然数列生成方式里存在冗余（1+2=3）。1、2 肯定是最基本的数字，新添加的砝码质量应该是原砝码集合所能称量的最大质量加一，如此生成的数列就是2的幂次，1，2，4，……想到正整数二进制表达的唯一性，应该是不存在冗余的。可表示性是有了，对于1-N N种不同的质量，最少需要
⌈log2(N+1)⌉ 种不同的砝码，那是不是最少的呢？这种做法没有冗余，且表示范围是砝码的排列组合（每一个砝码可用可不用），应该就是最少了的，不过这不是严格证明。 - 允许放在两边的情况，1、3是最基本的，因为 2 可以用 3-1 表达，新添加砝码的质量应该满足的条件是原砝码集合所能称量的最大质量加上这个最大质量的下一个质量。这种构造方法同样没有冗余，且表示范围是砝码的排列组合（每一砝码可加、可减、可不用，再排除掉和非正数的情况），所以应该也是最少的。按照这个思路生成的数列就是3的幂次，1，3，9，27……可以用数学归纳法证明如下。
Read full article from 面试经验分享之智力题 - Blog of 太极儒
No comments:
Post a Comment