С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
virtuos553
48 / 3 / 1
Регистрация: 18.12.2012
Сообщений: 247
Записей в блоге: 1
#1

Найти наибольший прямоугольник в матрице состоящий из четных чисел - C++

18.01.2014, 22:47. Просмотров 768. Ответов 9
Метки нет (Все метки)

Дана матрица натуральных чисел. Найти наибольший прямоугольник в матрице состоящий из четных чисел.

исходная матрица хранится в файле input.txt
файл имеет такую структуру:
m n
a_11 .. a_1n
...
a_m1 .. a_mn

Прямоугольную матрицу нужно записать в файл output.txt
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.01.2014, 22:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти наибольший прямоугольник в матрице состоящий из четных чисел (C++):

Найти наибольший прямоугольник в матрице состоящий из четных чисел - C++
Дана матрица натуральных чисел. Найти наибольший прямоугольник в матрице состоящий из четных чисел.

В матрице найти наибольший прямоугольник состоящий из четных чисел - C++
в матрице найти наибольший прямоугольник состоящий из четных чисел. До этого несколько раз создавал тему, никто так и не смог написать...

Матрица.В матрице A(6; 6) найти произведение суммы четных чисел в 3-ей строке и суммы отрицательных чисел 1-го столбца - C++
В матрице A(6; 6) найти произведение суммы четных чисел в 3-ей строке и суммы отрицательных чисел 1-го столбца:cry:

Найти и вывести ту строку в этой матрице, которая содержит наибольшее количество четных чисел - C++
Добрый день! Помогите с реализацией данного алгоритма? Дана матрица А размерности n на n. Найти и вывести ту строку в этой матрице,...

Получить массив, состоящий только из четных чисел исходного массива - C++
Здравствуйте, помогите решить проблему. Делаю задание ".Составьте программу для решения следующей задачи: «Дан одномерный массив целого...

Найти наибольший элемент в квадратной матрице - C++
Дана действительная квадратная матрица порядка 10. В строках с отрицательным элементом но главной диагонали найти наибольший из всех...

9
contedevel
57 / 55 / 8
Регистрация: 07.10.2012
Сообщений: 598
19.01.2014, 00:56 #2
Цитата Сообщение от virtuos553 Посмотреть сообщение
Дана матрица натуральных чисел. Найти наибольший прямоугольник в матрице состоящий из четных чисел.

исходная матрица хранится в файле input.txt
файл имеет такую структуру:
m n
a_11 .. a_1n
...
a_m1 .. a_mn

Прямоугольную матрицу нужно записать в файл output.txt
Ну, я думаю проблем с чтением из файла нет?!) Если есть, то вот, к примеру, Click me!
А так всё очень просто Используете
C++
1
vector <vector <int> > myMatrix(m, vector <int> (n, 0);
, так проще будет, но можно и так
C++
1
int * myMatrix = (int*) malloc(m*n*sizeof(int));
Далее для простоты можете создать еще один такой массив типа bool, а затем рекурсивно проверяете числа в матрице на точность, отмечая проверенные во втором массиве, только рекурссивная функция должна проверять рядом стоящие числа от текущее позиции и считать сколько просчитала уже, а координаты центра запуска (пусть это будет левый верхний угол например) и обнаруженного размера записывать в еще один массив, например) Потом в этом массиве находите наибольшее число, смотрите координаты его угла, а далее вывод с проверкой на четность, как только в строке следующее число нечетное переходите к началу новой с позицией по горизонтали как у первой)
0
contedevel
57 / 55 / 8
Регистрация: 07.10.2012
Сообщений: 598
19.01.2014, 01:06 #3
Вот рисунок сделал, чтобы понятнее было (рекурсивная функция вызывается в цикле для каждого элемента матрицы, если он false в массиве маски)
Найти наибольший прямоугольник в матрице состоящий из четных чисел

Можно, конечно, и с помощью стека сделать, но рекурсией проще, вроде)
0
Croessmah
Ушел
Эксперт CЭксперт С++
13558 / 7708 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 1
25.01.2014, 23:15 #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <vector>
 
 
 
struct rectangle {
   size_t left ;
   size_t top ;
   size_t right ;
   size_t bottom ;
   rectangle ( size_t left_, size_t top_ , size_t right_, size_t bottom_ ) : left(left_) , top (top_) , right (right_) , bottom(bottom_) {
   }
} ;
 
 
 
