首页 > 试题广场 >

腾讯大厦有39层,你手里有两颗一抹一眼的玻璃珠。当你拿着玻璃

[问答题]
腾讯大厦有39层,你手里有两颗一抹一眼的玻璃珠。当你拿着玻璃珠在某一层往下扔的时候,一定会有两个结果,玻璃珠碎了或者没碎。大厦有个临界楼层。低于它的楼层,往下扔玻璃珠,玻璃珠不会碎,等于或高于它的楼层,扔下玻璃珠,玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式,使得在该方式下,最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效的方式。
这道题有点没素质了吧,39楼往下扔玻璃球,砸到人脑袋的话直接能砸出一个坑
发表于 2017-08-24 11:13:23 回复(13)
用户随机选一层i,扔下去,有两个结果:

碎掉,或者没有碎掉。

1.如果碎掉,去试验前i-1层,那么最多需要i-1次再加上碎掉的那一次,最多就是i次。

2.如果没有碎掉,等于说从第i+1层往后,也还是有两个弹珠,这就回到了递归的思路上了。
在这种没有碎掉的情况下,假如总共有N层,那么N层的最多次数等于N-i层的最多次数。所以

针对用户随机选择的这一层i, 以上1和2两种情况, 求其最大值就是最差情况下的次数。

用户随机选择的这个i,也可以变化的,取值 1,2,3...N. 那么我们就会得到不同的值。
针对1,2,3...N. 会有N个,所有这些值中取最小,就是最优解。  用F(N)表示这个最优解,那么F(0)由于没有楼层,所以一定等于0,也就是说不需要实验。
F(0) = 0;
F(N)= min(max(1, F(N-1) + 1), max(2, F(N-2)+ 1)... max(N, F(0)+ 1))

F(0) = 0;
F(1) = 1;
F (2) = min(max(1, F(1)+ 1), max(2, F(0) + 1)) = 2;

可以使用递归算法求得其值,最终的结果是9次。

package interview;

import java.util.ArrayList;

public class ThrowPinballFrom30Layer {
	/**
	 * 腾讯大厦有39层,你手里有两颗一抹一眼的玻璃珠。当你拿着玻璃珠在某一层往下扔的时候,一定会有两个结果,玻璃珠碎了或者没碎。大厦有个临界楼层。低于它的楼层,往下扔玻璃珠,玻璃珠不会碎,
	 * 等于或高于它的楼层,扔下玻璃珠,玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式,使得在该方式下,最坏的情况扔的次数比其他任何方式最坏的次数都少。也就是设计一种最有效的方式来确定临界楼层
	 * 
	 * @param 39
	 *            layer
	 * @return the optimal step for the first ball.
	 */
	public static int getOptimalStep(int N, int[] results, int[] selection) {

		if (N == 0) {
			results[N] = 0;
			return 0;
		}
		if (results[N - 1] >= 0) {
			return results[N - 1];
		}

		int selectedIndex = 0;
		int min = -1;
		for (int i = 0; i < N; i++) {
			int max = Math.max(i + 1, getOptimalStep(N - i - 1, results, selection) + 1);
			if (min < 0) {
				min = max;
				selectedIndex = i;
			} else {
				if (min > max) {
					selectedIndex = i;
					min = max;
				}
			}
		}
		selection[N - 1] = selectedIndex;
		results[N - 1] = min;
		return min;
	}

	public static void main(String[] args) {

		int N = 39;
		int[] results = new int[N];
		for (int i = 0; i < results.length; ++i) {
			results[i] = -1;
		}
		int[] selection = new int[N];

		System.out.println("optimal steps:" + getOptimalStep(N, results, selection));

		ArrayList<Integer> steps = new ArrayList<>();
		int current = N - 1;
		int selectPosition = 0;
		while (true) {
			if (current < 0) {
				break;
			}
			selectPosition = selectPosition + selection[current];
			steps.add(selectPosition);

			selectPosition = selectPosition + 1;

			current = N - 1 - selectPosition;
		}

		StringBuilder sb = new StringBuilder();
		
		sb.append("selections:");
		sb.append("[");
		for (int i = 0; i < steps.size(); ++i) {
			if (i != 0) {
				sb.append(",");
			}
			sb.append(steps.get(i) + 1);
		}
		sb.append("]");

		System.out.println(sb.toString());
	}
}


