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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第十一题：相邻元素乘积最大
北京石油化工学院2026年研究生招生接收调剂公告
111/2返回列表12下一页
查看: 2049  |  回复: 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下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 320分人工智能调剂 +8 振—TZ 2026-04-03 8/400 2026-04-05 22:33 by 范式思维
[考研] 材料0856 英一数二 323 求调剂 +14 袁sy 2026-04-01 14/700 2026-04-05 18:18 by cql1109
[考研] 0703化学321分求调剂 +17 三dd. 2026-03-30 18/900 2026-04-05 18:07 by 蓝云思雨
[考研] 085500机械专硕初试288求调剂 +3 GZJguo666- 2026-04-05 3/150 2026-04-05 18:06 by jkddd
[考研] 电子信息调剂交叉学科有推荐吗 +6 jhtfeybgj 2026-04-01 9/450 2026-04-05 11:13 by 猪会飞
[考研] 083200 333求调剂 +3 十二！！ 2026-04-04 3/150 2026-04-05 08:28 by barlinike
[考研] 288环境专硕,求调材料方向 +13 lllllos 2026-04-04 14/700 2026-04-04 23:34 by lqwchd
[考研] 一志愿郑州大学材料与化工085600，求调剂 +24 吃的不少 2026-04-02 24/1200 2026-04-04 23:20 by 永字号
[考研] 。 +5 雾与海 2026-04-02 6/300 2026-04-04 19:53 by 蓝云思雨
[考研] 342求调剂 +3 Liang7111 2026-04-04 5/250 2026-04-04 19:47 by dongzh2009
[考研] 265求调剂 +20 梁梁校校 2026-04-01 21/1050 2026-04-04 00:38 by userper
[考研] 317分 一志愿江南大学 化学工程学硕 求调剂 +6 YinTai 2026-04-03 6/300 2026-04-03 22:30 by 无际的草原
[考研] 材料科学与工程339求调剂 +12 hyz0119 2026-03-31 13/650 2026-04-03 18:33 by ls刘帅
[考研] 英一数一408，总分284，二战真诚求调剂 +13 12.27 2026-03-30 15/750 2026-04-03 14:41 by 氮气气气
[考研] 调剂 +7 祉岷. 2026-04-02 7/350 2026-04-03 09:11 by 花呗还欠600
[考研] 一志愿山东大学，085600，344 +7 魏子per 2026-04-02 8/400 2026-04-02 21:12 by 百灵童888
[考研] 070300化学279求调剂 +15 哈哈哈^_^ 2026-03-31 17/850 2026-04-01 21:37 by 给你你注意休息
[考研] 0817化工学硕调剂 +11 努力上岸中！ 2026-03-31 11/550 2026-04-01 20:30 by 赖春艳
[考研] 求调剂 +4 DADA怪 2026-03-31 4/200 2026-04-01 14:30 by ZXlzxl0425
[考研] 生物考研337分求调剂 +4 cgxin 2026-03-30 6/300 2026-03-31 14:18 by 记事本2026
信息提示
关闭
请填处理意见
关闭