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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第十一题：相邻元素乘积最大
北京石油化工学院2026年研究生招生接收调剂公告
111/2返回列表12下一页
查看: 2050  |  回复: 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下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 求助071001调剂！！！ +3 黄守松 2026-04-05 4/200 2026-04-05 21:01 by barlinike
[考研] 考研调剂生寻找导师 +3 顾瞻考研啊 2026-04-05 3/150 2026-04-05 18:18 by 啵啵啵0119
[考研] 298求调剂 +3 manman511 2026-04-05 3/150 2026-04-05 18:09 by kk112233
[考研] 调剂 +5 好好读书。 2026-04-01 5/250 2026-04-05 17:54 by liucky
[考研] 295求调剂 +8 FZAC123 2026-04-03 8/400 2026-04-05 17:46 by 蓝云思雨
[考研] 284求调剂 +7 徐同学_001 2026-04-04 13/650 2026-04-05 17:19 by yulian1987
[考研] 306分材料与化工求调剂 +7 黎吧啦啦你很有� 2026-04-03 7/350 2026-04-05 17:18 by Hdyxbekcb
[考研] 一志愿江南大学085501机械工程专硕326分，本科佳木斯大学 +5 顾若浮生 2026-04-03 9/450 2026-04-05 09:57 by 1753564080
[考研] 085600，321分求调剂 +10 大馋小子 2026-04-04 11/550 2026-04-05 08:25 by 544594351
[考研] 材料求调剂 +10 呢呢妮妮 2026-04-01 10/500 2026-04-04 23:12 by 无际的草原
[考研] 环境285分，过六级，求调剂 +10 xhr12 2026-04-02 10/500 2026-04-04 21:53 by bn53987
[考研] 085400电子信息319求调剂（接受跨专业调剂） +5 星星不眨眼喽 2026-04-03 6/300 2026-04-04 21:50 by hemengdong
[考研] 学硕机械工程303求调剂 +6 无名所以叫吴明 2026-03-30 7/350 2026-04-03 16:48 by asdfzly
[考研] 282求调剂 不挑专业 求收留 +7 Yam. 2026-03-30 8/400 2026-04-03 14:12 by zhangdingwa
[考研] 0705理学294求调剂 +3 成果成果cg5 2026-04-03 3/150 2026-04-03 14:04 by simons1972
[考研] 一志愿中国科学院大学265求调剂 +9 恬淡ye 2026-03-31 10/500 2026-04-03 11:10 by txp1986
[考研] 0703化学 +7 goldtt 2026-04-02 9/450 2026-04-03 09:36 by 蓝云思雨
[考研] 求调剂！生物与医药专硕 +4 逆转陆先生 2026-04-01 5/250 2026-04-03 08:33 by Jaylen.
[考研] 一志愿北京科技，085601总分305求调剂 +9 半生瓜！ 2026-04-01 11/550 2026-04-02 08:28 by Wang200018
[考研] 0817化工学硕调剂 +11 努力上岸中！ 2026-03-31 11/550 2026-04-01 20:30 by 赖春艳
信息提示
关闭
请填处理意见
关闭