打印結果為:
optimal steps:9
selections:[3,11,18,24,29,33,36,38,39]

最多9步。

编辑于 2017-08-20 00:09:07 回复(9)

这是道动态规划
设函数F(x)为X层大厦时,最坏情况的最小值
比39层大厦,假设我再5楼仍两种结果
1.碎了,那么临界楼就在5楼内,接下来从1楼一层层往上试验。
2.没碎,此时问题相当于在34层大厦中找临界楼即F(34),最后再+1(这是dp的特征:最优子结构)
从5楼仍珠子的最坏情况:max(5,F(34)+1)
那么问题是怎么找最优,其实5楼是我自己随便挑的,我可以把每一楼都试过去
max(1,F(38)+1),max(2,F(37)+1)...max(39,F(0)+1)
恩,我列出了所有方案的最坏情况,接着从他们中找到"最坏的情况扔的次数比其他任何方式最坏的次数都少"
min(max(1,F(38)+1),max(2,F(37)+1)...max(39,F(0)+1))
整理公式(状态转移方程)
F(N)=Min(Max(1,1+F(N-1)),Max(2,1+F(N-2)),……,Max(N-1,1+F(1)))

发表于 2017-09-13 13:20:35 回复(1)
1
2     10
3     11       18
4     12       19     25
5     13       20     26     31
6     14       21     27     32       36
7     15       22     28     33       37
8     16       23    29      34       38
9     17       24     30      35       39
先从最后一行开始测试,当碎了时,再从该列最上方测试,所以最多需要9次;

发表于 2017-09-01 22:02:11 回复(0)
方案一(较复杂):建立二维数组a[39][2](39代表楼层,2代表剩两个珠子)令a[n][1]=n,a[1][2]=1,a[2][2]=2,递推公式a[n][2]=1+min(max(a[i-1][1],a[n-i][2])(0<=i<=39))

方案二:直接找出n*(n+1)/2的值大于39的最小n即可。分析:这应该是一个概率期望的问题:第一次选取x1层,需要满足x1-1=f(39-x1),意思就是选取一层扔球,球碎或不碎需要的测试次数都一样即不改变测试次数的期望(尽量满足,因为两种情况不一定完全一样)。对于39-x1层楼(0~39-x1层),选取x2层测试,满足x2-1=f(39-x1-x2),还需要满足f(39-x1-x2)+1=f(39-x1),因此 x2=x1-1,选取间隔依次为x1,x1-1,x1-2,..1,加起来最后一层能到x1*(x1+1)/2,意思是测试x1次最多能测x1*(x1+1)/2这么多层楼,而8*(8+1)/2=36<39<9*(9+1)/2=45,所以需要测试9次,一种方案:9,17,24,30,35,后面层数随便选不影响结果,因为第一次选9就已经定了最少测9次。(因为39<45,所以会出现多种组合,但是只要第i次测试完能使剩下的楼层小于或等于(9-i)*(9-i+1)/2即可,多种组合可以依次写出)
(如有错误,请各位网友指正)

编辑于 2017-08-28 15:03:15 回复(0)

第一个球测试楼层顺序 8-15-21-26-30-33-35-37-39,碎后第二个球自上一个测试层上一层依次测试

<thead> </thead>
\ 详情
测试楼层 0 1 2 3 4 5 6 7 8
测试次数 2 2 3 4 5 6 7 8 8
测试楼层 09 10 11 12 13 14 15
测试次数 03 04 05 06 07 08 08
测试楼层 16 17 18 19 20 21
测试次数 04 05 06 07 08 08
测试楼层 22 23 24 25 26
测试次数 05 06 07 08 08
测试楼层 27 28 29 30
测试次数 06 07 08 08
测试楼层 31 32 33 34
测试次数 07 08 09 09
测试楼层 35 36 37
测试次数 08 09 09
测试楼层 38 39
测试次数 09 09

由于是球的损坏性,切考虑的性能为“最坏的情况扔的次数”,所以需要尽可能分成每段最差情况需要测试次数相同,如上分段后,最差情况,33,34,36,37,38,39层,需要测试9次,其余每段的的最差情况为8次。

