1

我得到了一个“损坏的算法”来修复。它适用于“猜 1-100 之间的数字”游戏，计算机在 7 个问题/迭代内回答。

我得到的简短建议只需要对算法进行最小的更改，抱歉，如果这含糊不清，我也在想同样的事情。

无论如何，该算法充满了我已经清理的愚蠢错误。对于 33 的测试用例，算法分配以下中位数

50,25,37,19 << 19 显然是不正确的。

我知道 last_median = 当前中位数不在正确的位置。这是漫长的一天，如果有人能对此有所了解，我将不胜感激。

const int MAX_VALUE = 100;
int current_median = MAX_VALUE /2;
int last_median = 0;

while (true)
{
    last_median = current_median;

    if(number >= current_median)
    {
        if(number == current_median)
        { 
            //Check for equality
            cout << endl << number << endl; 
            break;
        } 

        current_median += last_median  /2;
    }
    else if(number <= current_median)
    {
        if(number == current_median)
        { 
            // Check for equality
            cout<<endl<<number<<endl; 
            break;
        }

        current_median -= last_median /2;
    }
}
4

4 回答 4

1

两个提示：

  • 您可以将相等比较移到两个ifs 之外。
  • 您应该跟踪您知道包含该数字的范围。一旦你这样做，逻辑将非常简单。
于 2013-10-30T20:33:08.257 回答
1

如果您正在寻找 0 到 100 之间的数字，您将在 7 步或更少的步骤中找到它。如果你想更精确，如果你正在寻找一个奇数，它恰好是 7 步，如果你正在寻找一个偶数，它在某些情况下会是 6 或更少。我将在下面放一个简单的代码。我没有把所有的支票都放进去（输入数字而不是字母或其他东西），它只是在几分钟内写出来的：

#include <iostream>

int main(){

    std::cout << "Think of a number between 1 and 100" << std::endl ;
    std::cout << "Press 0 if my number is correct. 1 if YOUR number is smaller. 2 if bigger" << std::endl;

    int response = 0;
    int middle = 64;
    int low = 0;
    int high = 128;
    int counter = 1;

    while(response!=0)
    {
        std::cout << counter << " Guess " << counter << ": " << middle << std::endl;
        std::cout <<"Press 0(bingo)   1(smaller)   2(greater):   " ;
        std::cin >> response ;
        std::cout << std::endl ;
        counter++;
        switch (response){
        case 0:
            std::cout << "Your number is: " << middle << std::endl;
            break;

        case 1:
            high = middle;
            middle = (low+high)/2;
            break;

        case 2:
            low = middle;
            middle = (low+high)/2;
            break;

        } //end swhitch

    }; //end while


    return 0;
}
于 2013-10-30T21:00:38.763 回答
1

该算法基本上是进行二进制搜索。您遇到的一个问题是您的条件：

if(number >= current_median)
// ...
else if(number <= current_median)
// ...

如果number等于，你想退出循环，而不是继续它：

if(number > current_median)
// ...
else if(number < current_median)
// ...
else // we are equal
{
    break;
}

您还应该调整条件以检查(low, high)范围，因为随着您的中值接近实际值，它应该（迅速）变小。

一个简单的例子：

#include <iostream>

int main()
{
    std::cout << "Pick a number between [0, 100] (Don't tell me what it is!)";

    unsigned int low = 0;
    unsigned int high = 100;
    do
    {
        unsigned int median = (low + high) / 2;
        std::cout << "Is your number > " << median << "?  ";
        char answer;
        std::cin >> answer;
        if (answer == 'Y' || answer == 'y')
        {
            low = median;
            continue;
        }
        else
        {
            std::cout << "Is your number < " << median << "?  ";
            std::cin >> answer;
            if (answer == 'Y' || answer == 'y')
            {
                high = median;
                continue;
            }
            else // we are equal
            {
               low = high = median;
            }
        }

    } while (low != high);

    std::cout << "Your number is " << low << std::endl;
    return 0;
}
于 2013-10-30T20:35:58.993 回答
0 
int main()
{
char uput = '?';
int maxx = 100;
int minn = 0;

while (minn != maxx)
{
    cout << (minn+maxx)/2 << ": [h]igher, [l]ower or [e]qual?";
    cin >> uput;
    if (uput == 'l')
    {
        maxx = (minn+maxx)/2;
    }
    else if (uput == 'h')
    {
        minn = (minn+maxx)/2;
    }
    else if (uput == 'e')
    {
        cout << "Your number is " << (minn+maxx)/2 << ". Yay.";
        return 0;
    }
}
return 0;
}

如果数字低于中位数，则中位数为新的最大值。

如果数字高于中位数，则中位数是新的最小值。

创建一个循环。对于循环中的每个时间，找到 minn 和 maxx 之间的中值。由于您每次都在缩小最小值和最大值之间的数字之间的差距，因此您最终将只剩下一种可能性，那就是您的数字。

上面的代码不是一个很好的例子，但希望它有助于说明。

于 2014-10-30T21:26:10.227 回答