3

これは Project Euler の問題 11 です。20x20 の数字のグリッドが表示され、次のように求められます。

20x20 のグリッドで任意の方向 (上、下、左、右、または斜め) に隣接する 4 つの数の最大の積は?

コードを何度か見直しましたが、結果が間違っている理由がわかりません。

#include <iostream>
using namespace std;

void find_greatest_product()
{   
    int grid[20][20] =
    {{8, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 8},
    {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00},
    {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65},
    {52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91},
    {22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
    {24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
    {32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
    {67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21},
    {24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
    {21, 36, 23, 9, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95},
    {78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 9, 53, 56, 92},
    {16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57},
    {86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
    {19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40},
    {04, 52, 8, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
    {88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
    {04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36},
    {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16},
    {20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54},
    {01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48}};

    int downRight_diag = 1;
    int upRight_diag = 1;
    int left = 1;
    int right = 1;
    int up = 1;
    int down = 1;
    int firstMax = 0;
    int absoluteMax = 0;

    for(int i = 0; i < 20; i++)
    {
        for(int j = 0; j < 20; j++)
        {
            for(int k = i; k < 17; k++)
            {
                downRight_diag = grid[i][j]*grid[i+1][j+1]*grid[i+2][j+2]*grid[i+3][j+3];
                down = grid[i][j]*grid[i+1][j]*grid[i+2][j]*grid[i+3][j];

                if(downRight_diag > down && downRight_diag > firstMax)
                    firstMax = downRight_diag;
                else if(down > downRight_diag && down > firstMax)
                    firstMax = down;

            }
            for(int l = i; l >= 3 && l < 20; l++)
            {
                upRight_diag = grid[i][j]*grid[i-1][j+1]*grid[i-2][j+2]*grid[i-3][j+3];
                up = grid[i][j]*grid[i-1][j]*grid[i-2][j]*grid[i-3][j];

                if(upRight_diag > firstMax)
                    firstMax = upRight_diag;
                else if(up > firstMax)
                    firstMax = up;
            }
            if(j < 17)
            {
                left = grid[i][j]*grid[i][j+1]*grid[i][j+2]*grid[i][j+3];

                if(left > firstMax)
                    firstMax = left;
            }
            if(j >= 3)
            {
                right = grid[i][j]*grid[i][j-1]*grid[i][j-2]*grid[i][j-3];

                if(right > firstMax)
                    firstMax = right;
            }

            if(firstMax > absoluteMax)
            {
                absoluteMax = firstMax;    
            }

            downRight_diag = 1;
            upRight_diag = 1;
            left = 1;
            right = 1;
            up = 1;
            down = 1;
            firstMax = 0;
        }
    }
    cout << absoluteMax << endl;
}
int main()
{

    find_greatest_product();
    system("pause");
}

明確にするために：左から右へ、left右から左へ製品を計算していrightます。

これがおそらく最も効率的な方法ではないことは承知していますが、フィードバックをいただければ幸いです。ありがとうございました！

4

3 に答える 3

5

As MRAB has answered, it's most likely due to array overflow.

The other thing I noticed (but probably isn't a problem because of redundant calculations) is this:

            if(upRight_diag > firstMax)
                firstMax = upRight_diag;
            else if(up > firstMax)
                firstMax = up;

If both are bigger than firstMax AND up happens to be the global maximum, then you will miss it. But this is odd because up is redundant (handled by down earlier).

I would make some general comments. Firstly, why do you loop multiple times for the up/down tests? You're not even using the loop variable. You just want to test boundaries (which in fact you're not doing). Also, there's no need to calculate left when you are already calculating right. Same with up and down as I've already mentioned.

Here's a simplification that calculates the horizontal, vertical and two diagonals:

for(int i = 0; i < 20; i++)
{
    for(int j = 0; j < 20; j++)
    {
        int horz=0, vert=0, diagDR=0, diagUR=0;

        if( j >= 3 )
            horz = grid[i][j-3]*grid[i][j-2]*grid[i][j-1]*grid[i][j];

        if( i >= 3 )
            vert = grid[i-3][j]*grid[i-2][j]*grid[i-1][j]*grid[i][j];

        if( i >= 3 && j >= 3 ) {
            diagDR = grid[i-3][j-3]*grid[i-2][j-2]*grid[i-1][j-1]*grid[i][j];
            diagUR = grid[i-3][j]*grid[i-2][j-1]*grid[i-1][j-2]*grid[i][j-3];
        }

        if( horz > absoluteMax ) absoluteMax = horz;
        if( vert > absoluteMax ) absoluteMax = vert;
        if( diagDR > absoluteMax ) absoluteMax = diagDR;
        if( diagUR > absoluteMax ) absoluteMax = diagUR;
    }
}
于 2012-08-15T00:13:19.220 に答える
2

より一般的に (常に 4 つ連続、または常に 20 であると想定しないでください)。 http://codepad.org/YkrT72kR 入手しました

70600674 (3,15) の左斜め下方向

#include <iostream>
#include <inttypes.h>

const uint8_t HEIGHT = 20;
const uint8_t WIDTH = 20;
const uint8_t CONSECUTIVE = 4;
const int GRID[HEIGHT][WIDTH] =
    {{8, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 8},
    {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00},
    {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65},
    {52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91},
    {22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80},
    {24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50},
    {32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70},
    {67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21},
    {24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
    {21, 36, 23, 9, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95},
    {78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 9, 53, 56, 92},
    {16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57},
    {86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
    {19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40},
    {04, 52, 8, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
    {88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
    {04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 8, 46, 29, 32, 40, 62, 76, 36},
    {20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16},
    {20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54},
    {01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48}};

int main()
{
    uint64_t max = 0, temp_max = 0;
    uint16_t max_x=0, max_y=0;
    std::string direction = "";
    for (uint8_t i=0; i<HEIGHT; i++)
    {
        for (uint8_t j=0; j<WIDTH; j++)
        {
            // Can we check right?
            if (j < (WIDTH - CONSECUTIVE))
            {
                temp_max=1;
                for (int k=0; k<CONSECUTIVE; k++)
                {
                    temp_max *= GRID[i][j+k];
                }
                if (temp_max > max)
                {
                    max = temp_max;
                    max_x = j;
                    max_y = i;
                    direction = "right";
                }
            }

            // Can we check down?
            if (i < (WIDTH - CONSECUTIVE))
            {
                temp_max=1;
                for (int k=0; k<CONSECUTIVE; k++)
                {
                    temp_max *= GRID[i+k][j];
                }
                if (temp_max > max)
                {
                    max = temp_max;
                    max_x = j;
                    max_y = i;
                    direction = "down";
                }
            }

            // Can we check down-right?
            if ((i < (HEIGHT - CONSECUTIVE)) && (j < (WIDTH - CONSECUTIVE)))
            {
                temp_max=1;
                for (int k=0; k<CONSECUTIVE; k++)
                {
                    temp_max *= GRID[i+k][j+k];
                }
                if (temp_max > max)
                {
                    direction = "diagonal down right";
                    max = temp_max;
                    max_x = j;
                    max_y = i;
                }
            }

            // Can we check up-right?
            if ((i > (CONSECUTIVE)) && (j < (WIDTH - CONSECUTIVE)))
            {
                temp_max=1;
                for (int k=0; k<CONSECUTIVE; k++)
                {
                    temp_max *= GRID[i-k][j+k];
                }
                if (temp_max > max)
                {
                    direction = "diagonal up right";
                    max = temp_max;
                    max_x = j;
                    max_y = i;
                }
            }

        }
    }
    std::cout << "Max product was " << max << " at (" << max_x << "," << max_y << ") in direction " << direction << std::endl;
    return 0;
}

素敵な小さな挑戦。check up, left, diag-up-left, diag-up-right は不要であることを忘れないでください。そして、前述のように、常に配列の境界を確認してください

于 2012-08-15T01:58:57.550 に答える
1

配列の境界をチェックしていないためだと思います。

たとえば、iが 19 でjが 0 の場合、 になりますがdownRight_diag = grid[19][0]*grid[20][1]*grid[21][2]*grid[22][3];、gridとして定義されint grid[20][20]ます。

于 2012-08-15T00:05:57.477 に答える