Another Google question - drop glassballs from a building 1 博客分类： algorithms GoogleUPF#Go
程序员文章站
2024-03-07 12:25:51
...
Here is the question:
原题: 有一个100层高的大厦,你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎,用你手中的这两个玻璃围棋子,找出一个最优的策略,来得知那个临界层面。
I copied and pasted the above since I can't type Chinese most of the time. A google yield a few articles that I copied too:
为了得到两个棋子的最优策略，我们先简化问题，看看一个棋子的情况。如果手中只有一个棋子，为了得知临界层面，你只有一种选择：从2楼开始，一层一层地试，直到棋子被打碎，此时你站的楼层就是所求的临界层面。在最差的情况下，我们需要投掷99-2+1=98次，你可能奇怪为什么不是100-2+1=99次，那是因为题目已经告诉我们“从这个大厦的某一层扔下围棋子就会碎”，所以在99层扔下来还没碎的话就不用去100层了——从那里扔它一定会碎。
从一个棋子的策略我们可以看出，一个棋子就足以解答这个问题了。现在又多了一个棋子，该如何利用它呢？很自然地，我们希望能通过这个棋子缩小这种一层一层查找的范围。为了缩小范围，我们将整个大厦的层数分成x段，在这x段中查找那个临界段，然后在临界段中再一层一层地找临界层。比如可以将大楼分成4段，我们分别在25层、50层、75层投掷棋子，以确定临界段；如果临界段在25层到50层，我们再从26层开始一层一层查找临界层。
分析到这里，问题就转化成了如何确定分段数x使棋子投掷的次数最少的问题。在最差的情况下，要确定临界段，我们需要投掷100/x-1次；确定了临界段之后要确定临界层，我们需要再投掷x-1次。因此，问题就成了求函数f(x)=(100/x-1)+(x-1)的最小值问题。先对f(x)求导，f’(x)=1-100/x2，令f’(x)=0求出驻点x=10(x=-10舍去)。由于f(x)存在最小值且只有一个驻点，所以当x=10时f(x)取得最小值，最小值为18。这样就解答了这个问题。
上文贴出之后，我又在CSDN和ChinaUnix的论坛看了一些网友的解法，发现上述方法并非最优。将大楼分段以缩小查找范围的想法是没错的，问题在于是否应该均匀分段。
题目要求我们总的投掷次数要最少。在分段之后，总的投掷次数就等于确定临近段的次数加上确定临界层的次数。如果我们均匀分段，则确定临界层的最坏投掷数是固定的（9次），随着我们确定临近段的投掷次数增加，总的投掷次数也在增加。这样一来，随着临界段的不同，投掷次数也不同。
这也就是为什么上述方法不是最优的原因：投掷次数分布不均。按最坏情况估计，这种方法就多做了几次。为了使最坏情况的投掷数最小，我们希望无论临界段在哪里，总的投掷数都不变，也就是说将投掷数均匀分布。
接下来的解决方案就很容易想出了：既然第一步（确定临界段）的投掷数增加不可避免，我们就让第二步（确定临界层）的投掷数随着第一步的次数增加而减少。第一步的投掷数是一次一次增加的，那就让第二步的投掷数一次一次减少。假设第一次投掷的层数是f，转化成数学模型，就是要求f+(f-1)+...+2+1>=99，即f(f+1)/2>=99，解出结果等于14。
这种方法要推广到n（n>2）个棋子的情况比较困难。我初步的想法是，先用均匀分段求出一个解，然后修正这个解使投掷次数均匀分布。如果你对此有兴趣，不妨思考一下具体的解法。
The key here is to obtain even distribution on how many times in the worst case we have to try regardless where the breaking floor is.
Let's look at the way how we get there, we start with the sequence
(1) 1, 2, 3, 4, 5, 6, 7, 8, 9, ... , 100
Then we take the sum on all numbers before,
(2) 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, ...
The last number 105 > 100, and it's the 14th element in the array (2). Now if we start from the 14th element, which is 14, from the first series (1), if the glass ball breaks, then we need to try at most 13 times below 14th floor to find the breaking floor(start from 1 to 13).
If it's not broken at 14th, then we move up 13 floors(13 is the number before 14) to 27th and check there. If it breaks at 27th, then we know the breaking floor is between 14 and 27(exclude both ends). Since there are only 12 floors in between, totally it takes us 12 + 2 (1 for 14, 1 for 27) trials.
Eventually we will cover all 100 floors(in fact we can cover 105) because 100 < 105 = sum of 1 to 14. And for the first 14 floors, the next 13 floors, the next 12 floors, we all get 14 trials in the worst case.
The floors that we should go if previous trials won't break the glass ball are:
(A) 14, 14+13=27, 14+13+12=39, 14+13+12+11=50, ...
So the process is:
1. take the summations on series (1) to form a new series (2)
2. find the index 14 so that the element with this index, namely 105, is larger than 100.
3. use this index on the series (1) again to sum up backward, namely, series (A).
Once we understand this logic, actually it's easy to extend this method to n glass balls, namely, we just keep taking summations, use (2) as the base and take the summation, we now get
(3) 1, 4, 10, 20, 35, 56, 84, 120, ...
(4) 1, 5, 15, 35, 70, 105, ...
(5) 1, 6, 21, 66, 136, ....
(6) 1, 7, 28, 94, 230, ...
(7) 1, 8, 36, 130,
(8) 1, 9, 45, 175, ...
.............
In every time, we take a evenly distributed series and sum it up to form a new series, then start backward and sum up the new series.
For example, if there are 3 balls, then we use (1), (2), and (3). From (3), 120(The first element > 100) has index 8(from 1, without loss of generality(WLOG)), Then from the 8th element in (2), which 36, we start backward sum-up using (2):
(B) 36, 64, 85, 100, ...
We stop the process once it reaches 100(i.e., >=100, this is because we want to cover 1-100). This series is where we should go, i.e., first try 36, if it's not broken, try 64. If it breaks at floor 36, then it becomes now the case where we have 2 balls and 36 floors. From (2), 36 is the 8th element, this means that we need to start from the 8th element in (1) and sum up backward, ....
If it breaks at 64 and not at 36, then it becomes now the case where we have 2 balls and 64-36=28 balls, if we exclude both ends 64 and 36(since we just tested), we end up 26 balls. Now use the upper bound 28 in 2, we can find the index for (1) and repeat the above.
It's a tedious process, so a program would do the trick for us. The code is largely easy to understand, but there are several cases that twists the logic a little bit:
(i). say floor 5 is broken and there is only one ball, so we have to try from floor 1 to 4, and they are just fine. So logically we know floor 5 is the answer. But the code would print out
something like (5, broken), (4, ok), ...(1, ok).
(ii) say the top floor 5 is the one we are looking for, with only one ball. We have to start from floor 1 on to floor 4. There is no reason to try 5 since it's the top one and every floor below it is ok, so the code has to insert the logic conclusion somewhere.
Noting that though series (1) is evenly distributed(with space 1), it's not the only choice, others are odd number and even numbers(with space 2). However, it's simple to show that when we optimize along space 0, 1, 2, ..., space=1 is the optimal solution(space 0, i.e., the above chinese solution with 10 divided, gives 18; and space 2, i.e., even/odd numbers, give 19).
原题: 有一个100层高的大厦,你手中有两个相同的玻璃围棋子。从这个大厦的某一层扔下围棋子就会碎,用你手中的这两个玻璃围棋子,找出一个最优的策略,来得知那个临界层面。
I copied and pasted the above since I can't type Chinese most of the time. A google yield a few articles that I copied too:
为了得到两个棋子的最优策略，我们先简化问题，看看一个棋子的情况。如果手中只有一个棋子，为了得知临界层面，你只有一种选择：从2楼开始，一层一层地试，直到棋子被打碎，此时你站的楼层就是所求的临界层面。在最差的情况下，我们需要投掷99-2+1=98次，你可能奇怪为什么不是100-2+1=99次，那是因为题目已经告诉我们“从这个大厦的某一层扔下围棋子就会碎”，所以在99层扔下来还没碎的话就不用去100层了——从那里扔它一定会碎。
从一个棋子的策略我们可以看出，一个棋子就足以解答这个问题了。现在又多了一个棋子，该如何利用它呢？很自然地，我们希望能通过这个棋子缩小这种一层一层查找的范围。为了缩小范围，我们将整个大厦的层数分成x段，在这x段中查找那个临界段，然后在临界段中再一层一层地找临界层。比如可以将大楼分成4段，我们分别在25层、50层、75层投掷棋子，以确定临界段；如果临界段在25层到50层，我们再从26层开始一层一层查找临界层。
分析到这里，问题就转化成了如何确定分段数x使棋子投掷的次数最少的问题。在最差的情况下，要确定临界段，我们需要投掷100/x-1次；确定了临界段之后要确定临界层，我们需要再投掷x-1次。因此，问题就成了求函数f(x)=(100/x-1)+(x-1)的最小值问题。先对f(x)求导，f’(x)=1-100/x2，令f’(x)=0求出驻点x=10(x=-10舍去)。由于f(x)存在最小值且只有一个驻点，所以当x=10时f(x)取得最小值，最小值为18。这样就解答了这个问题。
上文贴出之后，我又在CSDN和ChinaUnix的论坛看了一些网友的解法，发现上述方法并非最优。将大楼分段以缩小查找范围的想法是没错的，问题在于是否应该均匀分段。
题目要求我们总的投掷次数要最少。在分段之后，总的投掷次数就等于确定临近段的次数加上确定临界层的次数。如果我们均匀分段，则确定临界层的最坏投掷数是固定的（9次），随着我们确定临近段的投掷次数增加，总的投掷次数也在增加。这样一来，随着临界段的不同，投掷次数也不同。
这也就是为什么上述方法不是最优的原因：投掷次数分布不均。按最坏情况估计，这种方法就多做了几次。为了使最坏情况的投掷数最小，我们希望无论临界段在哪里，总的投掷数都不变，也就是说将投掷数均匀分布。
接下来的解决方案就很容易想出了：既然第一步（确定临界段）的投掷数增加不可避免，我们就让第二步（确定临界层）的投掷数随着第一步的次数增加而减少。第一步的投掷数是一次一次增加的，那就让第二步的投掷数一次一次减少。假设第一次投掷的层数是f，转化成数学模型，就是要求f+(f-1)+...+2+1>=99，即f(f+1)/2>=99，解出结果等于14。
这种方法要推广到n（n>2）个棋子的情况比较困难。我初步的想法是，先用均匀分段求出一个解，然后修正这个解使投掷次数均匀分布。如果你对此有兴趣，不妨思考一下具体的解法。
The key here is to obtain even distribution on how many times in the worst case we have to try regardless where the breaking floor is.
Let's look at the way how we get there, we start with the sequence
(1) 1, 2, 3, 4, 5, 6, 7, 8, 9, ... , 100
Then we take the sum on all numbers before,
(2) 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, ...
The last number 105 > 100, and it's the 14th element in the array (2). Now if we start from the 14th element, which is 14, from the first series (1), if the glass ball breaks, then we need to try at most 13 times below 14th floor to find the breaking floor(start from 1 to 13).
If it's not broken at 14th, then we move up 13 floors(13 is the number before 14) to 27th and check there. If it breaks at 27th, then we know the breaking floor is between 14 and 27(exclude both ends). Since there are only 12 floors in between, totally it takes us 12 + 2 (1 for 14, 1 for 27) trials.
Eventually we will cover all 100 floors(in fact we can cover 105) because 100 < 105 = sum of 1 to 14. And for the first 14 floors, the next 13 floors, the next 12 floors, we all get 14 trials in the worst case.
The floors that we should go if previous trials won't break the glass ball are:
(A) 14, 14+13=27, 14+13+12=39, 14+13+12+11=50, ...
So the process is:
1. take the summations on series (1) to form a new series (2)
2. find the index 14 so that the element with this index, namely 105, is larger than 100.
3. use this index on the series (1) again to sum up backward, namely, series (A).
Once we understand this logic, actually it's easy to extend this method to n glass balls, namely, we just keep taking summations, use (2) as the base and take the summation, we now get
(3) 1, 4, 10, 20, 35, 56, 84, 120, ...
(4) 1, 5, 15, 35, 70, 105, ...
(5) 1, 6, 21, 66, 136, ....
(6) 1, 7, 28, 94, 230, ...
(7) 1, 8, 36, 130,
(8) 1, 9, 45, 175, ...
.............
In every time, we take a evenly distributed series and sum it up to form a new series, then start backward and sum up the new series.
For example, if there are 3 balls, then we use (1), (2), and (3). From (3), 120(The first element > 100) has index 8(from 1, without loss of generality(WLOG)), Then from the 8th element in (2), which 36, we start backward sum-up using (2):
(B) 36, 64, 85, 100, ...
We stop the process once it reaches 100(i.e., >=100, this is because we want to cover 1-100). This series is where we should go, i.e., first try 36, if it's not broken, try 64. If it breaks at floor 36, then it becomes now the case where we have 2 balls and 36 floors. From (2), 36 is the 8th element, this means that we need to start from the 8th element in (1) and sum up backward, ....
If it breaks at 64 and not at 36, then it becomes now the case where we have 2 balls and 64-36=28 balls, if we exclude both ends 64 and 36(since we just tested), we end up 26 balls. Now use the upper bound 28 in 2, we can find the index for (1) and repeat the above.
It's a tedious process, so a program would do the trick for us. The code is largely easy to understand, but there are several cases that twists the logic a little bit:
(i). say floor 5 is broken and there is only one ball, so we have to try from floor 1 to 4, and they are just fine. So logically we know floor 5 is the answer. But the code would print out
something like (5, broken), (4, ok), ...(1, ok).
(ii) say the top floor 5 is the one we are looking for, with only one ball. We have to start from floor 1 on to floor 4. There is no reason to try 5 since it's the top one and every floor below it is ok, so the code has to insert the logic conclusion somewhere.
Noting that though series (1) is evenly distributed(with space 1), it's not the only choice, others are odd number and even numbers(with space 2). However, it's simple to show that when we optimize along space 0, 1, 2, ..., space=1 is the optimal solution(space 0, i.e., the above chinese solution with 10 divided, gives 18; and space 2, i.e., even/odd numbers, give 19).