Матрица наибольшего произведения из n чисел подряд
Здравствуйте, у меня проблемы с маленькой программой, которую я пытаюсь написать. Проблема в том, что если мне дают матрицу любого размера (скажем, 4×4 для этого примера), найдите наибольшее произведение из 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). Теперь моя матрица загружена в двухмерный вектор. Я не слишком придирчив к тому, как работает программа (грубая сила в порядке), так что я знаю, что мне понадобится как минимум два вложенных цикла для прохождения каждого исходного положения матрицы, но я не удалось найти текущий ответ. Любой совет поможет, спасибо.
Решение
Версия для поиска максимального продукта в строках с использованием скользящего умножения для экономии некоторых ресурсов. Эта скользящая процедура означает, что нам не нужно умножать n значения, чтобы найти каждый продукт из этих 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;
}
Вы должны завершить это, чтобы обработать также столбцы:
заполнить матрицу:
#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);
}
распечатать матрицу и найти максимальный товар в строках:
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;
}
использование:
/*
*
*/
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;
}
результат:
разрешение: 42
7,2,3,
RUN SUCCESSFUL (общее время: 113мс)
Другие решения
Допустим, у нас есть s x t матрица (s столбцов и t строк).
int res = 0;
if(s >= n)
{
for (int r = 0; r < t; ++r) // for each row
{
for (int i = 0; i <= s-n; ++i) //moving through the row
{
int mul = m[i][0];
for (int j = 1; j < n; ++j) //calculating product in a row
{
mul*=m[i][j];
}
if(mul > res)
{
res = mul;
//save i, j here if needed
}
}
}
}if(t >= n)
{
for (int c = 0; c < s; ++c) // for each column
{
for (int i = 0; i <= t-n; ++i) //moving through the column
{
int mul = m[0][i];
for (int j = 1; j < n; ++j) //calculating product in a column
{
mul*=m[j][i];
}
if(mul > res)
{
res = mul;
//save i, j here if needed
}
}
}
}
Если вы настаиваете на грубой силе, то, как вы сказали, вам нужно перебирать все [x,y],
которые будут отправными точками строк.
Из них вы можете перебрать k смежные элементы во всех направлениях.
Вы можете сохранить направления как векторы в массиве.
Это будет работать в O(k n^2),
За n x n матрица и ищет k элементы в строке, C-подобный псевдокод будет выглядеть следующим образом (заметьте, что для простоты нет проверки границ):
// define an array of directions as [x,y] unit vectors
// you only need to check in 4 directions, other 4 are the same, just reversed
int[4][2] dirs = {{1,0}, {1,1}, {0,1}, {-1,1}};
// iterate over all starting positions
for (x = 0; x < n; ++x) {
for (y = 0; y < n; ++y) {
// iterate over all directions
for (d = 0; d < 4; ++d) {
result = 1;
// iterate over elements in row starting at [x,y]
// going in direction dirs[d]
for (i = 0; i < k; ++i) {
// multiply current result by the element,
// which is i places far from the beginning [x,y]
// in the direction pointed by dirs[d]
new_x = x + i * dirs[d][0];
new_y = y + i * dirs[d][1];
// you need to check the bounds, i'm not writing it here
// if new_x or new_y are outside of the matrix
// then continue with next direction
result *= matrix[new_x][new_y];
}
if (result > max) {
max = result;
}
}
}
}
Чуть лучше, менее грубым способом было бы
начать на границе матрицы, выбрать направление и идти в этом направлении к противоположной стороне матрицы, сохраняя произведение последнего k номера в пути.
При ходьбе вы держите продукт, умножая его на число, которое вы получили, и деля его на число, которое вы оставили. k шаги назад.
Таким образом, с некоторыми проверками границ, конечно,
продукт всегда продукт последнего k номера,
поэтому, если текущий продукт больше максимального, просто max = product,
Это всегда работает в O(n^2),