找到你要的答案

Q:Hot and Cold Binary Search Game

Q:冷二进制搜索游戏

Hot or cold.

I think you have to do some sort of binary search but I'm not sure how.

Your goal is the guess a secret integer between 1 and N. You repeatedly guess integers between 1 and N. After each guess you learn if it equals the secret integer (and the game stops); otherwise (starting with the second guess), you learn if the guess is hotter (closer to) or colder (farther from) the secret number than your previous guess. Design an algorithm that finds the secret number in lg N + O(1) guesses.

Hint: Design an algorithm that solves the problem in lg N + O(1) guesses assuming you are permitted to guess integers in the range -N to 2N.

I've been racking my brain and I can't seem to come up with a a lg N + O(1).

I found this: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1316188034 but could not understand the diagram and it did not describe other possible cases.

热或冷。

我认为你必须做一些二进制搜索,但我不知道如何。

Your goal is the guess a secret integer between 1 and N. You repeatedly guess integers between 1 and N. After each guess you learn if it equals the secret integer (and the game stops); otherwise (starting with the second guess), you learn if the guess is hotter (closer to) or colder (farther from) the secret number than your previous guess. Design an algorithm that finds the secret number in lg N + O(1) guesses.

Hint: Design an algorithm that solves the problem in lg N + O(1) guesses assuming you are permitted to guess integers in the range -N to 2N.

我一直绞尽脑汁,我似乎无法拿出一一的LG N + O(1)。

我发现:HTTP:/ / www.ocf。伯克利。edu / ~ WWU / cgi-bin / yabb / yabb.cgi?板= riddles_cs;行动=显示;Num = 1316188034但不能理解图中并没有描述其他可能的情况。

answer1: 回答1:

For numbers between (1~N):

1st guess: (1/3)N

2nd guess: (2/3)N -> tells us the answer is either in 1~(1/2)N or (1/2)N +1 ~ N

3rd guess: in 1~(1/2)N: try (1/6)N; in (1/2)N +1 ~ N: try (5/6)N

...

Starting from 2nd guess, each step cuts the range in 1/2. So it's step 1 + lgN

数之间(1~n):

第一猜测:(1 / 3)N

第二猜:(2 / 3)N - >;告诉我们答案是1 ~(1 / 2)或(1 / 2)n + 1 ~ n

第三猜测:在1 ~(1 / 2)N:尝试(1 / 6)N;在(1 / 2)N + 1;尝试(5 / N)

从第二猜开始,每一步削减范围在1 / 2。所以它的步骤1 + lgn

answer2: 回答2:

This is a repost of my answer at Hot or Cold Guess Secret Number, which unfortunately has no upvoted or accepted answer:

This was a task at IOI 2010, for which I sat on the Host Scientific Committee. (We asked for an optimal solution instead of simply lg N + O(1), and what follows is not quite optimal.)

Not swinging outside -N .. 2N and using lg N + 2 guesses is straightforward; all you need to do is show that the obvious translation of binary search works.

Once you have something that doesn't swing outside -N .. 2N and takes lg N + 2 guesses, do this:

Guess N/2, then N/2+1. This tells you which half of the array the answer is in. Then guess the end of that half-array. You're either in one of the two "middle" quarters or you're in one of the two "end" quarters. If you're in a middle quarter, do the thing before and you win in lg N + 4 guesses. The ends are slightly trickier.

Suppose I need to guess a number in 1 .. K without straying outside 1 .. N and my last guess was 1. If I guess K/2 and I'm colder, then I next guess 1; I spent two guesses to get a similar subproblem that's 1/4 the size. If K/2 is hotter, I know the answer is in K/4 .. K. Guess K/2-1 next. The two subcases are K/4 .. K/2-1 and K/2 .. K, both of which are nice. But it took me three guesses to (in the worst-case) halve the size of the problem; if I ever do this, I wind up doing lg N + 6 guesses.

这是一个附在热或冷的猜密码我的答案,而不幸的是,没有upvoted或接受的答案:

这是在IOI 2010的任务,而我坐在主人的科学委员会。(我们要求最佳的解决方案,而不是简单的LG N + O(1),然后就是不太理想。)

不摆动外- N…2n和使用LG N + 2的猜测是直截了当的;所有你需要做的是表明二进制搜索明显的翻译作品。

一旦你有东西不摆在外面- N…LG N + 2次2N和需要,这样做:

猜N / 2,然后N / 2 + 1。这告诉你答案的数组中的哪一半。然后猜到一半的结束。你要么在其中的两个“中间”宿舍或你在两个“最后”宿舍之一。如果你在一个季度中,做事情前和LG N + 4的猜测你赢了。两端稍麻烦。

假设我需要猜一个数字在1…K不偏离外1。我最后的猜测是1。如果我想K / 2我冷,我一猜1;我花了两个猜测得到一个相似的子问题,1 / 4的大小。如果K / 2是热,我知道答案是在K / 4。K K/2-1猜下。两个子K / 4。K / 2-1和K / 2。这两个都不错。但我花了三次(最坏的)一半大小的问题;如果我这样做,我所做的LG N + 6的猜测。

