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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第十八题：三角阵上最大的和
52/1返回列表
查看: 1839  |  回复: 12
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

holmescn

金虫 (正式写手)

[交流] Euler 工程 第十八题：三角阵上最大的和 已有4人参与

已知从下面这个三角阵的顶端到底端，最大的和是 3 + 7 + 4 + 9 ＝ 23

      3
    7  4
  2  4  6
8  5  9  3

那么下面这个三角阵，从顶到底的最大的和是多少？

                            75
                          95 64
                        17 47 82
                      18 35 87 10
                    20 04 82 47 65
                  19 01 23 75 03 34
                88 02 77 73 07 63 67
              99 65 04 28 06 16 70 92
            41 41 26 56 83 40 80 70 33
          41 48 72 33 47 32 37 16 94 29
        53 71 44 65 25 43 91 52 97 51 14
      70 11 33 28 77 73 17 78 39 68 17 57
    91 71 52 38 17 14 91 43 58 50 27 29 48
  63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

哈哈，睡觉先
回复此楼

» 猜你喜欢
1楼 2011-05-30 23:57:02
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★
余泽成(金币+1): 鼓励交流！ 2011-06-04 19:18:23
引用回帖:
Originally posted by huycwork at 2011-06-02 17:18:46:
广度优先搜索的性能很不错的，顶点V,边E的有向图，遍历的复杂度只有O(|V|+|E|)，大体属于线性时间的复杂度。

有向图，我地不太懂
赞一下(1人) 回复此楼
12楼2011-06-02 17:53:55
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 13 个回答

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★ ★ ★
微尘、梦想(金币+5): 谢谢参与！ 2011-05-31 20:21:27
倒推回去就行了,这个题挺简单
CODE:
%% Find the maximum total from top to bottom of the triangle below:
function result = euler18()
tic;
s = {[ 75 ], [ 95 64 ], [ 17 47 82 ], [ 18 35 87 10 ], [ 20 04 82 47 65 ], [ 19 01 23 75 03 34 ], [ 88 02 77 73 07 63 67 ], [ 99 65 04 28 06 16 70 92 ], [ 41 41 26 56 83 40 80 70 33 ], [ 41 48 72 33 47 32 37 16 94 29 ], [ 53 71 44 65 25 43 91 52 97 51 14 ], [ 70 11 33 28 77 73 17 78 39 68 17 57 ], [ 91 71 52 38 17 14 91 43 58 50 27 29 48 ], [ 63 66 04 68 89 53 67 30 73 16 69 87 40 31 ], [ 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23 ]};
result = maxRoute(s);
toc;
end

%% compute max route in triangle
% called by 18 and 67
function result = maxRoute(s)
m = length(s);
for i=m-1:-1:1 % 从倒数第二层倒退
    for j=1:length(s{i}) % 每个元素加上下一层邻接2个数中最大的
        s{i}(j) = s{i}(j)+max(s{i+1}(j),s{i+1}(j+1));
    end
end
result = s{1}(1);
end

时间+结果
CODE:
% Elapsed time is 0.002799 seconds.
% ans =
%         1074

[ Last edited by libralibra on 2011-6-2 at 15:26 ]
赞一下(1人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
2楼2011-05-31 02:05:24
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★ ★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+5): 谢谢参与！ 2011-05-31 20:21:56
这题要动态规划下，空间换时间，C++实现如下：
CODE:
#include

enum { Row = 15, Col = 15 };

int buf[] = {
        75,
        95, 64,
        17, 47, 82,
        18, 35, 87, 10,
        20, 04, 82, 47, 65,
        19, 01, 23, 75, 03, 34,
        88, 02, 77, 73, 07, 63, 67,
        99, 65, 04, 28, 06, 16, 70, 92,
        41, 41, 26, 56, 83, 40, 80, 70, 33,
        41, 48, 72, 33, 47, 32, 37, 16, 94, 29,
        53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14,
        70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57,
        91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48,
        63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31,
        04, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23,
};

int buf2[sizeof(buf)];

int &at(int *buf, int i, int j){
        --i;
        return buf[j+(1+i)*i/2];
}

size_t eular18(){
        at(buf2, 1, 0) = at(buf, 1, 0);
        for(int i = 2; i <= Row; ++i){
                at(buf2, i, 0) = at(buf2, i-1, 0) + at(buf, i, 0);
                for(int j = 1; j < i-1; ++j){
                        at(buf2, i, j) = std::max(at(buf, i, j)+at(buf2, i-1, j-1), at(buf, i, j)+at(buf2, i-1, j));
                }
                at(buf2, i, i-1) = at(buf2, i-1, i-2) + at(buf, i, i-1);
        }
        int max = 0;
        for(int i = 0; i < Col; ++i){
                max = std::max(max, at(buf2, Row, i));
        }
        return max;
}
int main(){
        std::cout<         return 0;
}
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
3楼2011-05-31 12:01:35
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

wangww2011

