java - 号码搜索(最有效)

Question

假设 N 是一个随机数(范围 1 到 1000)。我们需要猜测 N，对于每次猜测，可能会给出以下反馈之一:

1. 猜测正确；
2. 猜测太大，因此您应该猜测一个较小的数字；
3. 猜测的数字太小，因此您应该猜测一个更大的数字。

在情况 3 中，N 的值将增加 P，其中 P 是另一个随机数(范围 1 到 200)。

如果初始值N=800，P=150。你按以下顺序猜测: Example

如何编写以下代码，特别是当它涉及两个数字(N 和 P)时。我正在考虑使用二分搜索，但如果我们不知道 P 的值，这将是一个问题。

这是我现在的代码:

myGuess=0;
checkCode=0;
int lower = 1, upper = 999;
myGuess = (lower+upper)/2;

do{
    if (checkCode == 2) {
    upper = myGuess - 1;
    }
else if (checkCode == 3){
    lower = myGuess + 1;
    upper += ran.nextInt(200);  //Need to guess the P value
    }

    myGuess = (lower+upper)/2;
}while(checkCode!=1);

Answer 1

第一步是获得一个有效的猜测系统。此代码提供了二分搜索方法的粗略指南。第二步是分析如何提高效率。 (注:可以恢复部分S.O.P()来查看进度)

private static int doGuess()
{
    int lowerBound = 1;
    int upperBound = 1000;
    int numberToGuess = ThreadLocalRandom.current().nextInt(upperBound) + 1;
    int guess = 0;
    int steps = 0;
    int increases = 0;

    while (guess != numberToGuess) {
        ++steps;

        guess = (lowerBound + upperBound) / 2;

//            System.out.printf("[%5d] Guessing %d (is: %d)%n",
//                    steps,
//                    guess,
//                    numberToGuess);

        if (guess == numberToGuess) {
            System.out.printf("Guessed %d in %d steps (%d increases)%n",
                    numberToGuess,
                    steps,
                    increases);
            continue;
        }
        else if (guess > numberToGuess) {
//                System.out.println("Guess is too high!");
            // adjust upper bound to be guess
            upperBound = guess;
        }
        else {
//                System.out.println("Guess is too low; changing number");
            numberToGuess += ThreadLocalRandom.current().nextInt(200) + 1;

            // adjust lower bound to this guess
            lowerBound = guess;

            // the number moved, so adjust upper bound by max range
            upperBound += 200;

            // track increases
            ++increases;
        }
    }

    return steps;
}

public static void main(String[] args)
{
    List<Integer> steps = new ArrayList<>();
    int iterations = 10;

    for (int i = 0; i < iterations; ++i) {
        steps.add(doGuess());
    }

    IntSummaryStatistics stats = 
            steps.stream().collect(IntSummaryStatistics::new,
                    IntSummaryStatistics::accept,
                    IntSummaryStatistics::combine);

    System.out.println(stats);
}

输出:

Guessed 8838 in 145 steps (83 increases)
Guessed 6301 in 106 steps (59 increases)
Guessed 3239 in 58 steps (30 increases)
Guessed 5785 in 109 steps (58 increases)
Guessed 2547 in 56 steps (27 increases)
Guessed 16071 in 300 steps (164 increases)
Guessed 3847 in 54 steps (31 increases)
Guessed 3125 in 42 steps (24 increases)
Guessed 6708 in 93 steps (57 increases)
Guessed 7433 in 143 steps (74 increases)
IntSummaryStatistics{count=10, sum=1106, min=42, average=110.600000, max=300}

[注:根据快速模拟，多次运行的平均值约为 115，因此效率改进平均应从 115 步减少]
[注:每次猜测的代码变化量都不同，太低； OP 的评论可能会建议随机选择一次增加，在这种情况下，上述代码中猜测的数字增加需要更改]

编辑:
从逻辑上讲，如果猜测低位移动是第一个猜测，那么使用某种偏向于选择更高的位置似乎是合乎逻辑的。正如 Holger 在各种评论中所建议的，有一些方法可以进行调整。

在看到 Holger 的建议之前，我已经尝试过一些基本的调整；然后我也尝试实现他的算法。但是，我还没有找到可以做出明显改进的调整(有些甚至更糟)。

使用 100,000 次运行，标准二分搜索平均为 127.7 步(注:比我之前基于较低运行次数的估计略有增加)。假设我正确实现 Holger 算法，则在 100,000 次时，平均值为 126.6 步。

由于我缺乏进一步研究的数学技能(不幸的是目前还没有时间)，因此简单的修改似乎并没有从根本上改变算法的平均效率。我没有调查更糟糕的情况。在 Math StackExchange 上提问，看看他们是否可以提供任何明确的输入，会很有趣。我确实进行了快速的 Google 搜索，但没有时间阅读可能会带来一些改进的学术论文(同样，在速度和算法复杂性方面存在未知的权衡)。

当然，也有可能我没有正确执行霍尔根的建议。这是我直接根据评论使用的代码(如果太低则替换猜测计算中的更改):

              if (tryHolgen) {
                double risc = 200.0/(upperBound-lowerBound);
                if (risc <= 1) {
                    guess = (upperBound + lowerBound) /2;
                }
                else {
                    guess = upperBound - 
                      Math.max((int)((upperBound - lowerBound)/risc/2),1);
                }
              else {
                guess = (lowerBound + upperBound) / 2;
            }

我很好奇其他人是否有比直接二分搜索更好的实现。

有趣的是，使用标准二分搜索的 1..1000 范围平均需要 8 个步骤，复杂度为 O(log n)。通过允许猜测发生变化，平均值将移动约 120 步。