版塊導航: 正在加載中...

登錄注冊

應《網絡安全法》要求，自2017年10月1日起，未進行實名認證將不得使用互聯網跟帖服務。為保障您的帳號能夠正常使用，請盡快對帳號進行手機號驗證，感謝您的理解與支持！

24小時熱門版塊排行榜

北京石油化工學院2026年研究生招生接收調劑公告

返回列表

holmescn

金蟲 (正式寫手)

程序強帖: 37
應助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時
蟲號: 913482
注冊: 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結構

[交流] 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

哈哈，睡覺先

回復此樓

» 猜你喜歡

283分材料與化工求調劑已經有12人回復
349求調劑已經有7人回復
296材料專碩求調劑已經有11人回復
一志愿上海海洋大學083200食品學碩，求調劑，接受其他專業(yè) 已經有7人回復
材料340分調劑已經有8人回復
316求調劑已經有13人回復
321求調劑已經有11人回復
315求調劑已經有6人回復
330分求調劑已經有13人回復
化工調劑303分，過四級已經有9人回復

» 本主題相關價值貼推薦，對您同樣有幫助:

Euler 工程第四十四題已經有4人回復
Euler 工程第四十二題: 三角詞已經有4人回復
Euler 工程第四十一題已經有5人回復
Euler 工程第三十八題已經有9人回復
Euler 工程第三十七題已經有6人回復
Euler 工程第三十六題：已經有18人回復
Euler 工程第三十五題：循環(huán)質數已經有16人回復
Euler 工程第三十二題：pandigital 數已經有3人回復
Euler 工程第三十一題: 換零錢已經有10人回復
Euler 工程第三十題已經有12人回復
Euler 工程第廿九題：有多少不同的項? 已經有30人回復
Euler 工程第廿八題：旋轉矩陣對角線的和已經有6人回復
Euler 工程第廿七題：系數的積已經有15人回復
Euler 工程第廿六題：最長的循環(huán)節(jié) 已經有9人回復
Euler 工程第廿五題：Fibonacci 數列第一個包含1000個數字的項已經有3人回復
Euler 工程第廿四題：全排列的第100萬項已經有19人回復
Euler 工程第廿三題：已經有16人回復
Euler 工程第廿二題: 姓的總分已經有13人回復
Euler 工程第廿題：100! 的各項和已經有5人回復
Euler 工程第十九題：每月第一天是周日的天數已經有4人回復
Euler 工程第十六題：2的1000次方的各項和已經有14人回復
Euler 工程第14題：找最長的數列已經有9人回復
Euler 工程第十一題：相鄰元素乘積最大已經有10人回復
Euler 工程第三題：尋找600851475143的最大質因子已經有18人回復

1樓 2011-05-30 23:57:02

已閱回復此樓關注TA 給TA發(fā)消息送TA紅花 TA的回帖

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

程序強帖: 40
應助: 817 (博后)
金幣: 12914.1
紅花: 64
帖子: 2238
在線: 287.3小時
蟲號: 696514
注冊: 2009-02-05
專業(yè): 計算機軟件

