Помогите плиз с алгоритмом проги (нужно отсортировать матрицу)

@Валентин^_^ · Регистрация: 15.10.2009

Задача: Характеристикой столбца целочисленной матрицы назовём сумму модулей его отрицательных нечётных элементов. Переставляя столбцы заданной матрицы, расположить их в соответствии с ростом характеристик.

Помогите плиз с алгоритмом, прогу-то сам напишу...)

Вот допустим матрица такая:

C++

int mas[n][m] = {
 {1, 2, 3, 2, -66},
{-2, -1, 2, 1, -99},
{0, 7, 3, -4, -95},
{-1, -1, -10, -15, 1},
{0, 8, 9, 3, 2},
{1, 2, 3, 4, 0} 
};

Посчитал характеристики вручную, суммы модулей нечетных эл-тов в столбцах: 0, 0, 0, 4, 161

КАК мне расставить столбцы матрицы??

Буду сильно благодарен за подсказку!)

@~~Сыроежка~~ · 17.10.2011, 21:16

Сообщение от Валентин^_^

Задача: Характеристикой столбца целочисленной матрицы назовём сумму модулей его отрицательных нечётных элементов. Переставляя столбцы заданной матрицы, расположить их в соответствии с ростом характеристик.

Помогите плиз с алгоритмом, прогу-то сам напишу...)

Вот допустим матрица такая:

C++

int mas[n][m] = {
 {1, 2, 3, 2, -66},
{-2, -1, 2, 1, -99},
{0, 7, 3, -4, -95},
{-1, -1, -10, -15, 1},
{0, 8, 9, 3, 2},
{1, 2, 3, 4, 0} 
};

Посчитал характеристики вручную, суммы модулей нечетных эл-тов в столбцах: 0, 0, 0, 4, 161

КАК мне расставить столбцы матрицы??

Буду сильно благодарен за подсказку!)

Лично я не понял, почему характеристика первого столбца равна 0. В С и С++ строки и столбцы нумеруются, начиная с нуля.

Начните с того, что напишите код, подсчитывающий характеристику столбца.

@Валентин^_^ · 17.10.2011, 21:50 **[ТС]**

Знаю, что нумерация с нуля) просто для удобства думал будет лучше, если с первого, не суть вобщем..

Таак, написал код, который бы посчитал характеристики:

C++

int haract[m];
for(int j = 0; j < m; j++)
{
    haract[j] = 0;
    for(int i = 1; i < n; i+=2)
    {
        if(mas[i][j] < 0)
            haract[j] += abs(mas[i][j]);
    }
}
 
cout << endl;
for(int k = 0; k < m; k++)
    cout << haract[k] << "\t";
cout << endl;

Вот дальше хз как

valeriikozlov · 17.10.2011, 21:59

Сообщение от Валентин^_^

Задача: Характеристикой столбца целочисленной матрицы назовём сумму модулей его отрицательных нечётных элементов.

Валентин^_^, а Вы считаете элементы стоящие на нечетной позиции.
все-таки это разные вещи.

@Валентин^_^ · 17.10.2011, 22:10 **[ТС]**

Я так понял, что если элемент находится на нечетной позиции - то есть это 1,3 и 5 строки и, если он отрицательный, то посчитать характеристику. Так вышеприведенный код и работает, в итоге для данной матрицы получаем: 3, 2, 10, 15 и 99. ...или я сам не въехал в задание...

@aeshes · 17.10.2011, 22:49

Валентин^_^, в вашем задании не важно на каком месте стоит число, главное, чтобы оно было отрицательное и нечетное, т.е. в приведенной вами матрице в первом столбце - это число -1, соответственно, и характеристика его равна 1; во втором -1 и -1 (характеристика 2) и т.д.

@Валентин^_^ · 17.10.2011, 23:01 **[ТС]**

aeshes, Спс, суть задания понял)

код исправил

C++

int haract[m] = {0, 0, 0, 0, 0};
for(int j = 0; j < m; j++)
    for(int i = 1; i < n; i++)
        if((mas[i][j] < 0) && (mas[i][j] % 2 != 0))
            haract[j] += abs(mas[i][j]);

Как опираясь на массив характеристик, переставить столбцы матрицы?

@aeshes · 17.10.2011, 23:11

Валентин^_^, самый простой подход - это завести еще один массив int index [5] ={0,1,2,3,4}, который хранит индексы столбцов в исходной матрице.
Теперь сортируете массив характеристик по возрастанию. Как только переставляете в нем местами два элемента, такую же перестановку делаете и в массиве index.
Затем в результирующий массив записываете строки исходного массива в том порядке, в котором получились индексы в массиве index.
Например, у вас будут характеристики 3 2 8 7 1
и массив индексов 0 1 2 3 4
После сортировки характеристики станут 1 2 3 7 8, а массив индексов 4 1 0 3 2
Именно в таком порядке и заполняете столбики в результирующей матрице: сначала 4-й, потом 1-й и т.д.

@Валентин^_^ · 18.10.2011, 00:26 **[ТС]**

aeshes,
написал функцию, которая сортирует массив характеристик и выстраивает массив индексов

C++

void Sort(int k, int x[], int y[]) 
{
    int i, j, buf, buf2;
 
    for(i = k - 1; i > 0; i--)
        for(j = 0; j < i; j++)
            if(x[j] > x[j+1])
            {
                buf = x[j];
                x[j] = x[j + 1];
                x[j + 1] = buf;
                
                buf2 = j;
                y[j] = j + 2;
                y[j + 1] = buf2;
            }
}
...
Sort(m, haract, index);

Имею массив индексов:2, 0, 1, 3, 4

..не получается столбцы расставить в соответствии с индексами,... если не затруднит, можно так же на словах?)

@aeshes · 18.10.2011, 15:08

Валентин^_^, насколько я поняла, x - это у вас матрица характеристик, y - матрица индексов. В ней обмен должен быть такой же, как в матрице х, т.е.

C++

for(i = k - 1; i > 0; i--)
                for(j = 0; j < i; j++)
                        if(x[j] > x[j+1])
                        {
                                buf = x[j];
                                x[j] = x[j + 1];
                                x[j + 1] = buf;
                                
                                buf = y[j];
                                y[j] = y[j+1];
                                y[j + 1] = buf;
                        }

Перед этим матрица y должна быть заполнена

C++

1 2	for(j=0;j<m;j++) y[j]=j;

Теперь вы должны завести матрицу res такого же размера, как исходная матрица - res[n][m] и в цикле копировать туда исходную матрицу по столбцам в соответствии с матрицей индексов. Примерно так

C++

int ind;
for(j=0;j<m;j++)
{
   ind=index[j];
   for(i=0;i<n;i++)
       res[i][j]=mas[i][ind];
}

P.S. я воспользовалась обозначениями res[n][m], как и у вас, но вообще говоря, вы должны выделять память под массив динамически, если n и m у вас не являются константами

valeriikozlov · 18.10.2011, 16:05

aeshes, слишком много дополнительных массивов. Хватит начального массива mas[][] и массива haract[].
После заполнения значениями массива haract[], делаем сортировку выбором в массиве haract[], одновременно меняя точно также столбцы в массиве mas[][].

@aeshes · 18.10.2011, 19:21

valeriikozlov, можно и так, я не говорила, что это лучший способ, я сказала - самый простой

@Валентин^_^ · 18.10.2011, 22:41 **[ТС]**

В общем вот что получилась:

C++

#include "stdafx.h"
#include <clocale>
#include <windows.h>
#include <iostream>
 
using namespace std;
 
void Sort(int k, int x[], int y[]); //ф-ия сортировки
 
