codetop几道逻辑题

---

一块金子，只能切两刀，请问如何给一个人发一周的工资

1,2,4三份，就是单独能取出1,2,3,4,5,6,7就好。

32个球，重量都不一样，只有一个天平

找最大的那个

需要多少次？

第一重，二分：16+8+4+2+1= 31次

第二大的那个

第二重，重点是比较过的也可能是第二重。

先两两比较，假设最后是AB比较，A最重，将之前和A比较过的都拿出来。

例如在第一次里，也就是两两比较，第二大只有两种可能，一种是和A比较的，所以到不了下一轮，另一种是没有和A比较的，那一定是较大的，到了下一轮，同理，要么是和A比较过的，要么进入了下一轮，直至最后一轮B。

除了B还有4个，也就是一共5个，再两两比较，3次（他说3次，但是感觉得4次），得出最重的。

类似的，还有一堆球里面只有一个质量不同

例如知道轻了，8个里面找最轻，最多两次比较就可以了，3,3,2。如果3个球和另外三个球相等，轻的肯定在2里面，否则就在轻的3里面，都可以用剩下的一次机会找出。

求用户在线峰值和持续时间

• 直接考虑到每秒
• 排序之后按段分。记录不同当前不同持续时间的段。例如第一段A是1-5，计数为1，如果第二段,7-10没有交集，证明A的计数就结束了，可以记录到一个文件里。如果第二段B是3-7，那就拆分成1-3是1，因为是已经排序好的，可以记录到文件里，这一段用不到了，3-5是2,5-7是1。这个放入队列，一会还要用到。如果B是3-4，也就是拆分成了三段，道理应该是一样的。然后在第三段C再继续判断，拆段，舍弃前面的，继续。

64匹马，8个跑道，问最少比赛多少场，可以选出跑得最快的4匹马

先每八匹马比一场，一共8场。找出各自的第一名，再比一场，看谁的第一名牛逼。例如A最厉害，B次之。

那么A下面的三匹马a1,a2,a3可能都是比A差一点点，但是比B牛逼，同理，b1,b2也可能比C要牛逼。也就是3+2+1+3（BCD)9匹马要再分胜负，两场，也就是8+1+2=11场。

两个玻璃球，需要扔多少次才能知道100层楼哪一层楼是玻璃球会被摔碎的最低楼层

例如扔50层，碎了，那还需要遍历1-50。

例如扔25层，碎了，要遍历1-25，没碎，再扔个50，可能碎也可能不碎。最差情况在100层是极限，要扔3次+25次。最好也要25次。

例如扔1层，那最差要100次。所以要在扔的楼层间隔和第一个球测试几次碎掉（间隔越大，次数越少）之间取一个均衡。

所以前后楼层的区间大小应该是不一样的，后面的区间要小些。

假设区间大小X，X+(X-1)+(X-2)+...+1 = 100,X=14。

一根绳子切两刀构成三角形的概率

某人进行10次打靶，每次打靶可能的得分为0到10分，10次打靶共得 90分的可能性有多少种

递归、插球（感觉是C21,9)

圆环上有10个点，编号为0~9。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法。

动态规划问题

两个盒子抽黑白球

黑球白球各一百个，有两个盒子，里面可以装任意个数的球。现在需要从中抽一个球出来。问怎么装球可以使得抽中黑球的概率最大，最大概率是多少？

（一个盒子装一个黑球，另一个装剩下所有的球。1/2 + 1/2 * (99/199)。）

圆桌放硬币

两个人坐在一张普通的圆桌旁，一个人往桌子上放一枚硬币，随后另一个人也往桌上放一枚同样的硬币，如此交替地继续下去，彼此约定，每一枚硬币都必须平放在桌上，而且不准重叠。谁在桌上放下最后一枚硬币，谁就是这场游戏的胜利者。假设你是先放硬币的人，怎么放能保证一定能赢？ 方案：第一个硬币放在圆心，随后的每次都把硬币放在同对方刚放的硬币的位置关于桌子中心成中心对称处，于是只要对方能放下一枚硬币，先放者在其对称的位置上一定也能放下一枚硬币。

两堆硬币 一堆6个 一堆10个 ，每次从一堆里拿出n个(n>=1)。AB两个人依次开始拿，A先开始，问如何是否能够确保A或者B获胜，拿完后如果硬币都为空则输

A先手拿10个中的4个，那么两堆都为6个，接下来B每轮拿多少，A每轮拿多少。 A获胜