题目11：在20×20的网格中同一直线上四个数的最大乘积是多少？

欧拉计划 · 发表于 2015-4-21 16:13:44

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由欧拉计划于 2023-6-28 03:01 编辑

Largest product in a grid

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
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 08 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 09 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 09 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 08 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 08 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

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

题目：

在以下这个 20×20 的网格中，四个处于同一对角线上的相邻数字用红色标了出来：

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
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 08 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 09 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 09 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 08 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 08 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

这四个数字的乘积是：26 × 63 × 78 × 14 = 1788696。

在这个 20×20 网格中，处于任何方向上（上，下，左，右或者对角线）的四个相邻数字的乘积的最大值是多少？

翅膀团 · 发表于 2015-7-26 17:20:30

本帖最后由翅膀团于 2015-11-16 14:13 编辑

#include <stdio.h>

    int num[20][20] = {
                        { 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91, 8},
                        {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62, 0},
                        {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65},
                        {52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,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, 3,45, 2,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, 2,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21},
                        {24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
                        {21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95},
                        {78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92},
                        {16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57},
                        {86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58},
                        {19,80,81,68, 5,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40},
                        { 4,52, 8,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66},
                        {88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69},
                        { 4,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, 4,36,16},
                        {20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54},
                        { 1,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48}
                     };

int max_Level(void)
{
    int i,j,z,result=1,max=0;
    for(z=0;z<20;z++)
    {
    for(i=0;i<17;i++)
    {
    for(j=0;j<4;j++)
    {
    if(num[z][i] == 0)
    {
        goto Z;
    }
    result *= num[z][i];
    i++;
    }
    if(result > max)
    {
    max = result;
    }
    i = i-4;
Z:  result = 1;
    }
    }
    return max;
}

int max_Vertical(void)
{
    int i,j,z,result=1,max=0;
    for(z=0;z<20;z++)
    {
    for(i=0;i<17;i++)
    {
    for(j=0;j<4;j++)
    {
    if(num[i][z] == 0)
    {
        goto Z;
    }
    result *= num[i][z];
    i++;
    }
    if(result > max)
    {
    max = result;
    }
    i = i-4;
Z:  result = 1;
    }
    }
    return max;
}

int max_Slash_top(void)
{
    int i,j,f,z,result=1,max=0;
    for(f=0;f<17;f++)
    {
    z=0,i=3+f;
    for(;z<1+f;z++,i--)
    {
    for(j=0;j<4;j++)
    {
    if(num[z][i] == 0)
    {
    goto Z;
    }
    result *= num[z][i];
    i--,z++;
    }
    if(result > max)
    {
    max = result;
    }
    z = z-4;
    i = i+4;
Z:  result = 1;
    }
    }
    return max;
}

int max_Slash_below(void)
{
    int i,j,f,z,result=1,max=0;
    for(f=0;f<17;f++)
    {
    z=19,i=16-f;
    for(;z<1+f;z--,i++)
    {
    for(j=0;j<4;j++)
    {
    if(num[z][i] == 0)
    {
    goto Z;
    }
    result *= num[z][i];
    i++,z--;
    }
    if(result > max)
    {
    max = result;
    }
    z = z+4;
    i = i-4;
Z:  result = 1;
    }
    }
    return max;
}

int max_Backslash_top(void)
{
    int i,j,f,z,result=1,max=0;
    for(f=0;f<17;f++)
    {
    z=0,i=16-f;
    for(;z<1+f;z++,i--)
    {
    for(j=0;j<4;j++)
    {
    if(num[z][i] == 0)
    {
    goto Z;
    }
    result *= num[z][i];
    i--,z++;
    }
    if(result > max)
    {
    max = result;
    }
    z = z-4;
    i = i+4;
Z:  result = 1;
    }
    }
    return max;
}

int max_Backslash_below(void)
{
    int i,j,f,z,result=1,max=0;
    for(f=0;f<17;f++)
    {
    z=19,i=3+f;
    for(;z<1+f;z--,i++)
    {
    for(j=0;j<4;j++)
    {
    if(num[z][i] == 0)
    {
    goto Z;
    }
    result *= num[z][i];
    i++,z--;
    }
    if(result > max)
    {
    max = result;
    }
    z = z+4;
    i = i-4;
Z:  result = 1;
    }
    }
    return max;
}

int main(void)
{

    int a,b,c1,c2,d1,d2,max=0;
    a = max_Level();
    b = max_Vertical();
    c1 = max_Slash_top();
    c2 = max_Slash_below();
    d1 = max_Backslash_top();
    d2 = max_Backslash_below();
    if(a > max)
    {
    max = a;
    }
    if(b > max)
    {
    max = b;
    }
    if(c1 > max)
    {
    max = c1;
    }
    if(c2 > max)
    {
    max = c2;
    }
    if(d1 > max)
    {
    max = d1;
    }
    if(d2 > max)
    {
    max = d2;
    }
    
    printf("max=%d\n",max);
}

如果有错误希望指出

huomqh · 发表于 2016-6-13 18:04:34

juzhen='''08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
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 08 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 09 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 09 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 08 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 08 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
'''
list1=[]
list2=[]
list3=[]
i=0
j=0
list1=juzhen.split('\n')
list1.pop()
for i in range(0,20):
    list2.append(list1[i].split(' '))
summax=0
sum1=1
for i in range(0,20):
    list2[i].append('0')
    list2[i].append('0')
    list2[i].append('0')
for i in range(0,23):
    list3.append('0')
for i in range(0,3):
    list2.append(list3)
for i in range(0,20):
    for j in range(0,20):
        sum1=1
        for x in range(0,4):
            sum1*=int(list2[i+x][j+x])
        if sum1>summax:
            summax=sum1
            a,b=i,j
print (summax)
for x in range(0,4):
    print(int(list2[a+x][b+x]),end="*")

40304286=94*99*71*61

k329266978 · 发表于 2016-8-15 11:19:31

#include<stdio.h>
#include<math.h>
        int s[20][20]={
        {8,2,22,97,38,15,0,40,0,75,4,5,7,78,52,12,50,77,91,8},
        {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,0},
        {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,49,13,36,65},
        {52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71,37,2,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,3,45,2,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,2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21},
        {24,55,58,5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
        {21,36,23,9,75,0,76,44,20,45,35,14,0,61,33,97,34,31,33,95},
        {78,17,53,28,22,75,31,67,15,94,3,80,4,62,16,14,9,53,56,92},
        {16,39,5,42,96,35,31,47,55,58,88,24,0,17,54,24,36,29,85,57},
        {86,56,0,48,35,71,89,7,5,44,44,37,44,60,21,58,51,54,17,58},
        {19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,89,55,40},
        {04,52,8,83,97,35,99,16,7,97,57,32,16,26,26,79,33,27,98,66},
        {88,36,68,87,57,62,20,72,3,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,4,36,16},
        {20,73,35,29,78,31,90,1,74,31,49,71,48,86,81,16,23,57,5,54},
        {01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48}};
int Num_Ver,Num_Hor;
void main()
{
int judge(int i,int j,int max,int *p);
int calc_horizontal(int i,int j);
int calc_vertical(int i,int j);
int calc_diagonal(int i,int j);
int calc_max(int a,int b,int c,int max,int *p,int i,int j);
int i,j,max=0,method=0;//about method  1:horizontal 2:vertical 3:calc_diagonal
int *p=&method;
for(i=0;i<20;i++)
for(j=0;j<20;j++)
{
max=judge(i,j,max,p);
}
printf("the max %d\n",max);
if(method==1) printf("the combination was [%d][%d] [%d][%d] [%d][%d] [%d][%d]\n",Num_Ver,Num_Hor,Num_Ver,Num_Hor+1,Num_Ver,Num_Hor+2,Num_Ver,Num_Hor+3);
if(method==2) printf("the combination was [%d][%d] [%d][%d] [%d][%d] [%d][%d]\n",Num_Ver,Num_Hor,Num_Ver+1,Num_Hor,Num_Ver+2,Num_Hor,Num_Ver+3,Num_Hor);
if(method==3) printf("the combination was [%d][%d] [%d][%d] [%d][%d] [%d][%d]\n",Num_Ver,Num_Hor,Num_Ver+1,Num_Hor+1,Num_Ver+2,Num_Hor+2,Num_Ver+3,Num_Hor+3);
}



int judge(int i,int j,int max,int *p)
{
int max1,max2,max3;
max1=(j<=16)?calc_horizontal(i,j):0;
max2=(i<=16)?calc_vertical(i,j):0;
max2=(i<=16&&j<=16)?calc_diagonal(i,j):0;

return calc_max(max1,max2,max3,max,p,i,j);
}

int calc_horizontal(int i,int j)
{
return s[i][j]*s[i][j+1]*s[i][j+2]*s[i][j+3];
}


int calc_vertical(int i,int j)
{
return s[i][j]*s[i+1][j]*s[i+2][j]*s[i+3][j];
}

int calc_diagonal(int i,int j)
{
return s[i][j]*s[i+1][j+1]*s[i+2][j+2]*s[i+3][j+3];
}

int calc_max(int a,int b,int c,int max,int *p,int i,int j)
{
int t,max_0;
t=0,max_0=0;
if(a>b) {max_0=a;t=1;}
else {max_0=b;t=2;}
if(max_0<c) {max_0=c;t=3;}

if(max_0>max) {*p=t;Num_Ver=i;Num_Hor=j;return max_0;}
else return max;
}

k329266978 · 发表于 2016-8-15 11:21:52

输出答案是[8][10]*[8][11]*[8][12]*[8][13]=78*78*96*83=48477312

Plusenxue · 发表于 2016-8-26 21:45:32

juzhen='''08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 
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 08 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 09 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 09 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 08 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 08 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 
'''
newtemp = []
vale = []
temp = juzhen.split('\n',20)
for i in range(20):
    templinei = temp[i].split(' ',19)
    for k in range(20):
        templinei[k] = int(templinei[k])
    newtemp.append(templinei)
for i in range(20):
    for j in range(17):
        vale.append(newtemp[i][j]*newtemp[i][j+1]*newtemp[i][j+2]*newtemp[i][j+3])

for i in range(17):
    for j in range(20):
        vale.append(newtemp[i][j]*newtemp[i+1][j]*newtemp[i+2][j]*newtemp[i+3][j])

for i in range(17):
    for j in range(17):
        vale.append(newtemp[i][j]*newtemp[i+1][j+1]*newtemp[i+2][j+2]*newtemp[i+3][j+3])


for i in range(17):
    for j in range(3,20):
        vale.append(newtemp[i][j]*newtemp[i+1][j-1]*newtemp[i+2][j-2]*newtemp[i+3][j-3])

print(max(vale))

jerryxjr1220 · 发表于 2016-9-17 11:19:03

本帖最后由 jerryxjr1220 于 2016-9-17 13:03 编辑

都不对吧，我算出来最大是70,600,674。
[6][12]开始，左下方4个的乘积。
89*94*97*87

8  2  22 97 38 15 0  40 0  75 4  5  7  78 52 12 50 77 91 8  

49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 4  56 62 0  

81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 3  49 13 36 65 

52 70 95 23 4  60 11 42 69 24 68 56 1  32 56 71 37 2  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 3  45 2  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 2  62 12 20 95 63 94 39 63 8  40 91 66 49 94 21 

24 55 58 5  66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 

21 36 23 9  75 0  76 44 20 45 35 14 0  61 33 97 34 31 33 95 

78 17 53 28 22 75 31 67 15 94 3  80 4  62 16 14 9  53 56 92 

16 39 5  42 96 35 31 47 55 58 88 24 0  17 54 24 36 29 85 57 

86 56 0  48 35 71 89 7  5  44 44 37 44 60 21 58 51 54 17 58 

19 80 81 68 5  94 47 69 28 73 92 13 86 52 17 77 4  89 55 40 

4  52 8  83 97 35 99 16 7  97 57 32 16 26 26 79 33 27 98 66 

88 36 68 87 57 62 20 72 3  46 33 67 46 55 12 32 63 93 53 69 

4  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 4  36 16 

20 73 35 29 78 31 90 1  74 31 49 71 48 86 81 16 23 57 5  54 

1  70 54 71 83 51 54 69 16 92 33 48 61 43 52 1  89 19 67 48 

6 12 70600674 lx
Time: 0.016 sec

# 在这个 20×20,网格中，处于任何方向上（上，下，左，右或者对角线）的四个相邻数字的乘积的最大值是多少？
matrix = [
'08','02','22','97','38','15','00','40','00','75','04','05','07','78','52','12','50','77','91','08','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','08','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','09','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','09','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','08','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','08','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']

import time
start = time.time()

matrix1 = []
for each in matrix:
    matrix1.append (int(each))

def showMatrix(matrix):  
    for j in range(20):  
        for i in range(20):
            if len (str(matrix[j*20+i])) == 1:
                print('%d '%(matrix[j*20+i]),end=' ')
            else:
                print('%d '%(matrix[j*20+i]),end='')  
        print('\n') 

class point:
        def __init__(self,x,y):  #x = col; y = row;
                self.x=x  
                self.y=y  
                self.ver=[]  
                self.hor=[]
                self.rx=[]
                self.lx=[]
                self.maxi=0  

def rowVer(point,matrix):
    row = []
    if point.x <17:
        row=matrix[(point.y*20+point.x):(point.y*20+point.x+4)] 
    return row #list type  
  
def colHor(point,matrix):  
    col=[]  
    if point.y <17:
        for i in range(point.y*20+point.x,point.y*20+point.x+80,20):  
            col.append(matrix[i])   
    return col #list type  

def rcRx(point, matrix):
    rx = []
    if point.x <17 and point.y <17:
        for i in range(point.y*20+point.x,point.y*20+point.x+84,21):  
            rx.append(matrix[i])
    return rx #list type
        
def rcLx(point,matrix):
    lx = []
    if point.x >2 and point.y <17:
        for i in range(point.y*20+point.x,point.y*20+point.x+76,19):
            lx.append(matrix[i])
    return lx #list type

def initPoint(matrix):
    length = len(matrix)
    pointlist = []
    for i in range(length):
        p=point(i%20,i//20)
        p.ver =  rowVer(p,matrix)
        p.hor =  colHor(p,matrix)
        p.rx =  rcRx(p,matrix)
        p.lx =  rcLx(p,matrix)
        pointlist.append(p)
    return pointlist

testlist = initPoint(matrix1)
maxam = 1
max_x = 0
max_y = 0
mm = ''
for each in testlist:
    vertotal = 1
    hortotal = 1
    rxtotal = 1
    lxtotal = 1
    for k in range(4):
        if each.ver != []:
            vertotal *= each.ver[k]
        if each.hor != []:
            hortotal *= each.hor[k]
        if each.rx != []:
            rxtotal *= each.rx[k]
        if each.lx != []:
            lxtotal *= each.lx[k]
        each.maxi = max(vertotal,hortotal,rxtotal,lxtotal)
for p in testlist:
    if p.maxi > maxam:
        maxam = p.maxi
        max_x = p.x
        max_y = p.y
        if p.maxi == p.ver:
            mm = 'ver'
        elif p.maxi == p.hor:
            mm = 'hor'
        elif p.maxi == p.rx:
            mm = 'rx'
        else:
            mm = 'lx'

end = time.time()

showMatrix(matrix1)

print (max_x, max_y, maxam, mm) 

print ('Time: %.3f sec' % (end-start))

lyciam · 发表于 2016-11-18 11:59:38

import time
t = time.clock()

def euler11():
    """
    在以下20X20的网格中，四个处于同一对角线上的相邻数字用红色标了出来：
    """
    gridnum="""
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
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 08 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 09 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 09 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 08 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 08 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
    """
    """
    这个四个数字的乘积是：26 X 63 X 78 X 14 = 1788696
    在这个20 X 20 网格中，处于任何方向上（上下左右或者对角线）的四
    个相邻数字的乘积的最大值是多少？
    """
    gridlist = [ [int(m) for m in row] for row in [ n.split() for n in gridnum.strip().split('\n') ]  ]
    x_left = [gridlist[ n ][ n ] for n in range(20)]
    x_right = [gridlist[ n ][19-n ] for n in range(20)]
    gridlist.insert(20,x_left)
    gridlist.insert(21,x_right)
    result = [ 0, [0, 0, 0, 0] ]
    for row in gridlist:
        for n in range(len(row)-3):
            temp = row[n]*row[n+1]*row[n+2]*row[n+3]
            if result[0] < temp:
                result = [temp, [row[n], row[n+1], row[n+2], row[n+3] ] ]
    return result
print(euler11(), '--time: ', time.clock()-t)

[48477312, [78, 78, 96, 83]] --time: 0.0010933442278124534

jerryxjr1220 · 发表于 2016-11-19 07:42:28

lyciam 发表于 2016-11-18 11:59
[48477312, [78, 78, 96, 83]] --time: 0.0010933442278124534

你算错了

lyciam · 发表于 2016-11-22 17:12:37

import time
t = time.clock()
def product(args):
    result = 1
    for n in args:
        result *= n
    return result

def euler11():
    """
    在以下20X20的网格中，四个处于同一对角线上的相邻数字用红色标了出来：
    """
    gridnum="""
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
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 08 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 09 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 09 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 08 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 08 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
    """
    """
    这个四个数字的乘积是：26 X 63 X 78 X 14 = 1788696
    在这个20 X 20 网格中，处于任何方向上（上下左右或者对角线）的四
    个相邻数字的乘积的最大值是多少？
    """
    gridlist = [ [int(m) for m in row] for row in [ n.split() for n in gridnum.strip().split('\n') ]  ]
    result = {'max' : 0}
    for x in range(17):
        for y in range(3,17):
            left = product( [ gridlist[x][y-n] for n in range(4) ] )
            right = product( [ gridlist[x][y+n] for n in range(4) ] )
            down = product( [ gridlist[x+n][y] for n in range(4) ] )
            downleft = product( [ gridlist[x+n][y-n] for n in range(4) ] )
            downright = product( [ gridlist[x+n][y+n] for n in range(4) ] )
            temp = {'left' : left, 'right' : right, 'down' : down, 'downleft' : downleft, 'downright' : downright}
            for key in temp:
                if result['max'] < temp[key]:
                    result['max'] = temp[key]
                    result['position(x,y)'] ='{}-->{}'.format( (x,y), key )   
    return result
print(euler11(), '--time: ', time.clock()-t)

{'position(x,y)': '(12, 6)-->downleft', 'max': 70600674} --time: 0.005414622617168334

@jerryxjr1220 谢谢指出我的错误。之前确实看错题啦，现在重新改写一遍，答案和你的一样

lyciam · 发表于 2016-11-22 17:13:42

jerryxjr1220 发表于 2016-11-19 07:42
你算错了

谢谢指出我的错误。现在我重新改写了一遍，答案是和你一样的！

芒果加黄桃 · 发表于 2017-1-9 15:34:33

# encoding:utf-8

numbers = [
['08', '02', '22', '97', '38', '15', '00', '40', '00', '75', '04', '05', '07', '78', '52', '12', '50', '77', '91', '08'],
['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', '08', '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', '09', '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', '09', '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', '08', '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', '08', '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']
]

# 字符串转为整数
for line in numbers:
    for num in line:
        line[line.index(num)] = int(num)  
        
max_num = 0
i_h, j_s = 0, 0

# 横排最大
for i in range(0, 20):
    for j in range(0, 17):
        temp = numbers[i][j] * numbers[i][j + 1] * numbers[i][j + 2] * numbers[i][j + 3]
        if temp > max_num:
            max_num = temp
            i_h, j_s = i, j

# 竖排
for i in range(0, 17):
    for j in range(0, 20):
        temp = numbers[i][j] * numbers[i + 1][j ] * numbers[i + 2][j ] * numbers[i + 3][j ]
        if temp > max_num:
            max_num = temp
            i_h, j_s = i, j


# 左斜
for i in range(0, 17):
    for j in range(0, 17):
        temp = numbers[i][j] * numbers[i + 1][j + 1 ] * numbers[i + 2][j + 2 ] * numbers[i + 3][j + 3 ]
        if  temp > max_num:
            max_num = temp
            i_h, j_s = i, j

# 左斜
for i in range(3, 20):
    for j in range(0, 17):
        temp = numbers[i][j] * numbers[i - 1][j + 1 ] * numbers[i - 2][j + 2 ] * numbers[i - 3][j + 3 ]
        # print(temp)
        if  temp > max_num:
            max_num = temp
            i_h, j_s = i, j
            
print('最大乘积是%d, 坐标为：x = %d, y = %d' % (max_num, i_h, j_s))

渡风 · 发表于 2017-1-14 00:03:26

此代码使用matlab编程
Problem11所用时间为0.002456秒
Problem11的答案为70600674

%题目11：在20×20的网格中同一直线上四个数的最大乘积是多少？
function Output=Problem11(Input)
 tic
if nargin==0
    Input=[08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08;
           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 08 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 09 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 09 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 08 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 08 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];
%end
Rank=zeros(21,21-4);
Row=zeros(21-4,21);
Diago_Right=zeros(21-4,21-4);
Diago_Left=zeros(21-4,21-4);
for ii=1:20
    for jj=1:21-4
        Rank(ii,jj)=prod([Input(ii,jj),Input(ii,jj+1),Input(ii,jj+2),Input(ii,jj+3)]);
    end
end
for jj=1:21-4
    for ii=1:20
        Row(jj,ii)=prod([Input(jj,ii),Input(jj+1,ii),Input(jj+2,ii),Input(jj+3,ii)]);
    end
end
for xx=1:21-4
    for yy=1:21-4
        Diago_Right(xx,yy)=prod([Input(xx,yy),Input(xx+1,yy+1),Input(xx+2,yy+2),Input(xx+3,yy+3)]);
    end
end
for pp=1:21-4
    for qq=4:20
        Diago_Left(pp,qq-3)=prod([Input(pp,qq),Input(pp+1,qq-1),Input(pp+2,qq-2),Input(pp+3,qq-3)]);
    end
end
Max1=max(max(Rank));
Max2=max(max(Row));
Max3=max(max(Diago_Right));
Max4=max(max(Diago_Left));
Output=max(Max1,max(Max2,max(Max3,Max4)));
toc
disp('此代码使用matlab编程')
disp(['Problem11所用时间为',num2str(toc),'秒'])
disp(['Problem11的答案为',num2str(Output)])
end

FlySelf · 发表于 2017-2-3 12:07:09

import time

def max_product(number=4):
    '求在20×20的网格中同一直线上四个数的最大乘积'
    source = '''
    08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
    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 08 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 09 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 09 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 08 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 08 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
    '''
    list_source = source.split()
    for i in range(0, len(list_source)):
        list_source[i] = int(list_source[i])
    list_matrix = []
    for i in range(0, 20):
        list_matrix.append(list_source[(i * 20):((i + 1) * 20)])

    result = 1
    value = []
    coord = []
    #横纵方向的最大乘积
    for i in range(0, 20):
        for j in range(0, 21 - number):
            result_horizontal = 1
            result_vertical = 1
            result_horizontal = list_matrix[i][j] * list_matrix[i][j + 1] * list_matrix[i][j + 2] * list_matrix[i][j + 3]
            result_vertical = list_matrix[j][i] * list_matrix[j + 1][i] * list_matrix[j + 2][i] * list_matrix[j + 3][i]
            if result_horizontal > result and result_horizontal > result_vertical:
                result = result_horizontal
                coord = [i, j]
                value = [list_matrix[i][j], list_matrix[i][j + 1], list_matrix[i][j + 2], list_matrix[i][j + 3]]
            elif result_vertical > result and result_vertical > result_horizontal:
                result = result_vertical
                coord = [j, i]
                value = [list_matrix[j][i], list_matrix[j + 1][i], list_matrix[j + 2][i], list_matrix[j + 3][i]]
    #对角线方向的最大乘积
    for i in range(0, 21 - number):
        for j in range(0, 21 - number - i):
            result_up = 1
            result_down = 1
            result_up_right = 1
            result_down_right = 1
            result_up = list_matrix[j][i + j] * list_matrix[j + 1][i + j + 1] * \
            list_matrix[j + 2][i + j + 2] * list_matrix[j + 3][i + j + 3]

            result_down = list_matrix[i + j][j] * list_matrix[i + j + 1][j + 1] * \
            list_matrix[i + j + 2][j + 2] * list_matrix[i + j + 3][j + 3]

            result_up_right = list_matrix[j][19 - i - j] * list_matrix[j + 1][19 - i - j - 1] * \
            list_matrix[j + 2][19 - i - j - 2] * list_matrix[j + 3][19 - i - j - 3]

            result_down_right = list_matrix[i + j][19 - j] * list_matrix[i + j + 1][19 - j - 1] * \
            list_matrix[i + j + 2][19 - j - 2] * list_matrix[i + j + 3][19 - j - 3]

            if result_up > result and result_up > result_down:
                result = result_up
                coord = [j, i + j]
                value = [list_matrix[j][i + j], list_matrix[j + 1][i + j + 1], \
                list_matrix[j + 2][i + j + 2], list_matrix[j + 3][i + j + 3]]
            elif result_down > result and result_down > result_up:
                result = result_down
                coord = [i + j, j]
                value = [list_matrix[i + j][j], list_matrix[i + j + 1][j + 1], \
                list_matrix[i + j + 2][j + 2], list_matrix[i + j + 3][j + 3]]

            if result_up_right > result and result_up_right > result_down_right:
                result = result_up_right
                coord = [j, 19 - i - j]
                value = [list_matrix[j][19 - i - j], list_matrix[j + 1][19 - i - j - 1], \
                list_matrix[j + 2][19 - i - j - 2], list_matrix[j + 3][19 - i - j - 3]]
            elif result_down_right > result and result_down_right > result_up_right:
                result = result_down_right
                coord = [i + j, 19 - j]
                value = [list_matrix[i + j][19 - j], list_matrix[i + j + 1][19 - j - 1], \
                list_matrix[i + j + 2][19 - j - 2], list_matrix[i + j + 3][19 - j - 3]]

    return [value, coord, result]

start = time.clock()
print(max_product())
end = time.clock()
print('程序执行了%fs。' %(end - start))

执行结果：
[[89, 94, 97, 87], [12, 6], 70600674]
程序执行了0.001152s。

marmot · 发表于 2017-2-22 16:25:48

本帖最后由 marmot 于 2017-2-22 16:40 编辑

date = """08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
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 08 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 09 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 09 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 08 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 08 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"""


date_nospac = list(date.split())     # 列表化，去空格

date_int = []
for i in date_nospac :       #换int
    date_int.append(int(i))

list = []
for j in range(20):       # 分片装入list
    list.append(date_int[j * 20 :(j + 1) * 20])

# n m 坐标定位
num = 0
for m in  range(16):
    for n in range(16):
        x1 = list[m][n] * list[m + 1][n + 1] * list[m + 2][n + 2] * list[m + 3][n + 3]  # 右斜
        x2 = list[m][n + 3] * list[m + 1][n + 2] * list[m + 2][n + 1] * list[m + 3][n]  # 左斜
        if x1 > num :
            num = x1
        if x2 > num:
            num = x2
for q in range(16):
    x3 = list[q][q] * list[q][q + 1] * list[q][q + 2] * list[q][q + 3]      # 横
    x4 = list[q][q] * list[q + 1][q] * list[q + 2][q] * list[q + 3][q]      # 竖
    if x3 > num:
        num = x1
    if x4 > num:
        num = x2
print("答案是： " + str(num))

JonTargaryen · 发表于 2017-4-1 14:58:52

本帖最后由 JonTargaryen 于 2017-4-1 15:01 编辑

The number is: 70600674

#include <stdio.h>

int row_product(int grid[][20], int result);
int column_product(int grid[][20], int result);
int right_cross_product(int grid[][20], int result);
int left_cross_product(int grid[][20], int result);
int main(void)
{
    int grid[][20] = {
    {8, 2, 22, 97, 38, 15, 0, 40, 0, 75, 4, 5, 7, 78, 52, 12, 50, 77, 91, 8},
    {49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 4, 56, 62, 0},
    {81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 3, 49, 13, 36, 65},
    {52, 70, 95, 23, 4, 60, 11, 42, 69, 24, 68, 56, 1, 32, 56, 71, 37, 2, 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, 3, 45, 2, 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, 2, 62, 12, 20, 95, 63, 94, 39, 63, 8, 40, 91, 66, 49, 94, 21},
    {24, 55, 58, 5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72},
    {21, 36, 23, 9, 75, 0, 76, 44, 20, 45, 35, 14, 0, 61, 33, 97, 34, 31, 33, 95},
    {78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 3, 80, 4, 62, 16, 14, 9, 53, 56, 92},
    {16, 39, 5, 42, 96, 35, 31, 47, 55, 58, 88, 24, 0, 17, 54, 24, 36, 29, 85, 57},
    {86, 56, 0, 48, 35, 71, 89, 7, 5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58},
    {19, 80, 81, 68, 5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 4, 89, 55, 40},
    {4, 52, 8, 83, 97, 35, 99, 16, 7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66},
    {88, 36, 68, 87, 57, 62, 20, 72, 3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69},
    {4, 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, 4, 36, 16},
    {20, 73, 35, 29, 78, 31, 90, 1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 5, 54},
    {1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 1, 89, 19, 67, 48}};

    int result = 0;

    result = row_product(grid, result);
    result = column_product(grid, result);
    result = right_cross_product(grid, result);
    result = left_cross_product(grid, result);

    printf("The number is: %d\n", result);

    return 0;
}

int row_product(int grid[][20], int result)
{
    int i, j;
    int temp;

    for(i = 0; i < 20; i++)
    {
        for(j = 0; j < 17; j++)
        {
            temp = grid[i][j] * grid[i][j+1] * grid[i][j+2] * grid[i][j+3];
            result = result > temp ? result : temp;
        }
    }

    return result;
}

int column_product(int grid[][20], int result)
{
    int i, j;
    int temp;

    for(i = 0; i < 17; i++)
    {
        for(j = 0; j < 20; j++)
        {
            temp = grid[i][j] * grid[i+1][j] * grid[i+2][j] * grid[i+3][j];
            result = result > temp ? result : temp;
        }
    }

    return result;
}

int right_cross_product(int grid[][20], int result)
{
    int i, j;
    int temp;

    for(i = 0; i < 17; i++)
    {
        for(j = 0; j < 17; j++)
        {
            temp = grid[i][j] * grid[i+1][j+1] * grid[i+2][j+2] * grid[i+3][j+3];
            result = result > temp ? result : temp;
        }
    }

    return result;
}

int left_cross_product(int grid[][20], int result)
{
    int i, j;
    int temp;

    for(i = 3; i < 20; i++)
    {
        for(j = 0; j < 17; j++)
        {
            temp = grid[i][j] * grid[i-1][j+1] * grid[i-2][j+2] * grid[i-3][j+3];
            result = result > temp ? result : temp;
        }
    }

    return result;
}

JonTargaryen · 发表于 2017-4-1 15:32:39

def row_product(grid, result):
    for i in range(20):
        for j in range(17):
            temp = grid[i][j] * grid[i][j+1] * grid[i][j+2] * grid[i][j+3]
            result = max(result, temp)

    return result

def column_product(grid, result):
    for i in range(17):
        for j in range(20):
            temp = grid[i][j] * grid[i+1][j] * grid[i+2][j] * grid[i+3][j]
            result = max(result, temp)

    return result

def right_cross_product(grid, result):
    for i in range(17):
        for j in range(17):
            temp = grid[i][j] * grid[i+1][j+1] * grid[i+2][j+2] * grid[i+3][j+3]
            result = max(result, temp)

    return result

def left_cross_product(grid, result):
    for i in range(3, 20):
        for j in range(17):
            temp = grid[i][j] * grid[i-1][j+1] * grid[i-2][j+2] * grid[i-3][j+3]
            result = max(result, temp)

    return result

def main():
    grid  = [\
    [ 8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8],\
    [49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0],\
    [81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65],\
    [52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 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,  3, 45,  2, 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,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21],\
    [24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72],\
    [21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95],\
    [78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92],\
    [16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57],\
    [86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58],\
    [19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40],\
    [ 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66],\
    [88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69],\
    [ 4, 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,  4, 36, 16],\
    [20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54],\
    [ 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48]]

    result = 0
    result = row_product(grid, result)
    result = column_product(grid, result)
    result = right_cross_product(grid, result)
    result = left_cross_product(grid, result)

    print(result)

if __name__ == "__main__":
    main()

天之南 · 发表于 2017-5-1 14:33:26

本帖最后由天之南于 2017-5-1 14:36 编辑

#include <stdio.h>

int main()
{
        int num[20][20] = 
        {    
                8,  2, 22, 97, 38, 15,  0, 40,  0, 75,  4,  5,  7, 78, 52, 12, 50, 77, 91,  8,
                49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48,  4, 56, 62,  0,
                81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30,  3, 49, 13, 36, 65,
                52, 70, 95, 23,  4, 60, 11, 42, 69, 24, 68, 56,  1, 32, 56, 71, 37,  2, 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,  3, 45,  2, 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,  2, 62, 12, 20, 95, 63, 94, 39, 63,  8, 40, 91, 66, 49, 94, 21,
                24, 55, 58,  5, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72,
                21, 36, 23,  9, 75,  0, 76, 44, 20, 45, 35, 14,  0, 61, 33, 97, 34, 31, 33, 95,
                78, 17, 53, 28, 22, 75, 31, 67, 15, 94,  3, 80,  4, 62, 16, 14,  9, 53, 56, 92,
                16, 39,  5, 42, 96, 35, 31, 47, 55, 58, 88, 24,  0, 17, 54, 24, 36, 29, 85, 57,
                86, 56,  0, 48, 35, 71, 89,  7,  5, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58,
                19, 80, 81, 68,  5, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77,  4, 89, 55, 40,
                 4, 52,  8, 83, 97, 35, 99, 16,  7, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66,
                88, 36, 68, 87, 57, 62, 20, 72,  3, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69,
                 4, 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,  4, 36, 16,
                20, 73, 35, 29, 78, 31, 90,  1, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57,  5, 54,
                 1, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52,  1, 89, 19, 67, 48};
        int max = 0;
        for (int i = 0; i < 20; i++)
        {
                for (int j = 0; j < 20; j++)
                {
                        if (i + 3 < 20) {
                                int temp = num[i][j] * num[i + 1][j] * num[i + 2][j] * num[i + 3][j];
                                max = max > temp ? max : temp;
                        }
                        if (j + 3 < 20)
                        {
                                int temp = num[i][j] * num[i][j + 1] * num[i][j + 2] * num[i][j + 3];
                                max = max > temp ? max : temp;
                        }
                        if (i + 3 < 20 && j + 3 < 20)
                        {
                                int temp = num[i][j]*num[i+1][j+1]*num[i+2][j+2]*num[i+3][j+3];
                                max = max > temp ? max : temp;
                        }
                        if (i + 3 < 20 && j > 3)
                        {
                                int temp = num[i][j] * num[i+1][j-1]*num[i+2][j-2] * num[i+3][j-3];
                                max = max > temp ? max : temp;
                        }
                }
        }
        
        printf("%d\n",max);
        return 0;
}

70600674

幻世伽蓝 · 发表于 2017-7-9 14:40:12

#include <stdio.h>

int n[20][20]={ { 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91, 8},
                {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62, 0},
                {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65},
                {52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,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, 3,45, 2,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, 2,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21},
                {24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72},
                {21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95},
                {78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92},
                {16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57},
                {86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58},
                {19,80,81,68, 5,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40},
                { 4,52, 8,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66},
                {88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69},
                { 4,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, 4,36,16},
                {20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54},
                { 1,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48}};


int main()
{
    int i,j,max=0,a=0,b=0,c=0,d=0,e=0;
    for(i=0;i<20;i++)
    {
        for(j=0;j<17;j++)
        {
            if(i>3&&i<17)
            {
                a=n[i][j]*n[i+1][j]*n[i+2][j]*n[i+3][j];
                b=n[i][j]*n[i][j+1]*n[i][j+2]*n[i][j+3];
                c=n[i][j]*n[i+1][j+1]*n[i+2][j+2]*n[i+3][j+3];
                d=n[i][j]*n[i-1][j+1]*n[i-2][j+2]*n[i-3][j+3];
                e=(a>b?a:b)>c?(a>b?a:b):c;
                if(d>e)
                    e=d;
                if(e>max)
                {
                    max=e;
                }
            }
            else if(i<=3)
            {
                a=n[i][j]*n[i+1][j]*n[i+2][j]*n[i+3][j];
                b=n[i][j]*n[i][j+1]*n[i][j+2]*n[i][j+3];
                c=n[i][j]*n[i+1][j+1]*n[i+2][j+2]*n[i+3][j+3];
                e=(a>b?a:b)>c?(a>b?a:b):c;
                if(e>max)
                {
                    max=e;
                }
            }
            else
            {
                b=n[i][j]*n[i][j+1]*n[i][j+2]*n[i][j+3];
                d=n[i][j]*n[i-1][j+1]*n[i-2][j+2]*n[i-3][j+3];
                if(b>max)
                {
                    max=b;
                }
                if(d>max)
                {
                    max=d;
                }
            }
        }
    }

    printf("%d\n",max);
    return 0;
}

py阿碗 · 发表于 2017-7-14 18:19:24

num = '''08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
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 08 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 09 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 09 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 08 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 08 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'''
num1 = num.replace('/n',' ')
#每行20个数=40+20=60个字符  总共60*20-1=1199
#行line 列column 斜oblique
L = []
for x in range(0,20):
    for i in range(x*60+0,x*60+59,3):
        a = int(num1[i:i+2])
        L.append(a)
#到这里把所有数放入list：L中

L1 = []

line = 0
for x1 in range(0,20):
    for i1 in range(x1*20+0,x1*20+17):
        line = L[i1]*L[i1+1]*L[i1+2]*L[i1+3]
        L1.append(line)

column = 0
for i2 in range(0,340):#不是341从0开始计数
    column = L[i2]*L[i2+20]*L[i2+40]*L[i2+60]
    L1.append(column)

oblique1 = 0
for x3 in range(0,17):
    for i3 in range(x3*20+0,x3*20+17):
        oblique1 = L[i3]*L[i3+21]*L[i3+42]*L[i3+63]
        L1.append(oblique1)

oblique2 = 0
for x4 in range(0,17):
    for i4 in range(x4*20+3,x4*20+21):
        oblique2 = L[i4]*L[i4+19]*L[i4+38]*L[i4+57]
        L1.append(oblique2)

print(max(L1))

账号		自动登录	找回密码
密码			立即注册

题目11：在20×20的网格中同一直线上四个数的最大乘积是多少？

马上注册，结交更多好友，享用更多功能^_^

评分