size_t square ( const rectangle & rect ) {
   return ( ( rect.right - rect.left ) + 1 ) * ( ( rect.bottom - rect.top ) + 1 ) ;
}
 
 
template < typename T1 , typename T2 >
rectangle gr ( const std::vector < std::vector < T1 > > & matrix, size_t left , size_t top , const T2 & predicate ) {
   rectangle maxRect ( 0 , 0 , 0 , 0 ) ;
   size_t width = 0  ;
   for ( size_t i = top , height = matrix.size() ; i < height ; ++i ) {
      width = width ? width : matrix[i].size() ;
      for ( size_t j = left ; j < matrix[i].size() &&  j < width ; ++j ) {
         if ( !predicate(matrix [i][j]) ) {
            width = j ;
            if ( j == left )
               return maxRect ;
         } else {
            rectangle rect ( left , top , j ,  i  ) ;
            if ( square(rect) > square(maxRect) )
               maxRect = rect ;
         }
      }
   }
   return maxRect ;
}
 
 
template < typename T >
bool isEven ( const T & first ) {
   return !(first & 1) ;
}
 
 
int main ( ) {
   std::vector < std::vector < int > > matrix
   {
         { 2 , 1 , 4 , 5 , 5 } ,
         { 6 , 6 , 8 , 8 , 8 } ,
         { 7 , 4 , 2 , 8 , 6 } ,
         { 2 , 1 , 8 , 1 , 7 } ,
         { 7 , 7 , 7 , 7 , 7 }
   } ;
   rectangle maxRect ( 0 , 0 , 0 , 0 ) ;
   for ( size_t i = 0 , height = matrix.size() ; i < height ; ++i ) {
      for ( size_t j = 0 , width = matrix[i].size() ; j < width ; ++j ) {
         rectangle rect ( gr ( matrix , j , i , isEven<int> ) ) ;
         if ( square(rect) > square(maxRect) )
            maxRect = rect ;
      }
   }
   std::cout << "( " << maxRect.left << " , " << maxRect.top << " ) - ( " << maxRect.right << " , " << maxRect.bottom << " ) : " << square(maxRect) <<std::endl ;
}
2
gromo
372 / 271 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
25.01.2014, 23:23 #5
Croessmah, как понять вывод результата? (С кодом не разбирался)
( 1 , 1 ) - ( 4 , 2 ) : 8 ?
0
Croessmah
Ушел
Эксперт CЭксперт С++
13558 / 7708 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 1
25.01.2014, 23:30 #6
Цитата Сообщение от gromo Посмотреть сообщение
Croessmah, как понять вывод результата?
в первой скобке индексы левого верхнего элемента прямоугольника, во второй скобке индекс правого нижнего элемента прямоугольника, после двоеточия площадь прямоугольника:
Название: cyberforum_matrix.png
Просмотров: 88

Размер: 3.4 Кб

P.S. Могут быть баги, куда ж без них то
0
Croessmah
Ушел
Эксперт CЭксперт С++
13558 / 7708 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 1
25.01.2014, 23:48 #7
Исправил некоторые ошибки:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <vector>
#include <utility>
 
 
struct rectangle {
   size_t left ;
   size_t top ;
   size_t right ;
   size_t bottom ;
   rectangle ( size_t left_, size_t top_ , size_t right_, size_t bottom_ ) : left(left_) , top (top_) , right (right_) , bottom(bottom_) {
   }
} ;
 
 
 
size_t square ( const rectangle & rect ) {
   return ( ( rect.right - rect.left ) + 1 ) * ( ( rect.bottom - rect.top ) + 1 ) ;
}
 
 
template < typename T1 , typename T2 >
std::pair < rectangle , bool > gr ( const std::vector < std::vector < T1 > > & matrix, size_t left , size_t top , const T2 & predicate ) {
   rectangle maxRect ( 0 , 0 , 0 , 0 ) ;
   bool flag = false ;
   size_t width = 0  ;
   for ( size_t i = top , height = matrix.size() ; i < height ; ++i ) {
      width = width ? width : matrix[i].size() ;
      for ( size_t j = left ; j < matrix[i].size() &&  j < width ; ++j ) {
         if ( !predicate(matrix [i][j]) ) {
            width = j ;
            if ( j == left )
               return {maxRect,flag} ;
         } else {
            rectangle rect ( left , top , j ,  i  ) ;
            if ( square(rect) >= square(maxRect) ) {
               maxRect = rect ;
               flag = true ;
            }
         }
      }
   }
   return {maxRect,flag} ;
}
 
 
template < typename T >
bool isEven ( const T & first ) {
   return !(first & 1) ;
}
 
//Добавил еще один предикат для проверки
template < typename T >
bool isEight ( const T & first ) {
   return first == 8 ;
}
 
 
 
