我被要求在项目欧拉问题 11 的 20x20 网格中找到水平、对角或垂直的 4 个相邻数字的最大乘积。可以在此处找到该网格：http ://projecteuler.net/problem=11 。
我找不到比循环整个数组 4 次更有效的方法。我创建了一个最初设置为 0 的变量 max。然后我水平循环遍历数组，并找到了产品。如果产品大于最大值，则将最大值设置为该产品，等等。我对所有 4 个循环都这样做了。但是，我的回答是错误的，而且可能太大了。
#include <iostream>
using namespace std;
int main () {
int twenty_grid[20][20] =
{
{ 8, 2, 22, /* data elided since the question links to it */ },
…
}
int max = 0;
// Pass 1: This determines the greatest element horizontally
for (int i = 0; i < 20; ++i) {
for (int j = 0; j < 17; ++j) {
// j stops at 17 to avoid a segmentation fault.
int n = twenty_grid[i][j] *
twenty_grid[i][j+1] *
twenty_grid[i][j+2] *
twenty_grid[i][j+2] *
twenty_grid[i][j+3];
if (n > max)
max = n;
}
}
// Now we do the same loop, except we do i + 1, i + 2, etc,
// rather than j +1, j+2. This does it vertically. Pass 2:
for (int i = 0; i < 17; ++i) {
for (int j = 0; j < 20; ++j) {
int n = twenty_grid[i][j] *
twenty_grid[i+1][j] *
twenty_grid[i+2][j] *
twenty_grid[i+3][j];
if (n > max) {
max = n;
}
}
}
// Finally, we increment both i and j to get the diagonals.
for (int i = 0; i < 17; ++i) {
for (int j = 0; j < 20; ++j) {
int n = twenty_grid[i][j] *
twenty_grid[i+1][j+1] *
twenty_grid[i+2][j+2] *
twenty_grid[i+3][j+3];
if (n > max) {
max = n;
}
}
}
// For diagonals, 2 passes are needed to account for both directions.
for (int i = 0; i < 17; i++) {
for (int j = 3; j < 20; j++) {
int n = twenty_grid[i][j] *
twenty_grid[i + 1][i -1] *
twenty_grid[i + 2][i -2] *
twenty_grid[i + 3][i -3];
if (n > max)
max = n;
}
}
cout << max << endl;
return 0;
}
为了看看为什么我的答案总是错误的，我开始打印出每个单独的产品，因为它是计算出来的。令我惊讶的是，其中许多都是负面的。检查我的循环后，他们似乎没有访问数组中的任何数据。有人可以引导我朝着修复此代码的正确方向前进吗？