有一栋100层高的大楼，给你两个完全相同的玻璃球。假设从某一层开始，丢下玻璃球会摔碎。那么怎么利用手中的两个球，如何知道这个临界的层是第几层？

解法思路

在思考这道题之前，思考一下为什么是两个球，多给一个球的目的是什么呢？

我们先想想只有一个球是什么情况：假如只有一个球，要想测出小球破碎的临界值，我们只能采取从第一层逐渐向上的测试方案，并且只能这样，因为球在任意一层都会碎，只剩下一个球之后就没法再测量了，假设你从第10层开始扔，球碎了，那么这个方案就是不可行的，因为并没有测出球破碎的临界值。所以只有一个球只能从第一层向上扔，一直扔到第x层球没碎，x+1层球碎了，找出球破碎的临界值x，但这样做球有可能在第100层破碎，所以显而易见的只有一个球对应着最差的解法，最多要尝试100次。

那么有两个球又会怎么样呢？

有两个球你就多了一次试错机会，只要第二球没碎，第一个球你随便扔，尽可能帮你排除楼层。我们假设先扔第一个球，在50层球没碎，那么从1到50层你都不需要再次尝试了，只需要在第51_{100层里面找，假如在第50层球碎了，那么就说明两个问题：首先是临界值在1}50里面，其次你没有试错机会了，只能从第1层逐渐向上尝试。但是这样期望从原来的100次降低到了50次，如果刚才50时候球没碎 ，那么你可以在第75层继续尝试，这样对应着二分的解法，以此类推，当然二分并不是最优解法。

明白上述的思路之后，要找到这个临界层，其实采用的就是叫做“两球分层法”的策略。这种方法的主要思路是，先用较大的间隔来尝试，当找到一个可能的临界区间后，再用较小的间隔进行精确查找。

1. 从第k层（如k=10）开始，每隔k层楼扔下第一个玻璃球。这样，你会尝试第10层、第20层、第30层，依此类推。
2. 当第一个玻璃球从第i*k层楼摔碎时（如i=3时，摔碎在第30层），你就知道临界层在(i-1)*k层和i*k层之间（在这个例子中，就是在20-30层之间）。
3. 接下来，从(i-1)*k层的下一层（如第21层）开始，逐层使用第二个玻璃球进行尝试，直到找到那个临界层。

为了最大限度地减少尝试次数，我们需要选择合适的k值。在这个问题中选择是k=14（向下取整的平方根的2倍），因为这样可以将尝试次数限制在最多14次。具体步骤如下：

1. 从第14层开始，每隔14层楼扔下第一个玻璃球。也就是先尝试14层、28层、42层，依此类推。
2. 当第一个玻璃球从第i*14层楼摔碎时，你就知道临界层在(i-1)*14层和i*14层之间。
3. 接下来，从(i-1)*14层的下一层开始，逐层使用第二个玻璃球进行尝试，直到找到那个临界层。

这种方法可以在最多14次尝试内找到临界层。

为什么是14

解释一下为什么k=14是最优解，我们需要分析最坏情况下的尝试次数：找到一个k值，使得在100层楼的情况下，最坏情况下的尝试次数最小。假设我们选择的k值为x，那么第一个球最多需要尝试100/x次（向上取整）。而当第一个球摔碎时，第二个球最多需要尝试x-1次。因此，最坏情况下的总尝试次数为：

T(x) = 100/x + x - 1

要找到最小化T(x)的x值，我们可以观察T(x)在x递增时的变化：

1. 当x较小时，100/x的值较大，而x - 1的值较小。因此，T(x)相对较大。
2. 当x较大时，100/x的值较小，而x - 1的值较大。因此，T(x)仍然相对较大。

要找到T(x) 最小值，可以对T(x)进行微分，并找到其临界点。在这个问题中，当x = 14时，最坏情况下的尝试次数达到最小，约为14次。在这个x值下：

T(14) = 100/14 + 14 - 1 ≈ 14

所以选择k = 14可以使得在最坏情况下，尝试次数最小。

如果是k个小球和n层楼

可以使用动态规划来解决这个问题，假设有k个小球和n层楼，需要找到一个策略来最小化确定小球在哪一层扔下会碎的实验次数。我们可以定义一个函数dp[k][n]，表示有k个小球和n层楼时，最坏情况下的最小实验次数。