template < typename T1 , typename T2 >
std::pair < rectangle , bool > find(const std::vector < std::vector < T1 > > & matrix, const T2 & predicate){
   rectangle maxRect ( 0 , 0 , 0 , 0 ) ;
   bool flag = false ;
   for ( size_t i = 0 , height = matrix.size() ; i < height ; ++i ) {
      for ( size_t j = 0 , width = matrix[i].size() ; j < width ; ++j ) {
         std::pair <rectangle,bool> pr (gr ( matrix , j , i , predicate ));
         rectangle rect ( pr.first ) ;
         if ( square(rect) >= square(maxRect) && pr.second ) {
            maxRect = rect ;
            flag = true ;
         }
      }
   }
   return {maxRect,flag} ;
}
 
int main ( ) {
   std::vector < std::vector < int > > matrix
   {
         { 1 , 1 , 1 , 1 , 5 } ,
         { 8 , 8 , 8 , 2 , 1 } ,
         { 8 , 8 , 8 , 4 , 1 } ,
         { 1 , 8 , 8 , 6 , 7 } ,
         { 7 , 7 , 4 , 4 , 7 }
   } ;
 
   std::pair <rectangle,bool> pr (find ( matrix , isEven<int> ));
   if ( pr.second ) {
      std::cout << "( " << pr.first.left << " , " << pr.first.top << " ) - ( " << pr.first.right << " , " << pr.first.bottom << " ) : " << square(pr.first) <<std::endl ;
   } else {
      std::cout << "not found" << std::endl ;
   }
}
1
__General__
24 / 24 / 3
Регистрация: 04.01.2014
Сообщений: 91
Завершенные тесты: 2
26.01.2014, 00:36 #8
virtuos553, Нужно написать функцию, в которую передавать саму матрицу и индексы-вершины прямоугольника, который нужно "проверить". Функция проверяет каждый элемент прямоугольника на четность, начиная с СЕРЕДИНЫ! и так далее, по спирали. Границы проверяются в последнюю очередь.
Если был найден нечетный элемент, вернуть номер строки и столбца, в которой его нашли.
если нечетного элемента нет, значит проверяемый прямоугольник - хороший

Ну а теперь действуем так:
Сперва проверяем всю матрицу с помощью написанной функции. Если внутри матрицы найден нечетный элемент, то добавляем в очередь (знаете, что такое очередь?:-) ) 4 самых больших прямоугольника, которые не содержат найденного нечетного элемента. Причем добавляем мы в очередь именно в порядке убывания площадей (или как мы сравниваем прямоугольники) - сначала добавим самый большой, потом поменьше итп.
Короче, у нас есть цикл:
пока очередь не пуста,
извлекаем из очереди прямоугольник.
Если он проходит проверку, мы нашли!!!!!
Если нет, то он распадается на 4 прямоугольника поменьше, которые мы добавляем в очередь в порядке убывания площадей.

Не думаю, что существует алгоритм, работающий быстрее + этот алгоритм не требует использования доп. памяти.
0
Kuzia domovenok
2078 / 1907 / 176
Регистрация: 25.03.2012
Сообщений: 6,574
Записей в блоге: 1
26.01.2014, 01:09 #9
Croessmah, нафига в твоём коде нужны шаблоны?
0
Croessmah
Ушел
Эксперт CЭксперт С++
13558 / 7708 / 872
Регистрация: 27.09.2012
Сообщений: 18,996
Записей в блоге: 3
Завершенные тесты: 1
26.01.2014, 01:22 #10
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
нафига в твоём коде нужны шаблоны?
чтобы были
0
26.01.2014, 01:22
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.01.2014, 01:22
Привет! Вот еще темы с ответами:

В матрице найти наибольший по модулю элемент - C++
Задание:&quot;В данной действительной прямоугольной матрице размером nxm найти наибольший по модулю элемент. Получить матрицу порядка (n-1)xm...

В заданной квадратной матрице найти наибольший элемент - C++
В данной квадратной матрице найти наибольший элемент и перемножить попарно элементы строки, в которой он расположен, и элементы столбца, в...

В данной действительной квадратной матрице найти наибольший элемент - C++
В данной действительной квадратной матрице найти наибольший элемент. Получить квадратную матрицу путем отбрасывания в исходной матрице...

Системное программирование (найти наибольший элемент по модулю в матрице n*m) - C++
Тип элементов одномерного массива – действительные числа. В данной действительной прямоугольной матрице размером nxm найти наибольший по...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
10
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.