★ ★ ★ ★ ★
微塵、夢想(金幣+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寫程序請發(fā)QQ郵件:790404545@qq.com

2樓2011-05-31 02:05:24

已閱回復此樓關注TA 給TA發(fā)消息送TA紅花 TA的回帖

huycwork

金蟲 (著名寫手)

程序強帖: 22
應助: 0 (幼兒園)
金幣: 953
散金: 663
紅花: 8
沙發(fā): 13
帖子: 1080
在線: 264.1小時
蟲號: 1257243
注冊: 2011-04-06
專業(yè): 金融學

★ ★ ★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
微塵、夢想(金幣+5): 謝謝參與！ 2011-05-31 20:21:56

這題要動態(tài)規(guī)劃下，空間換時間，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發(fā)消息送TA紅花 TA的回帖

wangww2011

木蟲 (著名寫手)

程序強帖: 13
應助: 11 (小學生)
金幣: 4023.1
散金: 2709
紅花: 18
沙發(fā): 1
帖子: 1915
在線: 1537.1小時
蟲號: 772953
注冊: 2009-05-17
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結構

★
小木蟲(金幣+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發(fā)消息送TA紅花 TA的回帖

holmescn

金蟲 (正式寫手)

程序強帖: 37
應助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時
蟲號: 913482
注冊: 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結構

★ ★ ★ ★ ★
微塵、夢想(金幣+5): 謝謝參與！ 2011-06-02 14:29:39

這個題，寫個窮舉還挺麻煩。雖然速度也不慢�？次业膓uick & dirty的Python版

CODE:

# -*- coding: utf-8 -*-

m = [[75],

    [95,64],

    [17,47,82],

    [18,35,87,10],

    [20,4,82,47,65],

    [19,1,23,75,3,34],

    [88,2,77,73,7,63,67],

    [99,65,4,28,6,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,4,68,89,53,67,30,73,16,69,87,40,31],

    [4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]

# 每一行的當前位置

pos = [0] * 15

# 最大值和最大值所在的位置

maxPos = pos

maxSum = 0

while pos[0] == 0:

    s = 0

    for i in range(15):

        s += m[i][pos[i]]

    if maxSum < s:

        maxSum = s

        maxPos = [x for x in pos]

# 查找移動后仍符合相鄰的那個點

    i = 14

    while pos[i] + 1 > pos[i-1] + 1: i -= 1

# 移動這個點

    pos[i] += 1

# 移動這個點下面的點

    for j in range(i, 14):

        pos[j+1] = pos[j]

# 輸出結果

print maxSum

print maxPos

print [m[i][maxPos[i]] for i in range(15)]

本來想用遞歸的，怎么也寫不好，后來放棄了。沒有試用于第67題，所以不知道那個會怎么樣。反正這個題是可以秒殺的。

上一個數格子的題和這個有點類似。不過大家都喜歡用數學方法解了，沒人用數的方法。

又說這個東西，有點像一個二叉樹的遍歷。但又好像不是。想不明白了。

贊一下(1人)

回復此樓

5樓2011-06-02 12:16:51

已閱回復此樓關注TA 給TA發(fā)消息送TA紅花 TA的回帖

匿名

用戶注銷 (小有名氣)

程序強帖: 3
應助: 2 (幼兒園)
金幣: 607.7
散金: 150
紅花: 2
帖子: 195
在線: 104小時
蟲號: 0
注冊: 2010-12-03
專業(yè): 動力學與控制

★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
微塵、夢想(金幣+3): 謝謝參與，建議去維基百科搜一下bbcode代碼，學習一下簡單的美貼…… 2011-06-02 14:31:43

本帖僅樓主可見

贊一下

6樓2011-06-02 12:33:08

已閱申請程序強帖回復此樓編輯查看我的主頁

huycwork

金蟲 (著名寫手)

程序強帖: 22
應助: 0 (幼兒園)
金幣: 953
散金: 663
紅花: 8
沙發(fā): 13
帖子: 1080
在線: 264.1小時
蟲號: 1257243
注冊: 2011-04-06
專業(yè): 金融學

★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
微塵、夢想(金幣+3): 謝謝參與！ 2011-06-02 14:32:00

引用回帖:

Originally posted by holmescn at 2011-06-02 12:16:51:
這個題，寫個窮舉還挺麻煩。雖然速度也不慢�？次业膓uick & dirty的Python版
[code]
# -*- coding: utf-8 -*-
m = [[75],
[95,64],
[17,47,82],
[18,35,87,10],
[20,4,82,47,65],
...

從數據結構看，可以說是二叉樹，但非滿二叉樹，還可以說是有向圖。
不過二叉樹遍歷肯定不成，先序中序后序遍歷是針對當前節(jié)點和子節(jié)點遍歷的，但這個題不涉及當前節(jié)點和子節(jié)點，而是涉及到兄弟節(jié)點及其子節(jié)點，應該視為有向圖的問題，遍歷手法應該是廣度優(yōu)先遍歷。

[ Last edited by huycwork on 2011-6-2 at 12:59 ]

贊一下(2人)

回復此樓

漩渦的中心有一塊空地，空空的。

7樓2011-06-02 12:37:19

已閱回復此樓關注TA 給TA發(fā)消息送TA紅花 TA的回帖

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

程序強帖: 40
應助: 817 (博后)
金幣: 12914.1
紅花: 64
帖子: 2238
在線: 287.3小時
蟲號: 696514
注冊: 2009-02-05
專業(yè): 計算機軟件

★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
余澤成(金幣+2): 鼓勵交流！ 2011-06-04 19:17:36

引用回帖:

等到67,就沒辦法用這個dirty的方法了,呵呵,原題也提示了.

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force.

贊一下(2人)

回復此樓

matlab/VB/python/c++/Java寫程序請發(fā)QQ郵件:790404545@qq.com

8樓2011-06-02 15:25:46

已閱回復此樓關注TA 給TA發(fā)消息送TA紅花 TA的回帖

holmescn

金蟲 (正式寫手)

程序強帖: 37
應助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時
蟲號: 913482
注冊: 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結構

★
余澤成(金幣+1): 鼓勵交流！ 2011-06-04 19:17:46

引用回帖:

Originally posted by huycwork at 2011-06-02 12:37:19:
從數據結構看，可以說是二叉樹，但非滿二叉樹，還可以說是有向圖。
不過二叉樹遍歷肯定不成，先序中序后序遍歷是針對當前節(jié)點和子節(jié)點遍歷的，但這個題不涉及當前節(jié)點和子節(jié)點，而是涉及到兄弟節(jié)點及其子節(jié) ...

不過，我覺得廣度優(yōu)先也不會比libralibra那種從下向上求和的算法好多少。因為基本是一個遍歷的過程。

贊一下(1人)

回復此樓

9樓2011-06-02 16:46:33

已閱回復此樓關注TA 給TA發(fā)消息送TA紅花 TA的回帖

holmescn

金蟲 (正式寫手)

程序強帖: 37
應助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時
蟲號: 913482
注冊: 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結構

★
余澤成(金幣+1): 鼓勵交流！ 2011-06-04 19:17:59

引用回帖:

Originally posted by libralibra at 2011-06-02 15:25:46:
等到67,就沒辦法用這個dirty的方法了,呵呵,原題也提示了.

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challe ...

寫這個算法是為了驗證你那個算法的正確性。

剛才試了一下67題，果然是算不出來啊，2^99真的很大啊。

[ Last edited by holmescn on 2011-6-2 at 16:59 ]

贊一下(1人)

回復此樓

10樓2011-06-02 16:47:30

已閱回復此樓關注TA 給TA發(fā)消息送TA紅花 TA的回帖

相關版塊跳轉我要訂閱樓主 holmescn 的主題更新

返回列表

最具人氣熱帖推薦 [查看全部]		作者	回/看	最后發(fā)表

[考研] 349求調劑 +7	zwjjjjjj 2026-03-31	7/350	2026-04-02 16:49 by zzsw+
[考研] 085600，材料與化工321分求調劑 +11	大饞小子 2026-03-28	11/550	2026-04-02 15:59 by yunlongyang
[考研] 321求調劑一志愿浙江工業(yè)大學生物醫(yī)藥 +5	嘿嘿HC 2026-04-01	6/300	2026-04-02 15:23 by sophie2180
[考研] 一志愿085600中科院寧波所276分求調劑 +26	材料學257求調劑 2026-03-28	27/1350	2026-04-02 15:15 by chyhaha
[考研] 材料調劑 +8	一樣YWY 2026-04-02	8/400	2026-04-02 12:30 by 173785543
[考研] 材料求調劑一志愿哈工大總分298分，前三科223分 +12	dongfang59 2026-03-27	12/600	2026-04-02 12:26 by ms629
[考研] 08開頭看過來！�。� +4	wwwwffffff 2026-03-31	6/300	2026-04-02 11:42 by 均值回歸
[考研] 311求調劑 +9	勇敢的小吳 2026-04-02	9/450	2026-04-02 11:37 by Sammy2
[考研] 生物學327，求調劑 +5	書上的梅子 2026-04-01	6/300	2026-04-02 06:47 by ilovexiaobin
[考研] 266分，一志愿電氣工程，本科材料，求材料專業(yè)調劑 +10	哇呼哼呼哼 2026-04-01	11/550	2026-04-01 21:48 by chyhaha
[考研] 349求調劑 +6	吃的不少 2026-04-01	6/300	2026-04-01 17:55 by JYD2011
[碩博家園] 考研調劑 +5	駱駝男人 2026-04-01	5/250	2026-04-01 14:28 by syjjj0321
[考研] 材料與化工調劑一志愿大連海事085600，349 +9	吃的不少 2026-03-30	9/450	2026-04-01 11:24 by wangjy2002
[考研] 英一數一總分334求調劑 +4	陳陽坤 2026-03-31	4/200	2026-03-31 14:22 by 記事本2026
[考研] 266分，求材料相關專業(yè)調劑 +10	哇呼哼呼哼 2026-03-30	12/600	2026-03-31 11:00 by 熊一刀
[考研] 274求調劑 +6	xiao愛同學 2026-03-30	6/300	2026-03-31 10:04 by cal0306
[考研] 22408 359分調劑 +4	Qshers 2026-03-27	8/400	2026-03-31 08:53 by Qshers
[考研] 327求調劑 +5	小卡不卡. 2026-03-29	5/250	2026-03-30 19:30 by Wang200018
[考研] 一志愿中南大學化學0703總分337求調劑 +6	niko- 2026-03-27	6/300	2026-03-30 10:25 by herarysara
[考研] 308求調劑 +7	墨墨漠 2026-03-27	7/350	2026-03-28 07:43 by 熱情沙漠

24小時熱門版塊排行榜

[交流] Euler 工程 第十八題：三角陣上最大的和 已有4人參與

» 猜你喜歡

» 本主題相關價值貼推薦，對您同樣有幫助:

[交流] Euler 工程第十八題：三角陣上最大的和已有4人參與

» 本主題相關價值貼推薦，對您同樣有幫助: