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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 5.00
Kemsit
 Аватар для Kemsit
4 / 4 / 1
Регистрация: 07.06.2009
Сообщений: 62
25.12.2009, 22:14     Найти все прямоугольные подмассивы в матрице #1
Как найти все прямоугольные подмассивы в массиве A[i][j]?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.12.2009, 22:14     Найти все прямоугольные подмассивы в матрице
Посмотрите здесь:

C++ Найти в матрице первую строку, все элементы которой положительны
Найти в матрице первую строку, все элементы которой положительны C++
C++ дана целочисленная матрица A , размером а х м, найти в матрице первую строку, все элементы которой равны нолю, Умножить элементы столбца с таким же н
В матрице найти количество строк, у которых все нули C++
В матрице найти количество строк, у которых все нули C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.12.2009, 22:30     Найти все прямоугольные подмассивы в матрице #2
Kemsit, Вам нужно найти их кол-во или вывести все на экран?
Kemsit
 Аватар для Kemsit
4 / 4 / 1
Регистрация: 07.06.2009
Сообщений: 62
25.12.2009, 22:31  [ТС]     Найти все прямоугольные подмассивы в матрице #3
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Kemsit, Вам нужно найти их кол-во или вывести все на экран?
Вообще задание у меня следующее. Дан массив A[N,M]. Необходимо найти максимальную сумму элементов прямоугольного подмассива по всем возможным прямоугольным подмассивам.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.12.2009, 22:33     Найти все прямоугольные подмассивы в матрице #4
Kemsit, Во как? тогда ждите
Kemsit
 Аватар для Kemsit
4 / 4 / 1
Регистрация: 07.06.2009
Сообщений: 62
25.12.2009, 22:33  [ТС]     Найти все прямоугольные подмассивы в матрице #5
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Kemsit, Во как? тогда ждите
О, спасибо заранее. Жду.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.12.2009, 22:50     Найти все прямоугольные подмассивы в матрице #6
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
#include <iostream.h>
#include <windows.h>
 
int main ()
{
    int **mas, n, m, i,j, temp, i_start, i_end, j_start, j_end, i1, i2, j1, j2, sum;
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    cout<<"Ââåäèòå êîëè÷åñòâî ñòðîê Г¬Г*òðèöû: "<< endl;
    cin>>n;
    mas=new int*[n];
    cout<<"Ââåäèòå êîëè÷åñòâî ñòðîê Г¬Г*òðèöû: "<< endl;
    cin>>m; 
    for(i=0; i<n; i++)
       mas[i]=new int[m];
    cout<<"Ââåäèòå ýëåìåГ*ГІГ» Г¬Г*òðèöû: "<< endl;
    for(i=0; i<n; i++)
       for(j=0; j<m; j++)
       {
          cout<<"["<<i<<"]["<<j<<"]= ";
          cin>>mas[i][j];
       }
        cout<<"èñõîäГ*Г*Гї Г¬Г*òðèöГ*"<<endl;
    for(i=0; i<n; i++)
        {
       for(j=0; j<m; j++)
       {
           cout.width(4);
          cout<<mas[i][j];
       }
          cout<<endl;
        }
    sum=mas[0][0];
    for(i1=0; i1<n-1; i1++)
        for(i2=0; i2<n; i2++)
            for(j1=0; j1<n-1; j1++)
                for(j2=0; j2<n; j2++)
                {
                    temp=0;
                    for(i=i1; i<=i2; i++)
                        for(j=j1; j<=j2; j++)
                            temp+=mas[i][j];
                    if(sum<temp)
                    {
                        sum=temp;
                        i_start=i1;
                        i_end=i2;
                        j_start=j1;
                        j_end=j2;
                    }
                }
    if(sum!=mas[0][0])
    {
        cout<<"ÑóììГ* Г°Г*ГўГ*Г* "<<sum<<endl;
        cout<<"ÝëåìåГ*ГІ Г¬Г*Г±Г±ГЁГўГ*: "<<endl;
        for(i=i_start; i<=i_end; i++)
        {
            for(j=j_start; j<=j_end; j++)
            {
                cout.width(4);
                cout<<mas[i][j];
            }
            cout<<endl;
        }
    }
    else
    {
        cout<<"ÑóììГ* Г°Г*ГўГ*Г* "<<sum<<endl;
        cout<<"ÝëåìåГ*ГІ Г¬Г*Г±Г±ГЁГўГ*: "<<endl;
        cout<<mas[0][0]<<endl;
    } 
    return 0; 
}
Kemsit
 Аватар для Kemsit
4 / 4 / 1
Регистрация: 07.06.2009
Сообщений: 62
25.12.2009, 22:58  [ТС]     Найти все прямоугольные подмассивы в матрице #7
Спасибо, но такая проблемка - я взял 3*4 матрицу, заполнил от 1 до 12. И он выдал квадратную матрицу, сумма элементов которой 54. А там можно взять квадратную матрицу, сумма элементов 63
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.12.2009, 23:03     Найти все прямоугольные подмассивы в матрице #8
Kemsit, Давайте полный пример
Kemsit
 Аватар для Kemsit
