原文链接:http://www.cnblogs.com/baiyanhuang/archive/2010/06/23/1763981.html
作者:@baiyanhuang
有 1 到 10000 共 10000 个数,如果我从中随机拿走一个数,你如何知道我拿走了哪个?
相信很多人看过这道题,并知道答案,这几天和同事聊天时听到了这个问题,因为有过自己的思考过程,不妨记录下来。 说是逻辑题,其实也算是一道算法题,同事先讲了下他被面试中的思维过程:
-
先把 10000 个数相乘,然后再将拿走一个数之后的 9999 个数相乘,两者相除即可。
这个算法是正确的,但是会有两个潜在的问题:
- 如此多的数相乘,其范围必然会超出系统提供的数据类型支持,当然你可以实现自己的大数表示的算法,但那样性能必然有影响。
- 假设扩展一下题目,提供的数组中有 0 的话,乘法就不可用了。
-
针对前面提出的问题,同事想到了使用加法,先求出 10000 个数的和,再减去 9999 个数的和。
这样数据不会溢出,而且加法的效率比乘法也要高很多,即使数据中包含 0,也没有任何问题。
然后就过关了,自己回去之后思考了一下,觉得还可以扩展,假设所有的数加起来之后仍然会溢出,那该如何处理,比如从 1 到 (2^64-1),于是想到了位操作,与、或,异或中,要数异或最为神奇,代入一看,果然合适: 先将所有的数异或起来,然后将拿走一个数之后的数异或起来,两者结果再异或,便是拿走的那个数。
我用 a,b,c,d 4 个数来做演示,因为异或符合结合律和交换律(你可以用 0,1 试一下),于是:
a^b^c^d = (a^b^c)^d
d = (a^b^c^d)^(a^b^c)
此处用异或的好处在于
- 不会溢出
- 异或的速度要快于加法
扩展一下题目,如果提供的不是整数,而是浮点数,会有问题吗? 当然没有,因为是在位级别上操作,无论是整数还是浮点数,在这个算法看来,都是一堆位,处理起来没有什么差别。
再扩展一下题目,如果提供的数本身就超出了内置类型的表示范围,如在 1 到 2^128,该如何处理? 这个问题是在写这篇文章的过程中想到的,暂时没有好的办法。
相关推荐
这个问题鼓励我们寻找最优解,可能需要跳出常规思维,比如一次拿走所有香蕉的一半,然后再拿走剩下一半的一半,以此类推。 通过这些逻辑推理题,我们可以训练自己的思维敏捷度,提高分析问题和解决问题的能力,这...
两人轮流取1、2或4枚硬币,最后拿走最后一枚硬币的人输。这类问题通常可以通过逆向思维来解决,即考虑游戏结束时的情况,然后逐步回溯。在这个例子中,因为每次可以取1、2或4枚硬币,所以无论对方如何取,你总能在下...
最优策略是:如果你是先手,第一次拿走1颗石头,之后每次对方拿几颗你就拿几颗,这样你就可以在最后一步取走最后一颗石头,从而获胜。 以上是对给定文件中的部分逻辑思维题目的解析。这些题目涵盖了数学、逻辑推理...
而减法如5-4,可以理解为从5个物品中拿走4个,剩下1个。 2. "小鸭做客"是一道结合实际情境的题目,通过连接小鸭的花朵和裙子,让学生在娱乐中学习加法。这种方式有助于激发孩子的学习兴趣,同时也锻炼了他们将实际...
12. 棋子分装问题:第十题是一道逻辑推理题,通过分析拿走棋子后的状态,确定原来的棋子数量和盒子数量。 13. 图形计数:最后一题要求计算图形的数量,分别是对三角形和长方形的计数。 以上就是这些试题所涉及的...
【1】这是一道经典的逻辑思考题,涉及到的是容斥原理和推理能力。要使用5升和6升的水壶得到3升水,首先需要理解每个水壶的特性。你可以通过以下步骤解决这个问题: 1. 将5升水壶装满水。 2. 使用5升水壶倒入6升水壶...
9. **灰雀的谎言**:这是一道逻辑推理题。根据题目设定的规则,可以构建一个关于年龄的逻辑关系网,通过排除法找出每只灰雀的年龄。 10. **半只小猫**:这是一个关于分数和逻辑思维的问题。通过祖父母的话,可以...
4. **数量的减法**:第6题中,妈妈有7个苹果,弟弟拿走了3个,剩下4个,这是一道简单的减法应用题。 5. **图形操作**:第7题让学生圈出水果,第12题画出指定数量的图形,这些题目旨在训练学生的观察能力和计数技巧...
10. **简单减法问题**:第十题看似简单,实际上是一个开放性问题,因为鸟听到枪声会飞走,所以树上的鸟数会减少。 11. **代数问题**:第十一题通过一系列等式求解变量值,涉及代数的加减运算和解方程。 12. **图形...
这份“一年级月考试题.doc”是一份针对小学一年级学生的数学测试卷,主要考察学生的数感、基础计算能力和简单的逻辑推理。下面将详细解析试卷中的各个部分及其涉及的知识点。 一、我会填 这部分题目旨在训练学生对...
3. 减法:减法练习包括从一个较大的数中减去较小的数,例如17-9、18-9,这种类型的题目有助于孩子理解减法的概念,即从总数中拿走一部分。 4. 反复练习:每一道题都是一个独立的口算练习,但题目多次出现类似的形式...
4. 这是一道看图列式的题目,可能包含一幅图,图中可能会有10个物品,然后被拿走了4个,让孩子理解并列出减法算式来表示这一过程。根据题目给出的答案,可以推测图中应该是表示了10减去4等于6的情景。 通过这样的...
总的来说,以内数的加减法学习教案旨在通过多种方式教授和练习基本的加减法,包括直接计算、应用题编制、逻辑推理等,确保学生能牢固掌握这些基础知识,并能灵活运用到实际问题中。这样的教学方法既注重知识的传授,...
6. **数字钥匙**:这是一道逻辑题,没有具体答案,但可以根据题目条件推断出可能的数字。 7. **找缺失防潮剂的糖果**:类似找不同重量物品的问题,但这里没有砝码,至少需要4次才能确定哪一袋缺少防潮剂。 8. **...
三人共支付$30,后退$5,每人退$1,小弟拿$2,似乎总数变成了$27,但实际上,每位客人支付了$9,共计$27,加上小弟拿走的$2,正好是最初的$30,不存在所谓的“消失的$1”。 - **盲人的袜子**:两位盲人需要找回各自...
4. 前后变化的计算:如笔的数量减少,需要找出拿走的数量。 5. 多步运算:一次走了10只,再次走了5只,总计走了多少只。 以上是试卷中的核心知识点,它们涵盖了数学的基本技能和概念,是小学一年级学生必须掌握的...
第二题考察了整数除法的应用,涉及到将糖果平均分给7或8个小朋友,需要找出能被这些数整除的余数,即至少需要拿走多少颗糖。 3. 常用度量单位: 第三题考察了对生活常见度量单位的理解,如身高、体重和时间的表达,...
7. **年龄问题**:这是一道数学逻辑题。根据信息,三个孩子的年龄之积为36,年龄之和等于门牌号。门牌号可能是11、10或14,因为36的因数组合只有(1,1,36),(1,2,18),(1,3,12),(1,4,9),(2,3,6)。结合最后的信息...
4. **用数学**:这部分是将数学知识应用于实际问题,比如拿走9本书后剩下多少,通过图像判断花朵或图形的数量等。这有助于培养学生的逻辑思维和解决实际问题的能力。 通过这份试卷,我们可以看到一年级下学期的数学...
10. 盘子里的梨经过拿走后,应用减法来计算剩余的梨数:17 - 9 - 6。 11. 这题考察加法和减法,草地上的羊经历了跑走和到来,羊的总数变化为10 - 3 + 7。 12. 小刚的玩具问题包含加法和减法,小刚开始有3个玩具,...