基本情况如下：

• 当k = 1时，我们需要从第1层开始逐层尝试，最坏情况下需要尝试n次。所以，dp[1][n] = n。
• 当n = 0或n = 1时，我们不需要进行实验或只需要尝试一次。所以，dp[k][0] = 0和dp[k][1] = 1。

状态转移方程为：

• 对于每一层楼i，我们可以选择在该层扔一个小球。如果小球碎了，我们需要在i-1层楼下继续尝试，此时剩余k-1个小球；如果小球没碎，我们需要在剩余的n-i层楼上继续尝试，仍有k个小球。所以，在这种情况下，最坏情况下的实验次数为1 + max(dp[k-1][i-1], dp[k][n-i])。
• 为了找到最优的策略，我们需要从所有可能的i中选择一个使实验次数最小的i，即dp[k][n] = 1 + min(max(dp[k-1][i-1], dp[k][n-i]))，其中i从1到n。

使用自底向上的动态规划方法计算dp[k][n]，以找到最优策略，时间复杂度为O(k * n^2)。

有20瓶药丸，其中19瓶装有1克/粒的药丸，余下一瓶装有1.1克/粒的药丸。给你一台称重精准的天平，怎么找出比较重的那瓶药丸？天平只能用一次。

问题的关键在“天平只能用一次”，这反倒是一种提示：利用有限的资源（只能使用一次天平）从20瓶药丸中找到异常的那一瓶。要解决这个问题，我们需要寻找一种方法来将每瓶药丸与一个唯一的结果相关联，解决思路源于数学中的等差数列概念。

当我们想到从每瓶药丸中取出与瓶子编号相等的药丸数量时，我们实际上在创建一个等差数列，其差值为1。这意味着从第1瓶药丸中取出1粒，从第2瓶药丸中取出2粒，以此类推，直到从第20瓶药丸中取出20粒。这样一来，当我们将所有取出的药丸放在天平上进行一次称重时，每瓶药丸都有一个唯一的重量贡献。

如果所有的药丸都是1克/粒，总重量应该是1+2+3+...+20=210克。然而，我们知道有一瓶药丸是1.1克/粒，这意味着实际称重结果将会比预期的210克稍重。而这个多出来的重量，恰好就是异常药丸的瓶子编号。巧妙地利用等差数列求和公式，我们仅用一次称重就能找出那瓶异常的药丸。

过程如下：

• 从每瓶药丸中取出与其瓶子编号相等的药丸数量。例如，从第1瓶药丸中取出1粒，从第2瓶药丸中取出2粒，以此类推，从第20瓶药丸中取出20粒。

• 将所有取出的药丸放在天平上进行一次称重。如果所有的药丸都是1克/粒，那么总重量应该是1+2+3+...+20=210克。但由于有一瓶药丸是1.1克/粒，总重量会比210克重一些。

• 计算天平上药丸总重量与210克之间的差值。这个差值将是一个整数倍的0.1克，这个整数就是装有1.1克/粒药丸的瓶子的编号。

例如，如果称重结果是210.3克，那么差值为0.3克，这意味着第3瓶药丸中的药丸重1.1克/粒。

有个岛上住着一群人，有一天来了个游客，定了一条奇怪的规矩：所有蓝眼睛的人都必须尽快离开这个岛。每晚8点会有一个航班离岛。每个人都看得见别人眼睛的颜色，但不知道自己的（别人也不可以告知）。此外，他们不知道岛上到底有多少人是蓝眼睛的，只知道至少有一个人的眼睛是蓝色的。所有蓝眼睛的人要花几天才能离开这个岛？

很经典的一道逻辑题，这个问题的解决思路来自于对信息和逻辑推理的巧妙运用。当游客告诉岛民至少有一个人的眼睛是蓝色时，虽然没有提供具体的数量，但提供了一条关键信息：岛民们将通过观察其他人的行为，逐渐揭示这个谜题的答案。

假设岛上有n个蓝眼睛的人，我们来分析每种情况下蓝眼睛的人需要多少天才能离开岛：

