应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第十一题：相邻元素乘积最大
111/2返回列表12下一页
查看: 2272  |  回复: 10
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 3 个 程序强帖 ，点击这里进行查看

holmescn

金虫 (正式写手)

[交流] Euler 工程 第十一题：相邻元素乘积最大 已有4人参与

In the 20x20 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 26x63x78x14 = 1788696.

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

给了一个20x20的两位数矩阵，其中的红字部分的积为：
26x63x78x14=1788696
那么，任意方向上（上、下、左、右、对角）4个相邻的数的最大乘积是多少？

这个显然比上一个要难啊。
回复此楼

» 猜你喜欢
1楼 2011-05-16 07:53:11
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+1): 鼓励讨论！ 2011-05-16 17:47:24
遍历还是不难的，难的还是找一个十分有效的算法。
看这光景，动态规划也不顶事啊。
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
2楼2011-05-16 15:23:04
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3, 程序强帖+1): 谢谢参与活动！ 2011-05-16 17:47:46
矩阵运算,matlab强项
CODE:
%% What is the greatest product of four adjacent numbers in any direction
% (up, down, left, right, or diagonally) in the 20×20 grid?
function result = euler11()
tic;
s = [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];
[m,n] = size(s);
result = 0;
for i=1:m-3
    for j=1:n-3
        curgrid = s(i:i+3,j:j+3);
        result = max([result,max([max(prod(curgrid,1)), ... % row -
                    max(prod(curgrid,2)), ... % column |
                    prod(diag(curgrid)), ... % diag \
                    prod(diag(imrotate(curgrid,90)))])]); % sub diag /
    end
end
toc;
end

结果,时间
CODE:
% Elapsed time is 0.158644 seconds.
% ans =
%     70600674
赞一下(2人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
3楼2011-05-16 15:59:44
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
Originally posted by libralibra at 2011-05-16 15:59:44:
矩阵运算,matlab强项

[code] %% What is the greatest product of four adjacent numbers in any direction
% (up, down, left, right, or diagonally) in the 20×20 grid?
function result = euler11()
...

打听下，循环里面的max是递归的么？
赞一下(1人) 回复此楼
漩涡的中心有一块空地，空空的。
4楼2011-05-16 16:15:36
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+2): 谢谢参与交流！ 2011-05-17 08:26:37
引用回帖:
Originally posted by huycwork at 2011-05-16 16:15:36:
打听下，循环里面的max是递归的么？

max不是递归的

另外，遍历已经是本题的优良解法了，动态规划并不合适~

如果要增加难度，此题可以改为：

已知一个20x20的整数矩阵，求任意方向上相邻的数（不一定是4个，也不一定是全部，因为值有正有负）的最大的和是多少。

这个时候就适合动态规划什么的了...
赞一下(2人) 回复此楼
5楼2011-05-16 18:12:58
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+2): 谢谢参与交流！ 2011-05-17 08:26:52
引用回帖:
Originally posted by huycwork at 2011-05-16 16:15:36:
打听下，循环里面的max是递归的么？

没递归,max[这里是4个数],[]里面4个数分别是max[行乘积],max[列乘积],对角积和次对角积,类似if判断
赞一下(2人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
6楼2011-05-16 18:29:09
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+2): 谢谢参与交流！ 2011-05-17 08:27:07
引用回帖:
Originally posted by sudo at 2011-05-16 18:12:58:
max不是递归的

另外，遍历已经是本题的优良解法了，动态规划并不合适~

如果要增加难度，此题可以改为：

已知一个20x20的整数矩阵，求任意方向上相邻的数（不一定是4个，也不一定是全部，因为值有正有 ...

也有那么一点可以规划下滴~
动态规划的核心就是划归最优子问题和保存重叠子问题嘛，虽然遍历这个表格没有什么最优子问题，但是重叠子问题还是有的，5个值相乘的情况下，下面就有4个元素的乘数重叠。
只是，没啥用。
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
7楼2011-05-16 20:07:15
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★
余泽成(金币+1): 鼓励交流！ 2011-05-18 17:13:38
引用回帖:
Originally posted by libralibra at 2011-05-16 18:29:09:
没递归,max[这里是4个数],[]里面4个数分别是max[行乘积],max[列乘积],对角积和次对角积,类似if判断

