上星期天去霸王笔群硕软件,别人开考接近十几分钟也放我们进去了,经典的称球问题再次在试卷上出现,对于算法的推广到n的情况,我没有搞定,这需要深刻的数学思考。看书好像碰到过类似的问题,但都放过了,借着这互联网之功把这道题也记载下来,这些问题很有意思哦,呵呵。
先讲
对于每个球都已知可能为轻或可能为重的情况,再往更复杂推广:
引用
先引入一个记号:对于任意实数a,我们用{a}表示大于等于a的最小整数,比如说{2.5}=3,{4}=4;我们用[a]表示小于等于a的最大整数,比如说[2.5]=2,[4]=4。
我们首先考虑这样一种布局的集合。假设m,n为两个非负实数,不同时为0。在编号从1到m+n的m+n个球中,我们知道1到m号球要么是标准球,要么比标准球重,而m+1到m+n号球要么是标准球,要么比标准球轻;我们还知道其中有一个是坏球(但不知轻重)。换句话说,我们知道真实的情况是以下m+n种布局之一:
1. 1号是坏球,且较重;
2. 2号是坏球,且较重;
……
m. m号是坏球,且较重;
m+1. m+1号是坏球,且较轻;
m+2. m+2号是坏球,且较轻;
……
m+n. m+n号是坏球,且较轻。
有一种特殊的情况是m=0或n=0,也就是说坏球的是轻还是重已经知,常常被用来单独作为智力题。
结论1:
1)在以上条件成立的情况下,要保证在m+n个球中找出坏球并知道其轻重,至少需要称{log3(m+n)}次。
2)如果m和n不同时为1,那么称{log3(m+n)}次就足够了。如果m=n=1,并且另有一标准球,那么称{log3(m+n)}={log3(1+1)}=1次也足够了。
现在来证明1)。
引用
在上面我们看到,可能的布局是m+n种(1重,2重,……,m重,m+1轻,m+2轻,……,m+n轻)。假设我们已经有一个策略能保证在这m+n个球中找出坏球并知道其轻重,那么每一个布局都要通向策略树上的不同叶子,这棵策略树至少需要有m+n片叶子。但是一棵高度为H的三分树最多只能有3^H片叶子。于是这棵策略树必须满足条件
3^H ≥ m+n
也就是
H ≥ log3(m+n)
考虑到H是整数,我们就证明了
H ≥ {log3(m+n)}
现在我们要具体找到一棵高度为{log3(m+n)}的策略树,使得m+n种布局通向它的不同叶子。我们对k=m+n使用数学归纳法。
引用
对于k=1。不用说了
对于k=2。m=1,n=1的情况已经讨论过了。考虑m=2,n=0。这时我们知道坏球比较重。
们知道坏球比较重。m=0,n=2的情况完全类似。
假设对于m+n<k的情况我们都可以用{log3(k)}次称出坏球。考虑m+n=k的情况。我们把1到m号球称为第一组球,m+1到n号球称为第二组球。
设H={log3(m+n)}={log3(k)}。那么我们有
3^H-1 < k ≤ 3^H
3^H-2 < k/3 ≤ 3^H-1
3^H-2 < {k/3} ≤ 3^H-1
于是
{log3{k/3}}=H-1。
现在我们把这k个球分为三堆,第一堆和第二堆分别有{k/3}个球,并且这两堆中属于第一组的球的数目一样(于是属于第二组的球的数目也一样),第三堆中有k-2{k/3}个球(也就是其余的球)。举一个例子,如果m=7,n=3,那么这三堆可以分成这样:(当然不是唯一的
分法)
第一堆:1,2,3,7 (属于第一组的3个,第二组的1个)
第二堆:4,5,6,8 (属于第一组的3个,第二组的1个)
第三堆:9,10
这样的分堆总是可能的吗?
引用
如果m或n是偶数,那就很简单。比如说假设m是偶数,有两种可能性。如果m/2≥{k/3},那么就从第一组球中各取{k/3}个球作为第一和第二堆(这时在第一第二堆中只有第一组的球);如果m/2<{k/3},那么就把第一组球分为相同的m/2个球的两堆,再分别用{k/3}-m/2个第二组球去把它们补充成{k/3}个球的两堆(这时在第三堆中就只有第二组的球了)。很显然这样的分堆符合上面的要求。
如果m和n都是奇数,事情就有点复杂。首先如果(m-1)/2≥{k/3}的话,那么按上面的方法也很容易把球按要求分为三堆。但是如果(m-1)/2<{k/3},我们就必须先从第一组中各拿出(m-1)/2个球放入第一和第二堆,再从第二组中各拿出{k/3}-(m-1)/2个球将它们补充到各
有{k/3}个球为止。这就需要从第二组中总共拿得出2({k/3}-(m-1)/2)个球来。所以必须有
2({k/3}-(m-1)/2) ≤ n
即
2{k/3} ≤ (m-1)+n
2{k/3} ≤ k-1
这个不等式在k=3或k>4时总是成立的,但是对k=4就不成立。所以我们要对k=4且m,n都是奇数的情况作特殊处理。我们只需考虑m=3,n=1这种情况。把1号球和2号球放在天平两端,如果不平衡,那么较重的那个是坏球;如果平衡,那么把1号球和3号球放在天平两端,平衡则4号球为坏球且较轻,不平衡则3号球为坏球且较重。m=1,n=3的情况完全类似。
于是现在我们就可以毫无障碍地假设,我们已经将m+n=k个球分为这样的三堆:第一堆和第二堆分别有{k/3}个球,并且这两堆中属于第一组的球的数目一样(于是属于第二组的球的数目也一样),第三堆中有k-2{k/3}个球(也就是其余的球)。
我们把第一堆球和第二堆球分别放在天平的左右两端。如果平衡,那就说明坏球在第三堆里,这样我们就把问题归结为一个k-2{k/3}个球的问题;如果右边比较重,那么我们得到结论:要么是坏球比较轻,并且它在第一堆中的第二组球,也就是可能较轻的那些球中,要么是坏球比较重,并且它在第二堆中的第一组球,也就是可能较重的那些球中,下面它就归结为一个{k/3}个球的问题了;如果是左边比较重,那么我们也完全类似地将问题归结为一个{k/3}个球的问题。
考虑到k-2{k/3}≤{k/3},另外此次称量后我们至少可以得到一个标准球(如果不平衡,第三堆里的球均为标准球,否则第一第二堆里的球均为标准球)。根据归纳假设,上面得到“左”、“平”、“右”三种情况归结后的问题都可以用{log3{k/3}}=H-1次的称法来解决。所以加上这第一次称量,k个球只需{log3(k)}次称量就可以找出坏球。
引用
结论2:现有N个小球,其中有一个坏球不知比标准球轻还是重。
我们令H={log3(2N)}。
1)要保证在N个球中找出坏球并知道其轻重,至少需要称H次。
假设N≠2,我们有
2)如果N<(3H-1)/2,那么称H次就足够了;
3)如果N=(3H-1)/2,那么称H次足以保证找到坏球,但不足以保
证知道坏球比标准球轻还是重;
4)如果N=(3H-1)/2,而且还另有一个标准球,那么称H次足以保
证找到坏球和知道,知道坏球比标准球轻还是重。
假设N=2,我们有
5)如果还另有一个标准球,称H={log3(2*2)}=2次足以保证找到
坏球和知道坏球比标准球轻还是重。
分享到:
相关推荐
面试智力题(附答案) 本资源摘要信息涵盖了 25 个面试智力题,每个问题都具有很高的挑战性和逻辑性。这些问题涵盖了逻辑推理、数学计算、语言理解和空间想象等多方面的能力。 以下是对每个问题的详细解释和答案:...
### 微软面试智力题解析 #### 1. 速度问题 题目描述:有两个人,一个每小时走4公里,另一个每小时走5公里。如果他们同时出发,走了30公里后,速度较快的人会比速度较慢的人快多少? **解析:** - 每小时走4公里的...
### 常见的面试智力题与答案解析 在求职过程中,面试官常常会通过一些智力题来评估应聘者的逻辑思维能力、问题解决能力和创新能力。本文将对一系列常见面试智力题进行详细解析,并给出答案,帮助大家更好地准备面试...
### IT面试中的智力题知识点解析 #### 一、逻辑推理题型分析 ##### 1. 蛋糕切分问题 **题目描述**: 将一盒蛋糕切成8份,分给8个人,但是要求蛋糕盒里还必须留有一份。 **解决思路**: 这个问题的关键在于理解...
12个球找异常球,可先称4个,确定异常球在哪一组,然后用类似方法找到。 12. 画10条直线:可以将点分为三组,每组3个点,每组内部两点连线,组间两点连线,共9条,再加一条穿过三个点的线。 13. 时针分针秒针重合...
这些题目是程序员面试中常见的智力题,旨在考察应聘者的逻辑思维、问题解决能力和创新思维。以下是对这些题目涉及的知识点的详细分析: 1. **烧绳计时**:这是一个经典的逻辑题,要求在没有标准时间工具的情况下...
**称球问题**,这是一个典型的寻找差异问题。在有限的次数内,需要找出一个重量不同的球。假设有12个球,可以将它们分为三组,每组四个球。首先称量两组,如果平衡,那么坏球在剩下的那组中;如果天平不平衡,可以...
笔试面试智力题整理(附答案) 本资源摘要信息将对笔试面试智力题进行总结和分析,涵盖逻辑推理、问题解决、空间想象等多个方面的智力题。 一、逻辑推理 1. 金条分配问题:如何在每天结束时给工人一段金条,只...
【智力题解析】 1. 金条问题:你需要在第一天给工人一段金条,然后将剩下的六段在第二天切分成两段,分别在第二天和第三天支付。这样,你只需两次切割就能完成支付。 2. 蛋糕分配:将蛋糕切成9份,先分给8个人各一...
【微软智力题】是微软公司在面试或招聘过程中常常用来测试应聘者思维能力、逻辑推理以及问题解决技巧的一类题目。这些题目通常具有一定的趣味性和挑战性,旨在考察候选人的创新能力、快速思考能力和应对压力的能力。...
这些题目属于趣味智力题,常出现在面试或笔试中,用于测试应聘者的逻辑思维、问题解决能力和创新性思考。这类题目不拘泥于常规答案,往往需要打破常规思维,从不同角度寻找解决方案。 第一题,金条分割问题,要求将...
这些称球问题考察了应聘者的分析能力和精确性,同时也体现了面试者对于细节的专注。 此外,还有一些空间想象和逻辑推理的问题。比如,在9个点上画10条直线,每个点与其他8个点连线,而且不重复。这个问题考验了应聘...
5.12个球一个天平,现知道只有一个和其它的重量不同,问怎样称才能用三次就找到那个球。13个呢?(注意此题并未说明那个球的重量是轻是重,所以需要仔细考虑) 6.在9个点上画10条直线,要求每条直线上至少有三个点?...
这些题目是各大公司在面试过程中用来考察应聘者逻辑思维、问题解决能力以及创新能力的智力题。让我们一一解析这些难题: 1. 金条问题:你需要将金条分成1/7、2/7和4/7三段,这样在第一天、第二天和第六天分别给工人...
这些题目都是经典的智力题,旨在测试面试者的逻辑思维、推理能力以及问题解决技巧。下面是对这些题目的详细解析: 1. 烧绳计时问题:这是一个关于时间测量的题目,利用了不均匀燃烧绳子的特点。两根绳子,第一根...
这些题目涵盖了多个领域的智力挑战,包括逻辑推理、数学问题、策略规划、物理概念以及日常常识。...这些智力题考察了观察力、逻辑思维、计算能力和策略规划,对于面试和笔试来说,能够展现应聘者的综合素质。
这些题目是经典的智力挑战,旨在测试问题解决能力、逻辑思维和创新能力。让我们逐一解析: 1、工人工作7天,金条分成7段。为确保每天支付一块,可以在第一天使用两次切割,将金条切成1、2、4三段。这样第一天给1段...