Project Euler 18

Mathematica C/C++ 
以下の三角形の頂点から下まで移動するとき、その数値の合計の最大値は23になる。

   3
  7 5
 2 4 6
8 5 9 3
この例では 3 + 7 + 4 + 9 = 23

以下の三角形を頂点から下まで移動するとき、その最大の合計値を求めよ。

              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
注: ここではたかだか 16384 通りのルートしかないので、すべてのパターンを試すこともできる。Problem 67 は同じ問題だが100行あるので、総当りでは解けない。もっと賢い方法が必要である。

Mathematica

A = Import["mathematica/pe/pedata/pe18.txt", "Table"];

LENGTH = 15;

A2 = Map[PadRight[#, LENGTH] &, A];

B = {};
B = Append[B, A2[[1]]];

For[i = 2, i <= LENGTH, i++,
  Clear[tmps];
  tmps = {};
  For[j = 1, j <= LENGTH, j++,
    If[j == 1,
      tmps = Append[tmps, A2[[i, j]] + B[[i - 1, j]]],
      tmps = Append[tmps, A2[[i, j]] + Max[B[[i - 1, j]], B[[i - 1, j - 1]]]]
    ]
  ];
  B = Append[B, tmps]
]

Max[B]

A2は15×15配列で、1行目には{75,0,0,0,...,0}、2行目には{95,64,0,0,0,...,0}のようにデータが入っています。
For文の中でデータを呼び出すために、Bとtmpsには Append 関数を使って値を挿入しています。


Append は第1引数に第2引数を最終要素として追加する、という機能の関数です。

このプログラムでProblem 67も解くことができました。

C/C++

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main(){
	const int SIZE = 15;
	ifstream ifs("dat018.txt");
	int dat[SIZE][SIZE];
	int dat2[SIZE][SIZE];
	string datstr;
	
	// ファイル読み込み
	for(int i=0 ; i<SIZE ; i++){
		for(int j=0 ; j<=i ; j++){
			ifs >> datstr;
			dat[i][j] = atoi(datstr.c_str());
		}
		for(int j=i+1 ; j<SIZE ; j++){
			dat[i][j]=0;
		}		
	}	

	// 1行目をコピー dat -> dat2
	for(int j=0 ; j<SIZE ; j++){
		dat2[0][j] = dat[0][j];
	}

	// DP
	for(int i=1 ; i<SIZE ; i++){
		for(int j=0 ; j<SIZE ; j++){
			if(j==0) dat2[i][j] = dat2[i-1][j];
			dat2[i][j] = max(dat2[i-1][j], dat2[i-1][j-1]) + dat[i][j];
		}
	}

	int ans=0;
	for(int j=0 ; j<SIZE ; j++){
		if(ans < dat2[SIZE-1][j]) ans = dat2[SIZE-1][j];
	}
	cout << ans << endl;
	
	int end;
	cin >> end;
	
	return 0;
}

初めてVS2010でやってみたんですが、もういろいろと困りました。まず一番違うなーと思ったのは、デバッグなしで実行したときにキー待ちを入れてくれなくなったことです。
なので、自分で" int end; cin >> end; " なんて行を追加してます。ないとコンソールが一瞬で立ち上がって閉じる。
それからVS2008のプロジェクトの変換もなんだか怪しいものでした。先行き不安です。
問題自体は簡単なもので、典型的なDP(Dynamic Programming)です。