第11题-计算最大的4个数之积
本文包含了欧拉项目第11题的解法
问题描述
这个问题翻译为中文是：
给定以下这个20x20的网格，求在这个网格中同方向的相邻的4个数字的积的最大值是多少
解题思路
题目比较简单，只需要会遍历二维数组就行
rust语言实现
p11.rs
use std::cmp::max;
pub fn max_product(grid: &[[usize; 20]; 20]) -> usize {
let mut max_num = 0;
for (i, row) in grid.iter().enumerate() {
for (j, _col) in row.iter().enumerate() {
let mut dia_prod1: usize = 0;
let mut dia_prod2: usize = 0;
let mut dia_prod3: usize = 0;
let mut dia_prod4: usize = 0;
let mut row_prod: usize = 0;
let mut col_prod: usize = 0;
if i >= 3 && j >= 3 {
// left-up
dia_prod2 =
grid[i][j] * grid[i - 1][j - 1] * grid[i - 2][j - 2] * grid[i - 3][j - 3];
}
if i <= 16 && j <= 16 {
// right-down
dia_prod1 =
grid[i][j] * grid[i + 1][j + 1] * grid[i + 2][j + 2] * grid[i + 3][j + 3];
}
if i >= 3 && j <= 16 {
// left-down
dia_prod3 =
grid[i][j] * grid[i - 1][j + 1] * grid[i - 2][j + 2] * grid[i - 3][j + 3];
}
if i <= 16 && j >= 3 {
// right-up
dia_prod4 =
grid[i][j] * grid[i + 1][j - 1] * grid[i + 2][j - 2] * grid[i + 3][j - 3];
}
if i <= 16 {
// left->right
row_prod = grid[i][j] * grid[i + 1][j] * grid[i + 2][j] * grid[i + 3][j];
}
if j <= 16 {
// up -> down
col_prod = grid[i][j] * grid[i][j + 1] * grid[i][j + 2] * grid[i][j + 3];
}
let max_prod = max(
max(
max(max(max(dia_prod1, dia_prod2), dia_prod3), dia_prod4),
row_prod,
),
col_prod,
);
max_num = max(max_prod, max_num);
}
}
max_num
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_max_product() {
let grid = [
[
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,
],
];
assert_eq!(70600674, max_product(&grid));
}
}
代码解释
遍历二维数组，基于当前迭代到的元素grid[i][j]出发，算出对应6个方向的积，为什么不是8个方向呢，因为左右，右左，上下，下上重复计算了，可以合并为2个。在计算乘积时要注意不要数组越界了，所以要做好判断。
小技巧
在把题目中那400个数复制到代码中时，可以使用编辑器的快捷键来操作，比如说把空格批量替换为逗号，在每行的开头结尾自动添加中括号，毕竟是一次性的活没必要写复杂的程序读入字符串输出二维数组
在写断言时，随便写一个值然后跑测试，这样就能看到程序运行时的结果，如果断言通过程序是不会有任何输出的
知识点
如何定义二维数组
如何迭代二维数组
Last updated