1. 当n=1时，岛上只有一个蓝眼睛的人。他看不到其他人的蓝眼睛，但知道至少有一个人是蓝眼睛的，所以他意识到自己就是那个蓝眼睛的人。所以，当天晚上8点，他就会离开岛。
2. 当n=2时，岛上有两个蓝眼睛的人，两个蓝眼睛的人看到对方，并不确定n是1还是2，但是由上一种情况他们知道，如果n = 1，那个蓝眼睛的人第一晚就会离岛。第二天，他们发现另一个蓝眼睛的人没有离开，这意味着至少有两个蓝眼睛的人，所以他们能确定自己也是蓝眼睛的。于是，第二天晚上8点，两个蓝眼睛的人都会离开岛。
3. 当n=3时，假设岛上有三个蓝眼睛的人。前两天晚上，他们都没有离开。到第三天，他们都看到其他两个蓝眼睛的人没有离开，这意味着岛上至少有三个蓝眼睛的人。由于他们看到了其他两个蓝眼睛的人，他们能确定自己也是蓝眼睛的。因此，第三天晚上8点，三个蓝眼睛的人都会离开岛。

以此类推，如果岛上有n个蓝眼睛的人，他们需要n天才能全部离开岛。因为每个人都在观察其他人的行为，当他们发现其他蓝眼睛的人都没有离开时，他们就能推断出岛上蓝眼睛的人数，并据此确定自己的眼睛颜色。

利用不均匀硬币产生等概率？

连续抛两次硬币，正反面的出现有四种情况，概率依次为：

1. 两次均为正面：p * p
2. 第一次正面，第二次反面：p * (1 - p)
3. 第一次反面，第二次正面：(1 - p) * p
4. 两次均为反面：(1 - p) * (1 - p)

问题的解法就是连续抛两次硬币，如果两次得到的相同则重新抛两次；否则根据第一次（或第二次）的正面反面情况，就可以得到两个概率相等的事件。

5只猫5分钟捉5只老鼠，请问100分钟捉100只老鼠需要多少只猫？

5只，分析：1只猫5分钟捉1只老鼠，1只猫100分钟捉20只老鼠，5只猫100分钟捉100只老鼠。

3升的杯子一个，5升的杯子一个，杯子不规则形状，问怎么得到4升的水？

• 5升杯子装满，全部倒给空的3升杯子，此时5升杯子有2升，3升杯子要3升
• 倒掉3升杯子的全部水，再把5升杯子的2升水倒给3升杯子，此时5升杯子有0升，3升杯子有2升
• 5升杯子装满水，向3升辈子倒水，倒满，此时此时5升杯子有4升，3升杯子有3升

用5L和6L的桶，没有刻度，怎么量出3L的水？

• 6L桶装满水，向空的5升桶倒水至水满为止，此时6L桶有1升水，5L桶有5升水
• 倒掉5L桶的全部水，再把6L桶的1升水倒给5L桶，此时6L桶有0升水，5L桶有1升水
• 6L桶装满水，向5升桶倒水至水满为止，此时6L桶有2升水，5L桶有5升水
• 倒掉5L桶的全部水，再把6L桶的2升水倒给5L桶，此时6L桶有0升水，5L桶有2升水
• 6L桶装满水，向5升桶倒水至水满为止，此时6L桶有3升水，5L桶有5升水

晚上有四个人过桥，一次只能过两个人，但是只有一只手电筒，四个人过桥时间分别是1，2，5，8，求最短过桥时间？

假设这四人依次是甲乙丙丁：首先甲和乙过桥，甲带手电筒回来；然后丙和丁过桥，由乙带手电筒回来；最后甲再和乙一起过桥，所以最少用时间是2+1+8+2+2=15（分钟）

有十张扑克牌，每次可以只出一张，也可以只出两张，要出完有多少种出法？

• 还有一张牌就出完10张，可能的情况有两种，从9到10和从8到10，已知了从0到9的出法有N种，如果再知道从0到8的出法有P种，那么从0到10级的出法就是N+P，那么可得出：
• F(9)=N；F(8)=P；F(10)=N+P；F(10)=F(9)+F(8);
• 又有：F(1)=1；F(2)=2最后推出：F(10)=89

两根香，一根烧完1小时，如何测量15分钟？

开始时一根香两头点着，一根香只点一头，两头点着的香烧完说明过去了半小时，这时将只点了一头的香另一头也点着，从这时开始到烧完就是15分钟。