Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 5.00
korsarqa
7 / 7 / 0
Регистрация: 06.12.2011
Сообщений: 170
#1

Найти в прямоугольной матрице подматрицу из единиц максимального размера. - C++

17.05.2012, 14:23. Просмотров 2079. Ответов 7
Метки нет (Все метки)

Прямоуголная подматрица. Вводится матрица a(m,n) из 0 и 1. Найти в ней прямоугольную подматрицу из одних единиц максимального размера (т.е. с максимальным произведением высоты на длину).

Помогите пожалуйста с написанием этой проги.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.05.2012, 14:23     Найти в прямоугольной матрице подматрицу из единиц максимального размера.
Посмотрите здесь:
C++ Найти квадратную подматрицу максимального размера
C++ В заданной матрице состоящей из нулей и единиц найти квадратную подматрицу, состоящую целиком из нулей
В матрице из нулей и единиц найти квадрат заданного размера, состоящую целиком из нулей C++
Найти в матрице квадратную подматрицу C++
C++ В прямоугольной матрице размера m*n в каждой строке поменять местами первый и минимальный элементы.
C++ В заданной матрице найти максимальную сумму элементов прямоугольной подматрицы среди всех возможных подматриц
Усовершенствовать алгоритм Рабина-Карпа, чтобы он искал символьную подматрицу в символьной матрице C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.05.2012, 17:57     Найти в прямоугольной матрице подматрицу из единиц максимального размера. #2
ограничения по времени есть?
korsarqa
7 / 7 / 0
Регистрация: 06.12.2011
Сообщений: 170
17.05.2012, 20:11  [ТС]     Найти в прямоугольной матрице подматрицу из единиц максимального размера. #3
Ну неделька максимум...
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.05.2012, 05:13     Найти в прямоугольной матрице подматрицу из единиц максимального размера. #4
Ограничения по времени выполнения программы есть?
korsarqa
7 / 7 / 0
Регистрация: 06.12.2011
Сообщений: 170
18.05.2012, 15:25  [ТС]     Найти в прямоугольной матрице подматрицу из единиц максимального размера. #5
нету ограничения
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.05.2012, 22:40     Найти в прямоугольной матрице подматрицу из единиц максимального размера. #6
если матрица a(m,n) уже есть, то можно так:
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
int col=0, i, j, i1, j1, tmp, tmp1;
 for(i=0; i<m; i++)
        for(j=0; j<n; j++)
      {
          if(a[i][j]!=0)
          {
              tmp=0;
              for(j1=j; j1<n && a[i][j1]!=0; j1++)
              {
 
                  tmp1=0;
                  for(i1=i; i1<m && a[i1][j1]!=0; i1++)
                      tmp1++;
                  if(!tmp)
                      tmp=tmp1;
                  else
                  {
                      if(tmp>tmp1)
                          tmp=tmp1;
                  }
                    if(col<tmp*(j1-j+1))
                        col=tmp*(j1-j+1);                    
              }
          }
      }
// здесь в переменной col максимальное значение площади
korsarqa
7 / 7 / 0
Регистрация: 06.12.2011
Сообщений: 170
19.05.2012, 21:13  [ТС]     Найти в прямоугольной матрице подматрицу из единиц максимального размера. #7
А как вообще создать такой массив состоящий из 0 и 1?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.05.2012, 21:23     Найти в прямоугольной матрице подматрицу из единиц максимального размера.
Еще ссылки по теме:
C++ В матрице заданного размера найти среднее арифметическое
В матрице заданного размера найти произведение элементов обозначенных звездочкой C++
C++ В квадратной матрице найти сумму минимального и максимального элементов главной диагонали
В матрице заданного размера найти сумму элементов на местах, обозначенных звездочкой C++
C++ В заданной матрице найти значение и номер максимального элемента (файловый ввод/вывод)

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

Или воспользуйтесь поиском по форуму:
MrGluck
Модератор
Эксперт CЭксперт С++
6988 / 4159 / 592
Регистрация: 29.11.2010
Сообщений: 11,039
19.05.2012, 21:23     Найти в прямоугольной матрице подматрицу из единиц максимального размера. #8
Цитата Сообщение от korsarqa Посмотреть сообщение
А как вообще создать такой массив состоящий из 0 и 1?
Можешь с файла считать, можешь с клавы ввести, можешь проинициализировать при объявлении массива, можешь заполнить СЧ:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <ctime>
 
int main()
{
    srand (time(0) );
    const int M = 3;
    int arr[M][M];
    for (int i=0; i < M; i++)
    {
        for (int j=0; j < M; j++)
        {
           arr[i][j] = rand() % 2; 
           std::cout<< arr[i][j]<< " ";
        }   
        std::cout<< std::endl;
    }   
    return 0;
}
Yandex
Объявления
19.05.2012, 21:23     Найти в прямоугольной матрице подматрицу из единиц максимального размера.
Ответ Создать тему
Опции темы

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