answer3: 回答3:

Suppose you know that your secret integer is in [a,b], and that your last guess is c.

You want to divide your interval by two, and to know whether your secret integer lies in between [a,m] or [m,b], with m=(a+b)/2.

The trick is to guess d, such that (c+d)/2 = (a+b)/2.

Without loss of generality, we can suppose that d is bigger than c. Then, if d is hotter than c, your secret integer will be bigger than (c+d)/2 = (a+b)/2 = m, and so your secret integer will lie in [m,b]. If d is cooler than c, your secret integer will belong to [a,m].

You need to be able to guess between -N and 2N because you can't guarantee that c and d as defined above will always be [a,b]. Your two first guess can be 1 and N.

So, your are dividing your interval be two at each guess, so the complexity is log(N) + O(1).

A short example to illustrate this (results chosen randomly):

Guess    Result    Interval of the secret number
 1       ***       [1   , N    ]    // d    =  a   +  b  - c
 N       cooler    [1   , N/2  ]    // N    =  1   +  N  - 1
-N/2     cooler    [N/4 , N/2  ]    //-N/2  =  1   + N/2 - N
 5N/4    hotter    [3N/8, N/2  ]    // 5N/4 = N/4  + N/2 + N/2
-3N/8    hotter    [3N/8, 7N/16]    //-3N/8 = 3N/8 + N/2 - 5N/4
  .        .            .               .
  .        .            .               .
  .        .            .               .

Edit, suggested by @tmyklebu:

We still need to prove that our guess will always fall in bewteen [-N,2N]

By recurrence, suppose that c (our previous guess) is in [a-(a+b), b+(a+b)] = [-b,a+2b]

Then d = a+b-c <= a+b-(-b) <= a+2b and d = a+b-c >= a+b-(a+2b) >= -b

Initial case: a=1, b=N, c=1, c is indeed in [-b,a+2*b]

QED

假设你知道你的秘密整数在a,b,并且你最后的猜测是C。

你想把你的区间分为两个,并知道你的秘密整数是否位于[ A,M ]或[ M,B ],与m =(A + B)/ 2。

诀窍是猜测D,这样(C + D)/ 2 =(A + B)/ 2。

没有一般性的损失,我们可以假设D是大于C。然后,如果D是热比C,你的秘密整数将大于(C + D)/ 2 =(A + B)/ 2 = m,所以你的秘密整数将躺在[ M,B ]。如果D比C更酷,你的秘密整数将属于[ a,m ]。

你需要能够猜之间的N和2N因为你不能保证C和D上面定义的永远是[a,b ]。你的第一个猜测可以是1和N.

所以,你是除以你的间隔是两个在每个猜测,所以复杂的日志(N)+ O(1)。

一个简短的例子来说明这一点(结果随机选择):

Guess    Result    Interval of the secret number
 1       ***       [1   , N    ]    // d    =  a   +  b  - c
 N       cooler    [1   , N/2  ]    // N    =  1   +  N  - 1
-N/2     cooler    [N/4 , N/2  ]    //-N/2  =  1   + N/2 - N
 5N/4    hotter    [3N/8, N/2  ]    // 5N/4 = N/4  + N/2 + N/2
-3N/8    hotter    [3N/8, 7N/16]    //-3N/8 = 3N/8 + N/2 - 5N/4
  .        .            .               .
  .        .            .               .
  .        .            .               .

编辑“tmyklebu建议:

我们还需要证明我们的猜测总是落在在[ N,2n ]

复发,假设C(我们以前的猜测)是[一个(A + B),B(A + B)] = [ B,一个+ 2B ]

然后D = A + B & lt;= A + B(B)& lt;= a + b和d = A + B & gt;= A + B(A + B)& gt;= B

初始情况:A = 1,B = N,C = 1,C确实在[ B,A + 2 * b ]

量子电动力学

answer4: 回答4:

The solution is close to binary search. At each step you have an interval that the number can be in. Start with the whole interval [1, N]. First guess both ends - that is the numbers 1 and N. One of them will be closer, thus you will know that now the number you are searching for is in [1, N/2] or in [N/2 + 1, N](considering N even for simplicity). Now you go to the next step having a twice smaller interval. Continue using the same approach. Keep in mind that you've already probed one of the ends, however it may not be your last guess.

I am not sure what you mean by lg N + O(1), but the approach I suggest will perform O(log(N)) operations and in the worst case it will do exactly log4(N) probes.

该解决方案接近二进制搜索。在每个步骤中,你有一个区间,数字可以在。开始与整个间隔[ 1,N ]。第一猜测两端-这是数字1和N.其中之一将更接近,因此,你会知道,现在你正在寻找的数字是[ 1,N / 2 ]或在N / 2 +,N(考虑N甚至简单)。现在你进入下一步有两个较小的间隔。继续使用相同的方法。请记住,你已经探索了其中的一个目的,但它可能不是你最后的猜测。

我不知道你说的什么LG N + O(1),但我建议的方法将执行O(log(n))的操作和在最坏的情况下会做log4(N)探针。

algorithm  binary-search