Project Euler 题解 #11 Largest product in a grid

本文主要是介绍Project Euler 题解 #11 Largest product in a grid，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：Largest product in a grid

数学描述

遍历：

从横、竖、左斜、右斜四个方向进行遍历。

左斜和右斜又分为：主对角、上三角、下三角。

减枝方法：

由于全为非负数，那么最大的乘积必>=0。当遍历到的数为0时，那么可直接跳过。

代码实现：

//https://projecteuler.net/problem=11
//Largest product in a grid
#include "stdafx.h"
#include <iostream>
#include <limits>
#include <fstream>
#include <iomanip>
#include <BaseTsd.h>
using namespace std;
template< class T > T MAX( T a, T b)
{
return a > b? a : b;
}
typedef short ElemType;
INT64 GetMaxProductFromLine(const ElemType *A, int N, int seq_num)
{
if (seq_num > N)
{
cout<<"N must be great than seq_num"<<endl;
return 0;
}
INT64 max_product = LLONG_MIN;
for (int i = 0; i< N - seq_num + 1; ++i)
{
INT64 product = A[i];
for (int j = 1; j < seq_num; ++j)
{
product *= A[i + j];
}
max_product = MAX(max_product, product);
}
return max_product;
}
INT64 GetMaxProductFromMatrix(ElemType **M, int N, int seq_num)
{
ElemType *A = new ElemType[N];
INT64 max = LLONG_MIN, temp = 0;
//横向,竖向
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j) //横向搜索
{
A[j] = M[i][j];
}
temp = GetMaxProductFromLine(A, N, seq_num);
max = MAX(max, temp);
for (int j = 0; j < N; ++j) //竖向搜索
{
A[j] = M[j][i];
}
temp = GetMaxProductFromLine(A, N, seq_num);
max = MAX(max, temp);
}
//右斜搜索
for (int i = 0; i < N; ++i) //主对角
{
A[i] = M[i][i];
}
temp = GetMaxProductFromLine(A, N, seq_num);
max = MAX(max, temp);
for (int i = 1; i < N - seq_num + 1; ++i) 
{
for (int j = 0; j < N -i; ++j) //上三角
{
A[j] = M[j][j + i];
}
temp = GetMaxProductFromLine(A, N - i, seq_num);
max = MAX(max, temp);
for (int j = 0; j < N -i; ++j) //下三角
{
A[j] = M[j + i][j];
}
temp = GetMaxProductFromLine(A, N - i, seq_num);
max = MAX(max, temp);
}
//左斜搜索
for (int i = 0; i < N; ++i) //主对角
{
A[i] = M[i][N - 1 - i];
}
temp = GetMaxProductFromLine(A, N, seq_num);
max = MAX(max, temp);
for (int i = 1; i < N - seq_num + 1; ++i) 
{
for (int j = 0; j < N -i; ++j) //上三角
{
A[j] = M[j][N - 1 - i - j];
}
temp = GetMaxProductFromLine(A, N - i, seq_num);
max = MAX(max, temp);
for (int j = 0; j < N -i; ++j) //下三角
{
A[j] = M[j + i][N - 1 - j];
}
temp = GetMaxProductFromLine(A, N - i, seq_num);
max = MAX(max, temp);
}
delete[] A;
return max;
}
void read_data(ElemType **M, int N)
{
fstream file("data.txt");
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
file>>M[i][j];
}
}
file.close();
}
int _tmain(int argc, _TCHAR* argv[])
{
//int N = 3, num = 2;
int N = 20, num = 4;
ElemType **M = new ElemType *[N];
for (int i = 0; i < N; ++i)
{
M[i] = new ElemType[N];
}
read_data(M, N);
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
cout<<setw(2)<<setfill('0')<<M[i][j]<<" ";
}
cout<<endl;
}
INT64 max = GetMaxProductFromMatrix(M, N, num);
cout<<"The greatest product of "<<num<<" adjacent numbers is "<<max<<endl;
for (int i = 0; i < N; ++i)
{
delete [] M[i];
}
delete M;
system("pause");
return 0;
}

输出：

89949787=70600674

这篇关于Project Euler 题解 #11 Largest product in a grid的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---