Google And The Puzzle of Dropping Eggs 구글과 퍼즐이 떨어지는 계란
Google is also known for its interesting interview questions. 구글은 또한 흥미로운 인터뷰 질문 유명합니다. Enjoy this one and my solution. 하나와 내 솔루션을 즐길 수있습니다. Suppose you have two eggs. 가정 계란이 두 개있습니다. These are special eggs—they can take much more punishment than you average chicken egg. 이들은 처벌을 특별 계란 - 그들은 당신보다 훨씬 더 걸릴 수있습니다 평균 닭고기 계란을합니다. The question is exactly just how much punishment can they take? 문제는 정확하게 단지 처벌을 할 수 얼마나 걸릴까요?
Using a 100 storey building and only the two eggs, how would you find out which is the highest floor of the building you can drop the eggs from, before they break? 100 층 건물과만을 사용하여 두 개의 난자가 어떻게 알아 냈 층 건물이 최고의 계란을하실 수있습니다에서 드롭하기 전에, 그들은 휴식 시간?It could be the 1st floor but it could also be the 99th floor—you don’t know but to test, you need to try dropping the eggs from different floors and see what happens. 그것 수있는 1 층하지만이 99번째 수도있습니다 층 - 넌 모르지만 새 버전을 테스트하려면 떨어지는 계란을 시도해야합니다 서로 다른지면, 어떻게되는지합니다.
via SitePoint 를 통해 Sitepoint -
Are you done yet? 아직도 멀었소? My solution is simple. 내 해결책은 간단합니다.
Use binary search with one egg till it breaks. 이진 검색과 하나가 될때까지 계란 나누기를 사용합니다. Use linear search with the second egg till it breaks. 선형 검색을 사용할 때까 지의 두 번째 계란 나누기합니다. And you have the solution. 그리고 당신은이 솔루션합니다. If that's not clear enough allow me to explain. 만약 그게 제게 기회를 충분히 설명할 명확하지 않다.
First drop one egg from 50th (midway). 한 계란에서 첫 번째 드롭 50 (미드웨이).
- If it breaks (no more binary search) then drop the second egg from first floor. 만약 브레이크 (더 이상 이진 검색)을 드롭 두 번째 계란을 1 층에있습니다. Move up one floor at a time till it breaks. 한 번에 한 층 위로 이동할 때까 지의 휴식합니다.
- If it doesn't break then drop it from 75th floor. 휴식 시간을 떨어뜨에서하지 않으면 75 층합니다.
- If it breaks then drop the second egg from 76th floor. 만약 브레이크를 드롭 76번째 바닥에서 두 번째 계란을합니다. Move up one floor at a time till it breaks. 한 번에 한 층 위로 이동할 때까 지의 휴식합니다.
- If it doesn't break then drop it from the 87th floor… 휴식 시간을 떨어뜨하지 않으면 제 87 회 바닥에서…
I hope you get the picture by now. 나는 지금까지 그림이 그려지 바랍니다. I would love to see anyone coming with a better optimized solution. 나는 사랑을 보이는 사람이 저와 함께 더 나은 최적의 솔루션을합니다.
Update: The optimization is to minimize the number of drops. 업데이트 :의 최적화는 상품의 개수를 최소화합니다.
Filed under 밑에 Google 구글 , Headline News 헤드 라인 뉴스 , How To 하는 방법을 , Web 웹 | | 
| | 
RSS 2.0 rss 2.0 | | 
Trackback 트랙백 this Article | 이 문서 | 
Email this Article 전자 우편이 문서
You may also like to read 같은를 읽을 수있습니다 |
June 10th, 2006 at 12:24 pm 2006년 6월 10일에서 오후 12시 24분
wouldn’t you drop it from the 51st instead of the 76th floor on the second round? 그렇지 않나요에서 드롭 쉰한번째 대신 바닥에서 제 76 회 제 2 차? if the first broke on 75, then it’s between 51 and 74 inclusive that you need to check now 첫 번째 파산을 경우에는 75, 그러면 51과 74 사이의 현재를 확인하는 데 필요한이 포함된
June 10th, 2006 at 5:41 pm 2006년 6월 10일에서 오후 5시 41분
I spent a long time typing a detailed explanation of a solution but I lost it in a browser mishap. 오랜 시간을 보냈어요의 해결 방법에 대한 자세한 설명을 입력 그러나 사고의 브라우저에서 잃어 버렸어요. But, here is my solution, without the explanation: drop egg #1 at every 10th (0, 10, 30, 50…) floor, and drop egg #2 at every 20th floor (20, 40, 60…), until one breaks. 하지만, 여기가 내 솔루션을하지 않고에 대한 설명 : 드롭 계란 # 1마다 10 일 (0, 10, 30, 50…) 바닥, 앤 드롭 계란 # 2마다 20 층 (20, 40, 60…),하기 전까지 휴식합니다. Then, drop one egg on every odd numbered floor and the other on every even numbered floor until one breaks. 그리고, 드롭 한 계란을하고 다른 모든 홀수 번호가 매겨진 층 바닥까지 모든 번호가 매겨진 나누기도합니다. Then, you will have the answer to the question of “what is the lowest floor on which the egg will break?” 그 다음 질문에 대한 답변을하셔야합니다 "낮은 층에있는 계란은 무엇입니까 휴식 시간은?"
If you analyze the two solutions with respect to the number of drops, you will see that this alternative has the same best-case performance, and notably better worst-case performance, always wins when the answer is within (10,50) when, and often wins (but sometimes loses) when the answer is greather than 50. 2 개의 솔루션을 분석하는 경우와 관련하여 상품의 개수가 나타납니다 - 사건이 대안은 동일한 최고의 성능을, 그리고 특히 더 나은 최악의 - 사건의 성능, 항상 승 때 대답은 '시간 (10,50) 때, 그리고 자주 승 (그러나 때로는 손실)을 greather에 대한 답변은 50.
If you analyze the two solutions with respect to travel time/effort going up/down the building, then I believe that the alternative’s advantage is even better. 2 개의 솔루션을 존중하는 경우로 여행을 분석하는 시간 / 노력을가는 업 / 다운 건물, 그리고 나서 내가 그 대안의 장점은 더욱 믿을합니다. Your solution ignores travel time, but I imagine you’d do it the same way I did (travel up, drop one, travel up again, drop the other, then travel down to get both). 귀하의 솔루션을 무시 소요 시간,하지만 난 그것을하고 싶어이 똑같은 방식으로 상상이 난 (여행을, 총 하나, 여행을 다시는 드롭 다른면 아래를 여행 둘 다).
I don’t know if the alternative solution is optimal; I was just trying to show a better alternative. 잘 모르겠 솔루션은 최적의 대안 경우에는; 전 그저 더 나은 대안을 표시합니다. I too am interested in a better solution. 나 또한 더 나은 솔루션에 관심이있습니다.
June 11th, 2006 at 7:17 am 2006년 6월 11일에서 오전 7시 17분
@a 다윈
That depends on whether your floor numbering starts from 0 (ground floor) or 1 (first floor). 귀하의 바닥 여부에 따라 달라집니다에서 시작하는 번호가 0 (1 층) 또는 1 (1 층).
@Brian @ 브라이언
I am sorry to hear your explanation got lost. 귀하의 설명을 듣는 나는 길을 잃었 죄송합니다. I would love to hear it. 나는 그것을 듣는 남편을 사랑합니다.
> Then, drop one egg on every odd numbered floor and the other on every even numbered floor until one breaks. > 그리고, 드롭 한 계란을하고 다른 모든 홀수 번호가 매겨진 층 바닥까지 모든 번호가 매겨진 나누기도합니다.
At this point one has already broken. 이 시점에서 하나가 이미 깨진합니다. If your second egg breaks too then you do not have any more eggs to find the exact floor. 만약 당신의 두 번째 계란을 나누기도를 더 이상하지 않아도됩니다 층 난자를 정확하게 찾을 수있습니다.
Also why use two eggs at ood and even floors? 또한 2 개의 난자를 사용하는 이유도 우드 플로어? Why not simply use one egg? 왜 계란을 단순히 하나를 사용? We are limited by only two eggs. 우리는 단 두 계란에 의해 제한합니다. So shouldn’t we keep the second egg to pinpoint the exact floor? 그래서 두 번째 계란을 유지를 정확하게 지적해야하지 않을까의 정확한 층?
June 12th, 2006 at 12:37 am 2006년 6월 12일에서 오전 12시 37분
You are right; I copied my wording from the 10/20 part absent-mindedly. 당신이 권리, 난 부분에 복사 부재 - 20분의 10에서 내 마음을 표현합니다. Once the first egg breaks, you should drop the second one from every floor, increasing the floor number by one, just as in your case. 첫 번째 계란을 한 번 나누기, 당신은 두 번째 드롭의 모든 층, 확대 바닥에 번호를 하나, 귀하의 경우처럼 단지.
However, my main point was that it is better to go every 10th floor then to try the “binary search” you described. 하지만, 내 주요 포인트는 매 10 층 갈 것이 좋습니다 그 다음에 시도 "이진 검색"을 설명합니다. Your search is highly optimized for when the answer is a floor over 75 and it performs very poorly for high floors less than 50. 귀하의 검색에 맞게 최적화되어에 대한 답변이 때, 그것을 수행 매우 저조한 층 이상 75 층 이하의 높이 50.
The reason for the “every 10th floor / every 20th floor” logic is to minimize travel time. 그 이유는 "모든 10 층 / 매주 20 층"논리는 여행 시간을 최소화하고자 노력하고있습니다. Let’s say that the answer is “22.” Then, I would drop egg #1 from floor 10, it would not break. 그 대답은 '이라고합시다 "22."그리고 나서, 나는 계란을 # 1에서 밑으로 떨어질 층 10, 그렇지 않을 휴식합니다. Then, I can go up to floor 20 and drop egg #2 from floor 20, and it does not break. 그리고 나서, 나는 바닥까지 갈 수 앤 드롭 계란 # 2에서 20 층에 20, 그리고 그것은 깨지지 않습니다. Then I need to go down and pick up both eggs, and take them both to floor 30. 그럼 난 둘 필요가 내려가서 픽업 계란, 그리고 양쪽에 데리고 층 30. At this point I have traveled 10+10+20+30=70 flights of stairs. 이 시점에서 나는 10 +10 +20 +30 = 70 항공 여행의 계단을합니다.
If travel time is not an issue, then you could just go up to floor 10, drop egg #1, go down to pick it up, carry it up to floor 20, drop it again, go down to pick it up, go up to floor 30 etc. In this case you would just keep egg #2 in your pocket until egg #1 breaks. 소요 시간은 문제가되지 않습니다 경우 다음에 갈 수있습니다 층 단지 10, 드롭 계란 # 1, 가서 수화기를 들면, 운반을 위해 그곳 층 20, 드롭 다시는 후세에 수화기를 들면, 갈 이 바닥 30 등등이 경우는 그냥 계속 계란을 # 2 주머니에 계란을 # 1 나누기까지합니다. This method would require traveling 10+10+20+20+30=90 flights of stairs to get to floor 30. 이 방법이 필요 10 +10 +20 +20 +30 = 90 항공 여행의 30 층 계단을 가봐야합니다. This is the kind of detail that interviewers would probably be interested in at least hearing about-they’d also probably like you to at least ask if the eggs will weaken structurally as you drop them. 이것은 아마 종류의 세부 사항을 면접 원 - they'd에 대한 청문회에 관심이 적어도 당신처럼, 그리고 아마 난자를 우울하게하는 경우에는 요청을 최소한 구조적으로 그들을 드롭합니다.
Note also that I chose “10″ arbitrarily: I was just trying a better solution, not the optimal one. 참고 : 역시 제가 선택한 "10"임의 : 나는 그냥가 더 나은 솔루션이 아니라 최적의 하나.
June 22nd, 2006 at 4:35 am 2006년 6월 22일에서 오전 4시 35분
What about N floors? 무엇에 대해 n 층?
Is 10 a good choice since it’s the sqrt of 100? 그것은 좋은 선택이 10 sqrt 이후의 100?
What about using a binary search on floors i=1, 2, 4, 8, 16, 32, 64, … and then a linear search for the floors inbetween? 이진 검색을 사용하는 방법을 나는 무엇 층 = 1, 2, 4, 8, 16, 32, 64,… 그 다음 1 층에 선형을 검색합니다 inbetween?
A solution for 36 floors is here: 에 대한 해결책을 36 층는 여기에있습니다 :
http://mathforum.org/wagon/past_solns/s921.html
Using the fact that 36 is the 8th triangular number, ie 36 = 1 + 2 + … + 8 를 사용하여 삼각형의 숫자는 사실을 36은 8 일, 즉 36 = 1 + 2 +… + 8
June 22nd, 2006 at 8:04 am 2006년 6월 22일에서 오전 8시 4분
If you know the height of the building then I think the jump search is optimum using sqrt(h) as your jump size, but if the height of the building is unknown then I’m really not sure. 그 건물의 높이를 알고 있으면 그때 생각하게 사용하여 최적의 점프 검색은 sqrt (원정)로 여러분의 점프의 크기, 그러나 만약의 높이를 알 수없는 건물은 다음 난 정말 모르겠합니다. Triangular numbers, fibonnaci, or binary. 삼각형 숫자, fibonnaci, 또는 바이너리합니다. Binary search on floors i=1, 2, 4, 8, 16, 32, 64, … covers a lot of ground quickly with the first egg. 이진 검색을지면 나는 = 1, 2, 4, 8, 16, 32, 64,… 커버는 많은 그라운드 신속하게 첫 번째 계란을합니다.
November 4th, 2006 at 4:02 am 2006년 11월 4일에서 오전 4시 2분
hei…just a simple math problem 현대 전자 수학 문제를 간단하게…
suppose we jump every N floors, and use second egg in the one step increasing pinpoint. 가정 점프 주파수를 우리가지면, 한 걸음 더 확대하고 사용하는 두 번째 계란을 정확하게 지적합니다.
MaxNumbers = 100/N + (N-1) maxnumbers = 100 / n + (n - 1)
To get the Max N we take a derivative: 를 최대 n 우리는 파생 :
-100/N^2 + 1 = 0 => N = 10 -100 / n ^ 2 + 1 = 0 => n = 10
So we take 1st egg every 10 floors, then second egg one by one to pinpoint. 그래서 우리는 1 계란을 매 10 층, 다음 계란을 하나씩 차례로 두 번째를 정확하게 지적합니다.
Worse case: 19 최악의 경우 : 19
Average case: 10. 평균 사례 : 10.
November 30th, 2006 at 1:43 am 2006년 11월 30일에서 오전 1시 43분
Say X is the number we are looking for. 우리가 말하는 엑스는 전화 번호를 찾고있습니다. Then, my choice will start with floor X first. 그 다음에 나의 선택을가 시작됩니다 층 x 우선합니다. This way, if the egg breaks, I start a linear search starting from 1 to X-1, guaranteeing a solution in Y attempts. 이런식으로, 만약 계란 나누기, 전 선형 검색을 시작부터 1 ~ x - 1, 그리고 시도에있는 솔루션을 보장합니다. Otherwise, I go to X + (X-1) floor…. 그렇지 않으면, 나는 갈 x + (x - 1) 바닥…. Continuing in this way, with X attempts, I can cover sum(X + X-1 + X-2… 2 + 1) floors. 지속적으로 이러한 방법으로 x 시도, 할 수 있 커버 (x 755 - 1 755 - 2… 2 + 1) 바닥합니다. Hence, we are looking for Min X such that X(X+1)/2 > 100. 그러므로, 우리는 찾고 분 x 같은 × (x +1) / 2> 100.
I can do it in 14 난 할 수 있어요 14
October 4th, 2007 at 3:57 pm 2007년 10월 4일에서 오후 3시 57분
I ran into this problem recently and am looking for a solution… it seems there are many 나는이 문제는 최근에 우연히 해결책을 찾고 그리고이 많은 것…
I don’t have a formal proof of this, but a gut feeling tells me my solution is good/pretty close to optimal (and it’s nice to have Jason Southgate’s agreement, I think he’s describing the same solution?). 공식적인 증거가없는 나는, 그러나 나의 해결 방법은 좋은 말로 직감 / 아주 가까이 최적의 (그리고 제이슨 남대문의 동의를 만나서, 나 같은 해결 방법을 설명하는 것 같은데? ).
Algorithm (assumes we know the number of floors): 알고리즘 (플로어의 수를 우리가 알고 있다고 가정) :
* Number of floors = N * 층수 = n
* Drop the first egg at floor 1 * sqrt(N), 2 * sqrt(N), … until you either reach N or it breaks. * 드롭에 대한 첫 달걀을 바닥 1 * sqrt (n), 2 * sqrt (n), n하거나… 도달할 때까지 휴식 중 하나. If you drop it from the top floor without it breaking you have your answer. 에서 드롭하는 경우 최상층에 대한 응답이 없으면, 파괴합니다.
* If it breaks when dropped from k * sqrt(N) floor then drop the second egg, starting at the (k - 1) * sqrt(N) floor and going up one floor at a time until it breaks. * 만약이 찢어져 떨어졌다 때 k * sqrt (n) 바닥을 드롭 두 번째 계란, 시작에 (케이 - 1) * sqrt (n) 바닥이나 올라 나누기까지 한 번에 한 층합니다. By definition it must break sometime before k * sqrt(N) 언젠가하기 전에 브레이크를 정의해야합니다 k * sqrt (n)
I think this algorithm is O(N^0.5) - the maximum number of drops it can take is sqrt(N) + (sqrt(N) - 2). 내 생각이 알고리즘은 오 (n ^ 0.5) - 상품의 최대 개수가 소요될 수있습니다 sqrt (n) + (sqrt (n) - 2). This would occur if it broke on the N-1′th floor. 이것은 고장에서 발생하는 n - 1'th 바닥면합니다.
Two interesting extensions of it would be: what if the number of floors doesn’t have an integer square root? 그것은 두 개의 재미있는 확장 : 만약에지면의 개수의 정수가되지 않습니다 제곱근? Eg if N = 378? 예를 들어 만약 n = 378? It seems there are three alternatives for the size of the increment of the first egg drops - the floor, ceiling or round of sqrt(N). 세 가지 대안을위한 것 증분의 크기는 달걀의 첫번째 상품 - 바닥, 천장 또는 차 sqrt (n). I’m not certain of my answer but I think using the round would be optimal? 내 답변이 확실하지 않다하지만 제 생각을 사용하여 최적의 라운드가?
The second extension is what to do in the case of an unknown number of floors, where N is just some integer (1…infinity). 두 번째 확장 기능이 무엇을해야할지 알 수없는 개수의 경우에는 바닥, 여기서 n은 어떤 정수 (1… 무한대). sqrt(infinity) just doesn’t make sense, and it seems to me that if any integer is equiprobable (sp?) then you want to leap up towards infinity as fast as possible, so you get a known upper bound and then just have a linear search. sqrt (무한대) 말이 안되는, 그리고 나에게 그것을 보인다 정수가있는 경우 equiprobable (출발점?) 그렇다면 무한대쪽으로 도약을 최대한 빨리, 잘 알려진 얻을 수 있도록 그리고 그 바로이 상한 선형 검색합니다. But I have no way of expressing this formally or in any convincing way, I’m just pumping intuitions madly! 하지만 난 표현 방법이 없다 설득력이 공식적으로 또는 어떠한 방식, 난 그냥 펌프 직감 미치!
All this fancy reasoning said though I think the triangle number solution linked to above is actually better. 공상 추론이 모든 삼각형 숫자는 비록 내 생각에 그 이상이 실제로 더 나은 솔루션을 연결합니다. I’m just not sure how you would generalise it to situations where N is not a triangular number. 나는 단지 generalise 없다면 그것을 확인하는 방법 상황에서 n은 삼각 번호를합니다.
Binary search would be O(log N) though… hmmm, OK, now I’m confused and lack all certainty, but what the heck, other things to do this morning, I’ll post anyway 이진 검색은 오 (로그 n) 비록… 흠, 그래, 지금은 혼란과 부재의 모든 확실성,하지만 도대체, 다른해야 할 것들이 오늘 아침, 난 어쨌든 게시물
Christo christo
PS: A point I didn’t consider till now: if you’ve checked all but two possible floors and break the egg on the second to last possible floor then you still have your answer… Again, not sure and no time to see if this is important! ps : 지금까지 고려할 점 안 : 만약이 검사를 제외한 모든 계란을 깰 수있는 2 개의지면, 두 번째를 마지막으로… 수있습니다 층 다음에 대한 응답을 다시 당신은 여전히가 아니라도없고 시간이 있는지 확인 이것은 중요합니다!
October 5th, 2007 at 5:13 pm 2007년 10월 5일에서 오후 5시 13분
The original puzzle doesn’t say what they’re trying to optimize, so I assume the optimization variable is left to the solver. 퍼즐의 원래 그들이 무슨 노력을 최적화하는 말을하지 않습니다, 그래서 왼쪽으로 추측의 최적화 변수가 해결합니다.
Personally, I would optimize for minimal egg breaks by starting on floor 1 and going up one floor at a time until it breaks. 개인적으로, 전 휴식을 최적화하기위한 최소한의 계란을 시작하여 1 층에까지 올라 휴식을 한 번에 한 층합니다. In the end you’d be left with your answer and one unbroken egg. 결국 당신은 당신의 대답을 한 끊어지지 왼쪽과 계란을합니다. Any egg that can survive a drop from more than 1 story would be a very valuable egg indeed, and get you a lot of money on ebay! 모든 계란을 한 개 이상에서 한 방울이 생존할 수있습니다 스토리는 매우 귀중한 난자 사실, 그리고 경매 사이트에 많은 돈을를 구해!
October 6th, 2007 at 11:42 am 2007년 10월 6일에서 오전 11시 42분
The optimization is for minimizing the number of drops. 의 최적화는 상품의 수를 최소화합니다.
October 16th, 2007 at 12:42 am 2007년 10월 16일에서 오전 12시 42분
For goodness sake. 이런 세상에합니다. The egg will break when dropped from the first floor because, well, it’s an egg. 휴식 시간은 떨어졌다 때, 계란은 1 층 왜냐하면, 음, 이건 달걀합니다.
I say cook the two eggs for breakfast and move onto the next question! 내가 말하는 요리사하고 이동은 아침에 계란 두 방면의 다음 질문!
November 2nd, 2007 at 11:21 pm 2007년 11월 2일에서 오후 11시 21분
@Christo Fogelberg execellent explanation and generalisation for optimizing the no of attempts. @ christo 아니오 fogelberg execellent 최적화하기위한 설명과 일반화를 시도합니다.
but ofcourse you can match sqrt(n)(how did you find this?) from duduqin solution. 하지만 당연하지를 일치시킬 수있습니다 sqrt (n) (하는 방법이 되셨습니까?)에서 duduqin 솔루션을합니다.
it is like : 이 같은 :
no of steps = n 지역의 단계 = n
let us assume x = no of steps between two attempts 우리 사이에 두 개의 시도의 단계 추측 x = 아니오
and y = total no of attempts with first egg (maximum) 그런데도 = 총 아무 소리와 첫 번째 계란을 시도합니다 (최대)
so we get 그럼 우리에겐
x*y = n x * 그리고 = n
and now no of attempt = y + x -1 (or y + x not sure) 그리고 이제 지역의 시도 = 그리고 755 -1 (또는 그리고 755 모르겠)
so for min(y + x - 1) 그렇기 때문에 분 (그리고 755 - 1)
derivative(y + x -1) = 0 파생 (그리고 755 -1) = 0
so you get x = y = sqrt(n) from here. 그러니 x = 및 = sqrt (n)를 여기에있습니다.
Now we can go with your solution. 이제 우리가 갈 수 귀하의 솔루션을합니다.
I dont know what to do when it is required to optimize not the no of attemps but the total no of steps travelled(going up to some floor and coming down to collect the egg(s) and in the same way). 나는 무엇을해야할지 모르는 경우가 아니을 최적화하는 것이 필요합니다 attemps하지만 지역의 전체 지역의 단계를 여행 (상승하고, 무너지는를 수집하는 일부 층, 계란 (들)와 같은 방식으로).
Please put your views. 당신의 전망에 넣어주세요.
December 4th, 2007 at 4:24 am 2007년 12월 4일에서 오전 4시 24분
Well because the questions is based upin eggs (fragile), we need to include the non-algorithmic parameters as well. 질문이 있기 때문에 잘 기반 upin 계란 (약한), 우리가 아닌 - 알고리즘 매개 변수를 포함해야합니다도합니다.
Looking at the question statement, nothing is mentioned about the material on which it is to be dropped & the place where it should be dropped. 질문을 문장을보고, 아무것도되는 물질에 대해서는 언급이있는 곳에 그것을 삭제 및 삭제되어야합니다. In those cases the egg could also be dropped on to the same floor from any height. 이러한 경우, 계란은 동일한 바닥에 떨어진 수도 모든 고도합니다.
December 4th, 2007 at 9:20 pm 2007년 12월 4일에서 오후 9시 20분
Obviously it is being dropped to the ground otherwise the question becomes meaningless. 명백히 그것은 다른 문제가 땅에 떨어졌다는 의미가된다. What non-algorithmic parameters are you talking about? - 알고리즘 매개 변수는 무엇 아닌 말씀이세요?
The task is to determine at which height (divisible by height of each floors which are of equal height) the egg breaks. 이 작업은 결정에 어떤 높이 (분할하여 각 플로어의 높이가 동일한 높이), 계란 나누기합니다. The material of egg is unknown but obviously it is made of stronger material than your regular poultry egg. 하지만 분명히 알 수없는 소재의 계란이 만들어진 것은 귀하의 일반 닭보다 더 강한 소재 계란을합니다.
December 14th, 2007 at 11:48 am 2007년 12월 14일에서 오전 11시 48분
One idea is that you want to maintain a constant risk throughout the drops to guarantee an equal average- and worst-case. 하나의 아이디어는 일정한 위험을 유지하고자하는 상품을 보장할 내내 대등한 평균 -와 최악의 - 사례합니다.
With the strategy of skipping a constant number of floors \ 일정 개수의 전략을 건너뛰는 플로어 \
January 18th, 2008 at 1:36 pm 2008년 1월 18일에서 오후 1시 36분
I found this page again randomly while checking nothing too noxious was being attributed to me on Google, it sounds like the discussion has moved on so I figure I\’ll add to it again 본 페이지를 다시 찾았을 확인하는 동안 나는 아무것도 무작위로 발생하는 유해는 자신의 전 날 구글, 듣기에 대한 토론이 이사를 그래서 난 그림 나는 \ '게요 장바구니에 다시
@Dhananjay: @ dhananjay :
Yes, going back now and reading duduqin\’s reasoning I see it is a specific example for n=100 of the general case. 예, 지금 돌아갈 및 읽기 duduqin \ '의 논리는 구체적인 예제를 보여 n = 100의 일반적인 사례.
You are also right that I did not explain why sqrt(n) was optimal - and in fact, as I think I noted, I\’m still not sure that it is! 또한 당신의 권리가 나는 이유를 설명 않았 sqrt (n)은 최적의 - 그리고 사실 적어 것 같아요, 나 \ 'm 아직 확신이있다!
In any case, I don\’t think derivatives factor into it. 어떠한 경우라도, 나 돈 \ 't 파생 상품 요인시켜 생각합니다. Perhaps they do but I\’m not sure what you\’re deriving with respect to. 아마도 그들은없습니다하지만 전 \ '모르겠 당신이 \'다시 파생과 관련하여합니다. I agree x = y and that the maximum number of attempts will be n=xy and that you can get sqrt(n) from that but I\’m still a little bit confused. 동의 x = 그리고 그 시도의 최대 개수는 n = xy을 얻을 수있습니다 sqrt (n)에서하지만 전 \ '아직 조금 혼란스러워합니다. Sorry! 죄송합니다! Also, what does the min function in min(x + y - 1) refer to or mean? 또한, 무엇을 최소 기능을 분 (x + 그리고 - 1)를 참조하거나 의미합니까?
###########
@dkaminski: @ dkaminski :
I haven\’t thought about this much, but I think you\’re right - it would be interesting to look at the expectation distribution. 나는있다 \ 't이 정도로 생각했다,하지만 제 생각에 당신 \'다시 오른쪽 -면 재미있을 분포에 대한 기대를 보면서 이런 생각을합니다. Any further thoughts? 그 이상의 생각하십니까? (I have none right now:) (지금은 아무도 없어 :)
Actually, talking of expectation, a cute wee problem with plenty of off-by-1 and off-by-k chances that a friend and I ended up talking about over dinner recently goes something like this: 사실, 이야기의 기대를, 귀여운 꼬마 문제를 충분히 -하여 - 1과 따로 따로 -에 - k 기회를 말하는가 결국은 저녁 식사 시간에 친구와 나는 최근에 식입니다이 :
You have a bag with 50 lengths of string inside it. 당신은이 50 길이의 문자열을 봉투 안에 그것합니다.
You pull out one end of one piece of string, leaving the rest of that piece in the bag. 당신의 한쪽 끝을 철수 하나 문자열, 봉투 안에는 그 부분의 나머지 부분 떠난다. You pull out a second end of string, possibly the end of a different piece of string and possibly the other end of the piece of string you\’re already holding. 두 번째 엔드의 문자열을 철수, 아마 월말에 다른 조각이 문자열과 아마 조각이 문자열의 나머지 끝부분을 \ '다시이 이미 보유합니다. You tie the two ends together before dropping them back in the bag. 2 엔드를 함께 묶어 봉투에 든하기 전에 그들을 돌려 하락합니다.
After all the ends have been tied to some other end, what is the expected number of loops in the bag? 이후의 모든 공동의 끝부분 일부가 다른 쪽 끝을, 어떤 경우에이 봉투 안에는 루프를 예상 개수?
OK, it\’s Friday night, there\’s jazz and cocktails on and if I\’m not going to go to that I should really be doing something more productive. 그래, 그것 \ '의 금요일 밤, 거기 \'의 재즈와 칵테일을 그리고 만약 내가 \ '아닙니다에 가서 일을하고있을 가롯 정말로 생산적합니다. Cheerio all! 잘있게 스타를 소개합니다!
xto