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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第十一题：相邻元素乘积最大
111/2返回列表12下一页
查看: 2423  |  回复: 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下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[硕博家园] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +3 0XLacIJUOj8D 2026-08-24 8/400 2026-08-25 05:12 by BZKMTicpDhFj
[考博] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 0XLacIJUOj8D 2026-08-24 3/150 2026-08-25 01:47 by BZKMTicpDhFj
[基金申请] 明天应该可查了！？ +5 chengyan1220 2026-08-23 5/250 2026-08-24 23:28 by 我4大白菜
[基金申请] 没有任何消息-是不是就凉了 +7 图啦图啦 2026-08-24 8/400 2026-08-24 22:00 by maomao_da
[论文投稿] 售SCI-T0P文章，我:8O.5.5.1.O.54,科目齐全,可+急 +3 0XLacIJUOj8D 2026-08-24 3/150 2026-08-24 21:59 by BZKMTicpDhFj
[基金申请] 人气不行了 +10 fansofjerry 2026-08-21 10/500 2026-08-24 21:03 by zhanghaozhu
[基金申请] 我面上完蛋了 +9 且听虎啸 2026-08-20 10/500 2026-08-24 20:08 by 苦寒来香
[基金申请] 能否退出参与的面上项目解除限项 +21 koalala 2026-08-24 24/1200 2026-08-24 19:25 by 家与远方
[基金申请] 2026国自然函评费到账 +17 羊腰板 2026-08-21 19/950 2026-08-24 16:52 by iaeyuan
[基金申请] 估计是周四 +4 archvillain 2026-08-18 4/200 2026-08-24 13:53 by zzuzxg
[基金申请] 范进中举一文的中心思想 +6 炎黄贵胄 2026-08-22 7/350 2026-08-24 11:58 by 6543yes
[基金申请] 朋友圈看到的 +7 wangzilk 2026-08-18 9/450 2026-08-24 10:50 by cmrandy
[基金申请] 让我中一个面上吧！ +13 大萍1987 2026-08-20 16/800 2026-08-24 10:23 by 太傻了
[基金申请] 科研孤儿太难了 +18 我4大白菜 2026-08-20 19/950 2026-08-24 09:47 by 凯恩广盛催化分�
[基金申请] 只有每年这种时候来逛逛小木虫 +24 yaoyewhu2008 2026-08-20 26/1300 2026-08-22 17:43 by kammury
[基金申请] 时间戳今天，20号变了 +5 archvillain 2026-08-20 5/250 2026-08-22 06:12 by hui_daxiao
[基金申请] 时间戳又变了 +13 wuchongjun 2026-08-20 19/950 2026-08-21 17:21 by 紫杉醇
[基金申请] 今天放榜没戏了吧 +9 yuleib84 2026-08-19 11/550 2026-08-21 10:06 by gltch
[基金申请] 基金啊基金 +4 longfie172 2026-08-20 4/200 2026-08-21 08:58 by mark mao
[基金申请] 重要消息，中午系统在维护 +11 yuleib84 2026-08-18 12/600 2026-08-20 11:09 by xskun
信息提示
关闭
请填处理意见
关闭