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

アルゴリズムは基本的に二分探索を行っています。あなたが抱えている問題の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 に答える
1

2 つのヒント:

  • 等価比較を 2 つifの の外に移動できます。
  • 数値が含まれていることがわかっている範囲を追跡する必要があります。これを行うと、ロジックは非常に簡単になります。
于 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 に答える
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 の間の中央値を見つけます。毎回最小値と最大値の差を縮めているので、最終的には残りの可能性が 1 つしかない状態で到達し、それがあなたの数字です。

上記のコードは良い例ではありませんが、説明に役立つことを願っています。

于 2014-10-30T21:26:10.227 に答える