咋看起来蛮像是从后面递归到前面的max，看来直觉不够好
赞一下(1人) 回复此楼
漩涡的中心有一块空地，空空的。
8楼2011-05-16 20:08:26
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★ ★ ★
余泽成(金币+3, 程序强帖+1): 鼓励交流！ 2011-05-18 17:14:09
写了个Fortran版的，好像结果不一样了。不知道怎么回事。主要是对角上的计算，不知道是不是算对了啊！
CODE:
Program euler11
    Implicit None
    Integer, Dimension(20,20) :: Matrix
    Integer :: M1 = 0, M2 = 0, M3 = 0
    Integer :: M = 0
    Integer :: Prod
    Integer :: I, J, K

    Open(100, File="matrix.txt")
    Do I = 1, 20
        Read(100, "(20(I2,X), I2)"), Matrix(I, :)
    EndDo
    Close(100)

    Do I = 1, 20 - 3
        M1 = MaxVal(Product(Matrix(I:I+3, :), 1))
        M2 = MaxVal(Product(Matrix(:, I:I+3), 2))
        M = Max(M1, M2, M)
    EndDo

    Do I = 1, 20 - 3
        Do J = 1, 20 - 3
            Prod = Product((/(Matrix(I+K, J+K), K=0,3)/))
            M3 = Max(M3, Prod)
        EndDo
    EndDo
    Print *, Max(M, M3)

EndProgram euler11

我这儿得51267216

[ Last edited by holmescn on 2011-5-18 at 16:16 ]
赞一下(1人) 回复此楼
9楼2011-05-18 16:14:58
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★ ★ ★
余泽成(金币+3): 鼓励交流！ 2011-05-20 21:05:08
余泽成(程序强帖+1): 2011-05-23 19:05:40
用C写了一个，这样什么都清楚了。
CODE:
#include

int main(int argc, char** argv) {
    int i, j, k;
    int max1 = 0, max2 = 0, max3 = 0, max4 = 0;
    int max;
    int prod;
    int matrix[20][20];
    FILE* fp;

    fp = fopen("matrix.txt", "r");
    for ( i = 0; i < 20; i++) {
        for ( j = 0; j < 20; j++) {
            fscanf(fp, "%d", &matrix[i][j]);
        }
    }

    // 上下
    //
    for ( j = 0 ; j < 20; j++) {
        for ( i = 0; i < 20 - 3; i++) {
            prod = 1;
            for ( k = 0; k < 4; k++) {
                prod *= matrix[i+k][j];
            }
            max1 = max1 < prod ? prod : max1;
        }
    }
    // 左右
    //
    for ( i = 0; i < 20; i++) {
        for ( j = 0 ; j < 20 - 3; j++) {
            prod = 1;
            for ( k = 0; k < 4; k++) {
                prod *= matrix[i][j+k];
            }
            max2 = max2 < prod ? prod : max2;
        }
    }
    // 对角
    for ( i = 0; i < 20 - 3; i++) {
        for ( j = 0 ; j < 20 - 3; j++) {
            // 正对角
            prod = 1;
            for ( k = 0; k < 4; k++) {
                prod *= matrix[i+k][j+k];
            }
            max3 = max3 < prod ? prod : max3;
            // 反对角
            prod = 1;
            for ( k = 0; k < 4; k++) {
                prod *= matrix[i+3-k][j+k];
            }
            max4 = max4 < prod ? prod : max4;
        }
    }

    max = max1 < max2 ? max2 : max1;
    max = max  < max3 ? max3 : max;
    printf("%d\n", max);
    max = max  < max4 ? max4 : max;
    printf("%d\n", max);
    return 0;
}

我得到的两个结果：1. 没有反对角线的是51267216        2. 有反对角线的是70600674
赞一下(2人) 回复此楼
10楼2011-05-20 16:13:36
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
111/2返回列表12下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