4 / 4 / 1
Регистрация: 07.06.2009
Сообщений: 62
25.12.2009, 23:10  [ТС]     Найти все прямоугольные подмассивы в матрице #9
К примеру ввожу квадратную матрицу
1 2 3
4 5 6
7 8 9
Прога выдаёт:
Элемент
1 2 3
4 5 6
7 8 9
Сумма 45,
А должен быть прямоуг. подмассив с наиб. суммой элементов тоесть
4 5 6
7 8 9
сумма 39
По моему так.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.12.2009, 23:13     Найти все прямоугольные подмассивы в матрице #10
Так, сам нашел, ошибка была.
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
#include <iostream.h>
#include <windows.h>
 
int main ()
{
    int **mas, n, m, i,j, temp, i_start, i_end, j_start, j_end, i1, i2, j1, j2, sum;
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    cout<<"Ââåäèòå êîëè÷åñòâî ñòðîê Г¬Г*òðèöû: "<< endl;
    cin>>n;
    mas=new int*[n];
    cout<<"Ââåäèòå êîëè÷åñòâî ñòðîê Г¬Г*òðèöû: "<< endl;
    cin>>m; 
    for(i=0; i<n; i++)
       mas[i]=new int[m];
    cout<<"Ââåäèòå ýëåìåГ*ГІГ» Г¬Г*òðèöû: "<< endl;
    for(i=0; i<n; i++)
       for(j=0; j<m; j++)
       {
          cout<<"["<<i<<"]["<<j<<"]= ";
          cin>>mas[i][j];
       }
        cout<<"èñõîäГ*Г*Гї Г¬Г*òðèöГ*"<<endl;
    for(i=0; i<n; i++)
        {
       for(j=0; j<m; j++)
       {
           cout.width(4);
          cout<<mas[i][j];
       }
          cout<<endl;
        }
    sum=mas[0][0];
    for(i1=0; i1<n; i1++)
        for(i2=0; i2<n; i2++)
            for(j1=0; j1<m; j1++)
                for(j2=0; j2<m; j2++)
                {
                    temp=0;
                    for(i=i1; i<=i2; i++)
                        for(j=j1; j<=j2; j++)
                            temp+=mas[i][j];
                    if(sum<temp)
                    {
                        sum=temp;
                        i_start=i1;
                        i_end=i2;
                        j_start=j1;
                        j_end=j2;
                    }
                }
    if(sum!=mas[0][0])
    {
        cout<<"ÑóììГ* Г°Г*ГўГ*Г* "<<sum<<endl;
        cout<<"ÝëåìåГ*ГІ Г¬Г*Г±Г±ГЁГўГ*: "<<endl;
        for(i=i_start; i<=i_end; i++)
        {
            for(j=j_start; j<=j_end; j++)
            {
                cout.width(4);
                cout<<mas[i][j];
            }
            cout<<endl;
        }
    }
    else
    {
        cout<<"ÑóììГ* Г°Г*ГўГ*Г* "<<sum<<endl;
        cout<<"ÝëåìåГ*ГІ Г¬Г*Г±Г±ГЁГўГ*: "<<endl;
        cout<<mas[0][0]<<endl;
    } 
    return 0; 
}
Добавлено через 1 минуту
Кстати потестируйте и с отрицательными числами, что бы полностью убедиться
Kemsit
 Аватар для Kemsit
4 / 4 / 1
Регистрация: 07.06.2009
Сообщений: 62
25.12.2009, 23:15  [ТС]     Найти все прямоугольные подмассивы в матрице #11
Суммирует он нормально, проверил. Но вот находит всегда квадратную матрицу. А должен прямоугольную...
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.12.2009, 09:14     Найти все прямоугольные подмассивы в матрице #12
Цитата Сообщение от Kemsit Посмотреть сообщение
Суммирует он нормально, проверил. Но вот находит всегда квадратную матрицу. А должен прямоугольную...
Нет, он находит такую матрицу (она получится или квадратная или прямоугольная), у которой сумма элементов наибольшая.
Например ввожу такую матрицу (3*4):
-20 12 10 6
4 20 13 -1
2 -30 -1 -2
Выводит такую:
12 10 6
20 13 -1
Если у Вас не так получается, то напишите здесь пример вводимой матрицы при которой получается неправильный результат.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.12.2009, 16:03     Найти все прямоугольные подмассивы в матрице
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Kemsit
 Аватар для Kemsit
4 / 4 / 1
Регистрация: 07.06.2009
Сообщений: 62
26.12.2009, 16:03  [ТС]     Найти все прямоугольные подмассивы в матрице #13
Всё, всё работает, спасибо большое!
Yandex
Объявления
26.12.2009, 16:03     Найти все прямоугольные подмассивы в матрице
Ответ Создать тему
Опции темы

Текущее время: 21:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru