行中n个数字的矩阵最大乘积 [英] Matrix largest product of n numbers in a row
问题描述
您好，我在尝试写一个小程序时遇到问题。问题是如果我给出任何矩阵大小（这个例子只是说一个4x4），找到一个行中n个数字的最大的乘积（让我们说n = 3）。一行中的3个数字可以是水平，垂直或对角线。因此，需要一个矩阵：
1 1 2 5
1 5 2 4
1 7 2 3
1 8 2 1
如果n等于3，那么我最大的产品是280 5 * 7 * 8）。现在我有我的矩阵加载到2D向量。我不是太挑剔如何程序工作（蛮力是好的），到目前为止，我知道我必须有至少两个嵌套for循环通过每个盯着矩阵的位置，但我没有成功地找到当前的答案。任何建议都会有帮助，谢谢。
版本可以使用滚动乘法来找到最大乘积，这个滚动过程意味着我们不必乘以 n 值来找到这些 n 值的每个乘积，但是我们只需要执行一个乘法和一个部门：
if（currN == N）{//计算完整的产品第一次
while（currn）{
product * =（* it3 ++）;
--currn;
}
} else {//滚动计算
product * =（*（it3 + n - 1））/（*（it3 - 1）
it3 + = n;
}
完成此操作也可以处理列：
填充矩阵：
#include< cstdio>
#include< vector>
#include< algorithm>
#include< iterator>
#include< iostream>
using namespace std;
typedef vector<载体， int> >矩阵;
typedef Matrix :: iterator outIt;
typedef vector< int> :: iterator inIt;
void fillMatrix（Matrix& matrix）{
outIt it = matrix.begin（）;
（* it）.push_back（1）;
（* it）.push_back（1）;
（* it）.push_back（2）;
（* it）.push_back（5）;
++ it;
（* it）.push_back（1）;
（* it）.push_back（5）;
（* it）.push_back（2）;
（* it）.push_back（4）;
++它;
（* it）.push_back（1）;
（* it）.push_back（7）;
（* it）.push_back（2）;
（* it）.push_back（3）;
++ it;
（* it）.push_back（1）;
（* it）.push_back（8）;
（* it）.push_back（2）;
（* it）.push_back（1）;
}
打印矩阵并在行中找到最大产品：
void printMatrix（Matrix& matrix）{
outIt it = matrix.begin（）;
while（it！= matrix.end（））{
inIt it2 =（* it）.begin（）;
while（it2！=（* it）.end（））{
printf（％d，* it2）;
++ it2;
}
printf（\\\
）;
++ it;
}
}
/ **
*
* @param matrix
*使用滚动乘法的行中最大的乘积
* @param n个因素
* @param v最大乘积的因子
* @返回最大乘积
* /
int maximumProductInRow（Matrix& matrix，int n，vector< int>& v）{
if（n> matrix.size（））return -1;
int res = 0;
int N = matrix.size（） - n + 1; //行（或列）中的产品数量
/ *在行中搜索* /
outIt it = matrix.begin（）;
while（it！= matrix.end（））{
inIt it2 =（* it）.begin（）;
int currN = N;
int product = 1;
while（currN）{//滚动产品计算
inIt it3 = it2;
int currn = n;
if（currN == N）{//计算完整的产品第一次
while（currn）{
product * =（* it3 ++）;
--currn;
}
} else {//滚动计算
product * =（*（it3 + n - 1））/（*（it3 - 1）
it3 + = n;
}
if（product> res）{
res = product;
copy（it3 - n，it3，v.begin（））;
}
--currN;
++ it2;
}
++ it;
}
return res;
}
用法：
/ *
*
* /
int main（int argc，char ** argv）{
矩阵4，vector< int>（））;
fillMatrix（matrix）;
printMatrix（matrix）;
vector< int> v（3）;
int res = largestProductInRow（matrix，3，v）;
printf（res：％d\\\
，res）;
copy（v.begin（），v.end（），ostream_iterator< int>（cout，，））;
return 0;
}
结果：
res：42
7,2,3，
RUN SUCCESSFUL（总时间：113ms） p>
Hello I'm having trouble with a little program I am trying to write. The problem is if I'm given any matrix size (lets just say a 4x4 for this example), find the largest product of n numbers in a row (lets say n = 3). The 3 numbers in a row can be horizontal, vertical, or diagonal. So heres a matrix:
1 1 2 5
1 5 2 4
1 7 2 3
1 8 2 1
If n was equal to 3 then my largest product would be 280 (5*7*8). Now I have my matrix loaded into a 2D vector. I'm not too picky on how the program works(brute force is fine), so far I know I'm going to have to have at least two nested for loops to go through each staring location of the matrix but I haven't been successful in finding the current answer. Any advice will help, thank you.
Version to find max product in rows using rolling multiplication to save some resources. This rolling procedure means that we don't have to multiply n values to find each product of these n values, but instead we have to just do one multiplication and one division:
if (currN == N) { // compute full product first time
while (currn) {
product *= (*it3++);
--currn;
}
} else { // rolling computation
product *= (*(it3 + n - 1)) / (*(it3 - 1));
it3 += n;
}
It is up to you to complete this to handle also columns:
populate matrix:
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
using namespace std;
typedef vector< vector< int> > Matrix;
typedef Matrix::iterator outIt;
typedef vector< int>::iterator inIt;
void fillMatrix( Matrix& matrix) {
outIt it = matrix.begin();
(*it).push_back( 1);
(*it).push_back( 1);
(*it).push_back( 2);
(*it).push_back( 5);
++it;
(*it).push_back( 1);
(*it).push_back( 5);
(*it).push_back( 2);
(*it).push_back( 4);
++it;
(*it).push_back( 1);
(*it).push_back( 7);
(*it).push_back( 2);
(*it).push_back( 3);
++it;
(*it).push_back( 1);
(*it).push_back( 8);
(*it).push_back( 2);
(*it).push_back( 1);
}
print matrix and find max product in rows:
void printMatrix( Matrix& matrix) {
outIt it = matrix.begin();
while ( it != matrix.end()) {
inIt it2 = (*it).begin();
while ( it2 != (*it).end()) {
printf( "%d", *it2);
++it2;
}
printf( "\n");
++it;
}
}
/**
*
* @param matrix
* Largest product in row using rolling multiplication
* @param n number of factors
* @param v factors of largest product
* @return largest product
*/
int largestProductInRow( Matrix& matrix, int n, vector< int>& v) {
if ( n > matrix.size()) return -1;
int res = 0;
int N = matrix.size() - n + 1; // number of products in row (or column)
/* search in rows */
outIt it = matrix.begin();
while (it != matrix.end()) {
inIt it2 = (*it).begin();
int currN = N;
int product = 1;
while (currN) { // rolling product calculation
inIt it3 = it2;
int currn = n;
if (currN == N) { // compute full product first time
while (currn) {
product *= (*it3++);
--currn;
}
} else { // rolling computation
product *= (*(it3 + n - 1)) / (*(it3 - 1));
it3 += n;
}
if (product > res) {
res = product;
copy(it3 - n, it3, v.begin());
}
--currN;
++it2;
}
++it;
}
return res;
}
usage:
/*
*
*/
int main(int argc, char** argv) {
Matrix matrix( 4, vector< int>());
fillMatrix( matrix);
printMatrix( matrix);
vector< int> v(3);
int res = largestProductInRow( matrix, 3, v);
printf( "res:%d\n", res);
copy( v.begin(), v.end(), ostream_iterator<int>(cout, ","));
return 0;
}
result:
res:42
7,2,3,
RUN SUCCESSFUL (total time: 113ms)
这篇关于行中n个数字的矩阵最大乘积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