编辑于 2017-08-19 19:06:25 回复(2)
测试层数顺序:7 13 19 24 28 32 35 37 39,在第一颗珠子没碎时,一直按着这个顺序测试,珠子一旦在某一层碎了,就用另一颗珠子在上次没导致珠子摔碎的楼层的上面一层开始逐层测试(如:第一颗珠子在第35层摔碎,那么第二颗珠子就从33层开始逐层测试,就能得出临界楼层),就可以得出临界楼层。这种方法的最坏情况是,第一颗珠子在第39层才摔碎,但是也只需要测试10次就能得出临界楼层,不知道有没有更好的办法。(顺序由来:  a(n)表示第n个测试楼层,  a(0)=0,  a(n)= (39 - a(n-1))开方上取整   + a(n-1)。得 a(1)至a(9)的值分别为 7,13,19,24,28,32,35,37,39
发表于 2017-08-19 15:24:25 回复(5)
class Solution{

    static int solution(int num){
        int[]dp=new int[num+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=num;i++){
            for(int j=1;j<=i;j++){
                dp[i]=Math.min(Math.max(j,dp[i-j]+1),dp[i]);
            }
        }
        return dp[num];
    }
    public static void main(String[]args){
        System.out.print(solution(39));
    }
}
发表于 2019-03-09 16:58:30 回复(0)
                           中间楼层mid=(1+39)/2=20 
                                    /                                \
                    [1,19] mid=10                            [21,39] mid=30
                           /       \                                           /            \
                  [1,9]          [11,19]                      [21,29]               [31,39]
                 mid=5         mid=15                     mid=25                mid=35
                  /   \              /        \                       /       \                    /           \
              [1,4]  [6,9]   [11,14]   [16,19]      [21,24]    [26,29]     [31,34]       [36,39]
             mid=3 mid=7 mid=13  mid=17     mid=22    mid=27     mid=32       mid=37
             /   \     /   \            /   \        /    \           /    \          /    \            /   \            /   \
      [1,2] [4] [6] [8,9]  [11,12][14][16][18,19][21] [23,24][26][28,29][31][33,34][36][38,39]

注意:遇到[8,9]这样相邻的楼层,再扔一次确定临界楼层
                     
第一次在20层扔下,A.球碎了==》临界楼层低于等于20层
                               B.球没碎==》临界楼层高于20层
依次类推,最多五次找到临界楼层,所以最坏情况为5次.
发表于 2018-01-17 10:54:44 回复(1)
类二分法思想
直接找20层进行试验,碎了说明临界层在20层以下,没碎说明在20~39
然后根据这个思路继续进行试验。
发表于 2017-08-29 15:36:46 回复(1)
数学解法,假设最坏至少扔n次,那么分析如下:
第一次在x层扔玻璃珠碎了,此时需要用第二颗玻璃珠从1到x-1遍历,最坏x次;
第一次没碎,而二次在x+y层碎了,那么同理需要第二颗玻璃珠从x+1到x+y-1遍历,最坏1+y次;
以此类推,要求x<=n,1+y<=n..........,要求n最小,那么让所有不等式取等。
即第一次可向上n层,第二次向上扔n-1层(因为第一次已消耗了一个次数,能遍历的层数-1),以此类推直到只能向上扔一层为止。
由此可得,扔n次最多能检验n*(n+1)/2层楼,解不等式n*(n+1)/2>=39取整即可得n>=9.
同理可推广到m个玻璃珠。
发表于 2022-06-08 23:26:26 回复(0)
设刚好 K 层的时候,扔下玻璃球会碎。则使用以下的扔球措施,可保证最多扔 K 次就能找到刚好会碎的层:
第一次在第K层扔;
第二次在第2K-1层仍;
则K应该满足下面的关系:
K+K-1+K-2.....+1>=39;
可以求出K>=9;
所以最少扔9次。扔球方案,就如上面说的那样。
发表于 2021-03-04 22:56:58 回复(0)
以后路过腾讯大厦前要注意防护


发表于 2020-04-26 02:14:40 回复(0)
社会的道德呢,这种人还能进腾讯?39层往下扔玻璃球
发表于 2019-09-17 01:03:17 回复(0)
#include <iostream>
using namespace std;

inline int max(int a, int b) { return a > b ? a : b; }

int miniFloorR(int maxFloor)
{
	if (maxFloor == 0) return 0;
	if (maxFloor == 1) return 1;

	int ret = maxFloor;
	for (int i = 0; i < maxFloor; i++)
	{
		int tmp = max(i + 1, miniFloorR(maxFloor - i - 1) + 1);
		if (ret > tmp) ret = tmp;
	}

	return ret;
}

int miniFloorI(int maxFloor)
{
	int *arra = new int[maxFloor + 1];

	for (int i = 0; i <= maxFloor; i++)
	{
		arra[i] = i;
		for (int j = 1; j <= i; j++)
		{
			int tmp = max(j, arra[i - j] + 1);
			if (tmp < arra[i])
				arra[i] = tmp;
		}
	}
	
	int ret = arra[maxFloor];

	delete arra;

	return ret;
}

int main()
{
	cout << "Result: " << miniFloorI(39) << endl;

	return 0;
}

发表于 2019-09-07 09:43:41 回复(0)

package prac_tencent;


public class dp_boli {

    static int[][] dp;

    static int INF = 0x3f3f3f;


    public static void main(String[] args) {

        int N = 39;

        int M = 2;

        dp = new int[N + 1][M + 1];

        for (int i = 0; i <= N; i++) {

            for (int j = 0; j <= M; j++) {

                dp[i][j] = INF;

            }

        }

        int dfs = dfs(N, M);

        System.out.println(dfs);

    }


    public static int dfs(int n, int m) {

        if (dp[n][m] != INF) {

            return dp[n][m];

        }

        if (n == 0) {

            return dp[n][m] = 0;

        }

        if (m == 1) {

            return dp[n][m] = n;

        }

        for (int i = 1; i <= n; i++) {

            dp[n][m] = Math.min(dp[n][m], 1 + Math.max(dfs(i-1, m-1), dfs(n-i, m)));

        }


        return dp[n][m];


    }


}

发表于 2019-04-05 14:21:17 回复(0)
这道题什么意思啊,看不懂4
发表于 2019-03-09 17:53:52 回复(0)
没看懂这个题什么意思。。。不知道算法到底是要干什么
发表于 2018-06-06 22:16:06 回复(0)
用户随机选一层i,扔玻璃球,有两个结果:碎了,或者没有碎。
1.如果碎了,去试验前i-1层,那么最多需要i-1次再加上碎掉的那一次,最多就是i次。
2.如果没有碎掉,等于说从第i+1层往后,也还是有两个弹珠,这就回到了递归的思路上
了。
在这种没有碎掉的情况下,假如总共有N层,那么N层的最多次数等于N-i层的最多次数。所以
针对用户随机选择的这一层i, 以上1和2两种情况, 求其最大值就是最差情况下的次数。
用户随机选择的这个i,也可以变化的,取值 1,2,3...N. 那么我们就会得到不同的值。
针对1,2,3...N会有N个,所有这些值中取最小,就是最优解。用F(N)表示这个最优解,那么F(0)由于没有楼层,所以一定等于0,也就是说不需要实验。
F(0) = 0;
F(1) = 1;
F(N)= min(max(1, F(N-1) + 1), max(2, F(N-2)+ 1)... max(N, F(0)+ 1))

/**
 * 腾讯大厦有39层,你手里有两颗一模一样的玻璃珠。当你拿着玻璃珠在某一层往下扔的时候,一定会有两个结果,
 * 玻璃珠碎了或者没碎。大厦有个临界楼层。低于它的楼层,往下扔玻璃珠,玻璃珠不会碎,等于或高于它的楼层,
 * 扔下玻璃珠,玻璃珠一定会碎。玻璃珠碎了就不能再扔。现在让你设计一种方式,使得在该方式下,最坏的情况扔的次数比其他任何方式最坏的次数都少。
 */
public class ThrowPinballFromNLayer {
    public static void main(String[] args) {
        ThrowPinballFromNLayer test = new ThrowPinballFromNLayer();
        System.out.println(test.fun(39));
    }
    
    public int fun(int n){
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        int[] arr = new int[n+1];
        arr[0] = 0;
        arr[1] = 1;
        
        for(int i=2;i<=n;i++){
            int min = Integer.MAX_VALUE;
            for(int j=1;j<=i;j++){
                if(min > Math.max(j, arr[i-j]+1))
                    min = Math.max(j, arr[i-j]+1);
            }
            arr[i] = min;
        }
        return arr[n];
    }
}


编辑于 2018-04-04 22:51:25 回复(0)