3
我正在解决Project Euler的问题11。我已经想出了算法和我需要做的事情。网格被保存在一个文件grid.txt和它的内容是 -网格中的相邻产品
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
的问题是 - 什么是四个相邻数的最大产品在任何方向（上，下，左，右，或对角）在20x20网格？
我知道算法正常工作，因为我已经尝试使用cout输出数字，并且它们以正确的顺序出现。虽然它给了我一个不正确的答案，但是可能是错误？
void problem11()
{
vector<vector<int>> grid;
ifstream stream("grid.txt");
string line;
char *tok;
if (stream.is_open())
{
while(stream.good())
{
getline(stream, line);
tok = strtok((char *)line.c_str(), " ");
vector<int> row;
while (tok != NULL)
{
int field;
stringstream ss;
ss << tok;
ss >> field;
row.push_back(field);
tok = strtok(NULL, " ");
}
grid.push_back(row);
}
stream.close();
}
unsigned long highest = 0;
/// LEFT TO RIGHT
for (int i=0; i < 20; i++) // i'th row
{
vector<int> row = grid.at(i);
for (int c=0; c < 20-3; c++) // -3 to accomodate for last
{
unsigned long prod = row.at(c) * row.at(c+1) * row.at(c+2) * row.at(c+3); // four consecutive
//cout << row.at(c) << " " << row.at(c+1) << " " << row.at(c+2) << " " << row.at(c+3) << endl;
if (prod > highest)
highest = prod;
}
}
/// TOP TO DOWN
/// This moves from left to right, then top to botom
///
for (int i=0; i < 20-3; i++) // subtract last 3
{
vector<int> row1, row2, row3, row4;
row1 = grid.at(i);
row2 = grid.at(i+1);
row3 = grid.at(i+2);
row4 = grid.at(i+3);
for (int c=0; c < 20; c++)
{
unsigned long prod = row1.at(c) * row2.at(c) * row3.at(c) * row4.at(c);
//cout << row1.at(c) << " " << row2.at(c) << " " << row3.at(c) << " " << row4.at(c) << endl;
if (prod > highest)
highest = prod;
}
}
/// DOWN DIAGONAL
/// This moves diagonally from left to right, top to bottom
for (int i=0; i < 20-3; i++) // subtract last 3
{
vector<int> row1, row2, row3, row4;
row1 = grid.at(i);
row2 = grid.at(i+1);
row3 = grid.at(i+2);
row4 = grid.at(i+3);
for (int c=0; c < 20-3; c++) // omit last 3
{
unsigned long prod = row1.at(c) * row2.at(c+1) * row3.at(c+2) * row4.at(c+3);
//cout << row1.at(c) << " " << row2.at(c+1) << " " << row3.at(c+2) << " " << row4.at(c+3) << endl;
if (prod > highest)
highest = prod;
}
}
/// UP DIAGONAL
/// This moves diagonally from left to right, bottom to top
for (int i=3; i < 20; i++) // start from 3, skipping first four
{
vector<int> row1, row2, row3, row4;
row4 = grid.at(i);
row3 = grid.at(i-1);
row2 = grid.at(i-2);
row1 = grid.at(i-3);
for (int c=0; c < 20-3; c++) // omit last 3
{
unsigned long prod = row4.at(c) * row3.at(c+1) * row3.at(c+2) * row4.at(c+3);
//cout << row4.at(c) << " " << row3.at(c+1) << " " << row2.at(c+2) << " " << row1.at(c+3) << endl;
if (prod > highest)
highest = prod;
}
}
cout << "Required: " << highest;
}
您是否试过在调试器中逐步调试程序？或者打印出中间变量？或者先运行一个简单的数据集？你是否确定了四个循环中的哪一个（上下，左 - 右，向上，向下）是不正确的？ – 2011-06-08 10:50:40
你怎么知道答案不正确？你会得到什么答案而不是正确答案？ – 2011-06-08 11:05:56
我不打算回答这个问题（并且破坏了它的乐趣），但我建议将它分解成（至少）四个单独的函数并独立地测试它们。 – Johnsyweb 2011-06-08 11:16:21