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

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

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

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

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

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

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

Найти квадратную подматрицу максимального размера - C++
Ввести матрицу, которая состоит из 0 и 1. Найти в ней квадратную подматрицу максимального размера, элементы которой имеют значение 1. ...

В заданной матрице состоящей из нулей и единиц найти квадратную подматрицу, состоящую целиком из нулей - C++
Черный квадрат. В матрице состоящей из 0 и 1 найти квадрат заданного размера(квадратную подматрицу), состоящий целиком из нулей.

В матрице из нулей и единиц найти квадрат заданного размера, состоящую целиком из нулей - C++
В матрице A (m, n), которая состоит из нулей и единиц, найти квадрат заданного размера (квадратную подматрицу), состоящую целиком из нулей ...

Найти в матрице квадратную подматрицу - C++
дана матрица а(m,n) из 0 и 1. найти в ней квадратную подматрицу из одних единиц максимального размера.

В прямоугольной матрице размера m*n в каждой строке поменять местами первый и минимальный элементы. - C++
Помогите написать программу на языке Си В прямоугольной матрице размера m*n в каждой строке поменять местами первый и минимальный...

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

7
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.05.2012, 17:57 #2
ограничения по времени есть?
0
korsarqa
7 / 7 / 0
Регистрация: 06.12.2011
Сообщений: 170
17.05.2012, 20:11  [ТС] #3
Ну неделька максимум...
1
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.05.2012, 05:13 #4
Ограничения по времени выполнения программы есть?
0
korsarqa
7 / 7 / 0
Регистрация: 06.12.2011
Сообщений: 170
18.05.2012, 15:25  [ТС] #5
нету ограничения
0
valeriikozlov
Эксперт С++
4670 / 2496 / 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 максимальное значение площади
1
korsarqa
7 / 7 / 0
Регистрация: 06.12.2011
Сообщений: 170
19.05.2012, 21:13  [ТС] #7
А как вообще создать такой массив состоящий из 0 и 1?
0
MrGluck
Модератор
Эксперт CЭксперт С++
7418 / 4533 / 673
Регистрация: 29.11.2010
Сообщений: 12,287
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;
}
1
19.05.2012, 21:23
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.05.2012, 21:23
Привет! Вот еще темы с ответами:

Усовершенствовать алгоритм Рабина-Карпа, чтобы он искал символьную подматрицу в символьной матрице - C++
У меня есть этот алгоритм. Кто знает, как усовершенствовать его, чтобы он искал символьную подматрицу m * m в символьной матрицы n * n, при...

В матрице заданного размера найти среднее арифметическое - C++
Найти среднее арифметическое элементов(на местах обозначенные звездочкой) в двумерном массиве 8 на 7. - - - - - - - - - - - - - - - -...

В матрице заданного размера найти произведение элементов обозначенных звездочкой - C++
Найти произведение элементов(на местах обозначенные звездочкой) в двумерном массиве 7 на 7. * - - - - - * - * - - - * - - - * - * - -...

В квадратной матрице найти сумму минимального и максимального элементов главной диагонали - C++
В квадратной матрице найти сумму минимального и максимального элементов главной диагонали. Добавлено через 3 часа 13 минут Помогите...


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

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

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