木虫 (著名写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想: 这样没有题目，后面来的人是看不懂的啊，还是按题做吧！ 2011-05-31 20:24:04
那啥 这题确实简单 直接做67题吧
67题和18题一样，只不过数据多一些而已，解法是一样的
数据见附件
CODE:
7273
elapsed time=0.000000 seconds.

代码
CODE:
#include
#include
#include

#define TIMERSTART clock_t start_time,stop_time;double elapsed_time;start_time = clock();
#define TIMERSTOP stop_time = clock();elapsed_time=(double)(stop_time-start_time)/CLOCKS_PER_SEC;printf("elapsed time=%f seconds.\n",elapsed_time);


static const int n=100;

int euler67(){
  int i,j,sum=0;
  int data[n][n];
  int path[n];
  
  FILE *fp=fopen("triangle.txt", "r");
  if(fp == 0) return -1;

    for(i = 0; i < n; i++) {
       for(j = 0; j          fscanf(fp, "%d", &data[i][j]);
        }
    }
    fclose(fp);

   for(i = n-1; i > 0; i--) {
      for(j = 0; j         if(data[i][j]>data[i][j+1]) data[i-1][j]+=data[i][j];
        else data[i-1][j]+=data[i][j+1];
      }
   }
   
  return data[0][0];
}


int main(void){
int i;

TIMERSTART;

printf("%d\n",euler67());
  
TIMERSTOP;

  return 0;
}

[ Last edited by wangww2011 on 2011-5-31 at 20:38 ]
赞一下(2人) 回复此楼
4楼2011-05-31 19:06:37
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 13 个回答
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[找工作] 售SCI一区T0P文章，我:8.O.55.1.O54,科目全,可伽急 +3 cqwQDCxMcL3I 2026-09-29 4/200 2026-09-30 16:33 by Z9YWQ5EAO3qp
[公派出国] 售SCI一区文章，我:8O5.5.1.O5.4,科目全,可伽急 +3 cqwQDCxMcL3I 2026-09-29 6/300 2026-09-30 16:26 by Z9YWQ5EAO3qp
[考研] 售SCI一区文章，我:8O5.5.1.O5.4,科目全,可伽急 +3 cqwQDCxMcL3I 2026-09-29 6/300 2026-09-30 16:14 by Z9YWQ5EAO3qp
[有机交流] 同一个分子，一条来自文献，一条来自AI——不告诉你答案，你会选哪条？ +4 tianxiaoxian 2026-09-28 7/350 2026-09-30 08:34 by 88817753
[博后之家] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +4 IDs3scOF0tjC 2026-09-28 4/200 2026-09-29 19:27 by cqwQDCxMcL3I
[找工作] 售SCI一区T0P文章，我:8.O.55.1.O54,科目全,可伽急 +4 ZYXdhzDAy9ZX 2026-09-28 4/200 2026-09-29 16:54 by yCO1Ll7aHtsw
[考博] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +3 tqUTOxClQUMF 2026-09-28 3/150 2026-09-29 15:46 by etmYJ6d2rquH
[考博] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +6 GDBe8tDZqE8z 2026-09-28 6/300 2026-09-29 14:41 by etmYJ6d2rquH
[硕博家园] 售SCI一区T0P文章，我:8O.55.1.O.5.4,科目齐全,可+急 +3 GDBe8tDZqE8z 2026-09-28 3/150 2026-09-29 14:30 by etmYJ6d2rquH
[博后之家] 售SCI一区T0P文章，我:8.O.55.1.O54,科目全,可伽急 +6 IDs3scOF0tjC 2026-09-28 7/350 2026-09-29 14:07 by etmYJ6d2rquH
[博后之家] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +3 IDs3scOF0tjC 2026-09-28 3/150 2026-09-29 13:56 by etmYJ6d2rquH
[公派出国] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +4 IDs3scOF0tjC 2026-09-28 5/250 2026-09-29 13:50 by etmYJ6d2rquH
[考研] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +3 tqUTOxClQUMF 2026-09-28 3/150 2026-09-29 09:59 by JzYBbHIXWSrW
[教师之家] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +4 GDBe8tDZqE8z 2026-09-28 4/200 2026-09-29 09:49 by JzYBbHIXWSrW
[考研] 售SCI一区文章，我:8.O.551.O.5.4,科目全,可伽急 +3 ZYXdhzDAy9ZX 2026-09-28 3/150 2026-09-29 06:42 by ZvyPK8n6Nfki
[硕博家园] 售SCI一区T0P文章，我:8.O.55.1.O.54,科目齐全,可+急 +3 tqUTOxClQUMF 2026-09-28 3/150 2026-09-28 23:46 by b8fCuTHqckEt
[考研] 售SCI一区文章，我:8.O.55.1.O.54,科目齐全,可伽急 +3 GDBe8tDZqE8z 2026-09-28 3/150 2026-09-28 23:12 by b8fCuTHqckEt
[找工作] 售SCI文章，我:8O.5.5.1O.54,科目全,可十急 +3 IDs3scOF0tjC 2026-09-28 5/250 2026-09-28 22:32 by ez6fGg9abYaj
[论文投稿] 售SCI文章，我:8O5.5.1.O.54,科目齐全,可+急 +3 CfXuS1rDhLYN 2026-09-28 3/150 2026-09-28 19:08 by 9lS3ad5oOymn
[考研] 售一区SCI文章T0P，我:8O.551.O54,科目全,可十急 +3 IDs3scOF0tjC 2026-09-28 4/200 2026-09-28 18:51 by 9lS3ad5oOymn
信息提示
关闭
请填处理意见
关闭