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

%% 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

% Elapsed time is 0.002799 seconds.
% ans =
%         1074

#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;
}

7273
elapsed time=0.000000 seconds.

#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;
}

# -*- 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)]

Originally posted by holmescn at 2011-06-02 12:16:51:
这个题，写个穷举还挺麻烦。虽然速度也不慢。看我的quick & dirty的Python版
[code]
# -*- coding: utf-8 -*-
m = [[75],
    [95,64],
    [17,47,82],
    [18,35,87,10],
    [20,4,82,47,65],
   ...

Originally posted by holmescn at 2011-06-02 12:16:51:
这个题，写个穷举还挺麻烦。虽然速度也不慢。看我的quick & dirty的Python版
[code]
# -*- coding: utf-8 -*-
m = [[75],
    [95,64],
    [17,47,82],
    [18,35,87,10],
    [20,4,82,47,65],
   ...

Originally posted by huycwork at 2011-06-02 12:37:19:
从数据结构看，可以说是二叉树，但非满二叉树，还可以说是有向图。
不过二叉树遍历肯定不成，先序中序后序遍历是针对当前节点和子节点遍历的，但这个题不涉及当前节点和子节点，而是涉及到兄弟节点及其子节 ...

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 ...