int main()
{
    setlocale(LC_ALL, "russian");
 
    const int n = 6;
    const int m = 5;
    int mas[n][m] = { {1, 2, 3, 2, -66},
                    {-2, -1, 2, 1, -99},
                    {0, 7, 3, -4, -95},
                    {-1, -1, -10, -15, 1},
                    {0, 8, 9, 3, 2},
                    {1, 2, 3, 4, 0} };
 
    cout << "Исходная матрица:" << endl;
    for(int i = 0; i < n; i++, cout << endl)
        for(int j = 0; j < m; j++)
            cout << mas[i][j] << "\t";
 
 
    int haract[m] = {0, 0, 0, 0, 0}; //характеристика
 
    for(int j = 0; j < m; j++)
        for(int i = 1; i < n; i++)
            if((mas[i][j] < 0) && (mas[i][j] % 2 != 0))
                haract[j] += abs(mas[i][j]);
 
    int index[m] = {0, 1, 2, 3, 4}; //индексы столбцов
 
    int result[n][m]; //результирующая матрица
 
    Sort(m, haract, index); //отсортируем индексы столбцов с учетом хар-ик
 
    int ind;
    for(int j = 0; j < m; j++)
    {
       ind = index[j];
       for(int i = 0; i < n; i++)
           result[i][j] = mas[i][ind];
    }
 
    cout << endl << "Отсортированная матрица: " << endl;
        for(int i = 0; i < n; i++, cout << endl)
        for(int j = 0; j < m; j++)
            cout << result[i][j] << "\t";
 
    cout << endl << endl;
 
    system("PAUSE");
        return 0;
}
 
void Sort(int k, int x[], int y[]) 
{
    int buf;
 
    for(int i = k - 1; i > 0; i--)
        for(int j = 0; j < i; j++)
            if(x[j] > x[j + 1])
            {
                buf = x[j];
                x[j] = x[j + 1];
                x[j + 1] = buf;
 
                buf = y[j];
                                y[j] = y[j + 1];
                                y[j + 1] = buf;
            }
}

Прога работает правильно, спс всем=)

Только все равно сортировку нужно будет вынести в отдельную функцию, попробовал передать двумерный массив в ф-ию также, как и одномерный.. но так нельзя. Над этим буду еще думать..

@aeshes 446 / 209 / 21 Регистрация: 07.10.2011 Сообщений: 462
	18.10.2011, 19:21	12
	valeriikozlov, можно и так, я не говорила, что это лучший способ, я сказала - самый простой 0

valeriikozlov 4710 / 2535 / 753 Регистрация: 18.08.2009 Сообщений: 4,550
	17.10.2011, 21:59	4
	Сообщение от Валентин^_^ Задача: Характеристикой столбца целочисленной матрицы назовём сумму модулей его отрицательных нечётных элементов. Валентин^_^, а Вы считаете элементы стоящие на нечетной позиции. все-таки это разные вещи. 0

@Валентин^_^ 25 / 25 / 11 Регистрация: 15.10.2009 Сообщений: 185
	17.10.2011, 22:10 [ТС]	5
	Я так понял, что если элемент находится на нечетной позиции - то есть это 1,3 и 5 строки и, если он отрицательный, то посчитать характеристику. Так вышеприведенный код и работает, в итоге для данной матрицы получаем: 3, 2, 10, 15 и 99. ...или я сам не въехал в задание... 0

@aeshes 446 / 209 / 21 Регистрация: 07.10.2011 Сообщений: 462
	17.10.2011, 22:49	6
	Валентин^_^, в вашем задании не важно на каком месте стоит число, главное, чтобы оно было отрицательное и нечетное, т.е. в приведенной вами матрице в первом столбце - это число -1, соответственно, и характеристика его равна 1; во втором -1 и -1 (характеристика 2) и т.д. 0

@aeshes 446 / 209 / 21 Регистрация: 07.10.2011 Сообщений: 462
	17.10.2011, 23:11	8
	Валентин^_^, самый простой подход - это завести еще один массив int index [5] ={0,1,2,3,4}, который хранит индексы столбцов в исходной матрице. Теперь сортируете массив характеристик по возрастанию. Как только переставляете в нем местами два элемента, такую же перестановку делаете и в массиве index. Затем в результирующий массив записываете строки исходного массива в том порядке, в котором получились индексы в массиве index. Например, у вас будут характеристики 3 2 8 7 1 и массив индексов 0 1 2 3 4 После сортировки характеристики станут 1 2 3 7 8, а массив индексов 4 1 0 3 2 Именно в таком порядке и заполняете столбики в результирующей матрице: сначала 4-й, потом 1-й и т.д. 1

valeriikozlov 4710 / 2535 / 753 Регистрация: 18.08.2009 Сообщений: 4,550
	18.10.2011, 16:05	11
	aeshes, слишком много дополнительных массивов. Хватит начального массива mas[][] и массива haract[]. После заполнения значениями массива haract[], делаем сортировку выбором в массиве haract[], одновременно меняя точно также столбцы в массиве mas[][]. 0