VPF::[C++]Сотрировка двумерного массива

SMedv

Дата 20.6.2007, 13:33 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 7.5.2007

Репутация: нет
Всего: нет

Буду очень признателен , если поможите сделать прогу.
Дан двумерный массив n*m , нужно отсортировать его методот простых вставок по убыванию и расположить элементы по диагогалям , вот так :

исходный массив:           такой должен получиться :
       7  8  4                                   9  7  4
       1  3  9                                   8  5  2
       2  5  6                                   6  3  1

Помогите пожалуйста !   smile

Dov

Дата 20.6.2007, 19:16 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Опять нужно просить кого-нить перевести на русский язык. smile

zkv, у тебя не плохо получается, может подсобишь? smile

--------------------

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

zkv

Дата 20.6.2007, 19:52 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 21
Всего: 92

Да вроде тут не сложно: растягиваем двумерный массив в вектор (неважно как), сортируем методом простых вставок по убыванию, затем элементы вектора распихиваем в исходную матрицу в порядке указанным автором (те параллельно побочной диагонали, начиная с элемента (0,0), в направлении снизу-вверх). smile

Вероятно растягивать в вектор необязательно, и сортировать можно прям на месте - над этим надо подумать.

Dov

Дата 20.6.2007, 20:24 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Цитата(zkv @ 20.6.2007, 19:52

)

(те параллельно побочной диагонали, начиная с элемента (0,0), в направлении снизу-вверх).

Вот это не понял. smile

--------------------

zkv

Дата 21.6.2007, 01:14 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 21
Всего: 92

Цитата(Dov @ 20.6.2007, 20:24

)

Вот это не понял. smile

эх, не сложилась карьера переводчика smile

попробую себя в качестве программера. (немного не выдержал стиль и нет последовательности в действиях, не берите с меня пример, видящие человеки smile

)

Код


#include<iostream>
#include<iomanip>

typedef float ELEM_T;

const int g_nRows = 3;
const int g_nCols  = 5;

ELEM_T g_matrix[g_nRows][g_nCols] = 
{
    { 7,  8,  4, 10, 12},
    { 1,  3,  9, 11, 14 },   
    { 2,  5,  6, 0, 13 }
};

void GetNextDiagPos( int *pnRow, int *pnCol );
void InsertSort(ELEM_T **a, int lb, int ub);
void PrintMatrix();

int main()
{
    const int nNumElems = g_nCols*g_nRows;
    ELEM_T *arrpEl[nNumElems];    
    
    for( int nElem = 0; nElem < nNumElems; ++nElem )
    {
        int nRow = 0, nCol = 0;
        GetNextDiagPos( &nRow, &nCol );
        arrpEl[ nElem ] = &g_matrix[nRow][nCol];
    }

    std::cout<<"\nInitial matrix:\n";
    PrintMatrix();        

    InsertSort( arrpEl, 0, nNumElems );

    std::cout<<"\nResult matrix:\n";
    PrintMatrix();

    std::cout<<"\nPress <Enter> to exit...";
    std::cin.get();
}

void GetNextDiagPos( int *pnRow, int *pnCol )
{
    static int s_nRow = 0, s_nCol = 0, s_nColPlusRow = 0;
    *pnRow = s_nRow;
    *pnCol = s_nCol;
    if( (s_nCol == s_nColPlusRow) || (s_nCol == g_nCols-1) || (s_nRow == 0) )
    {
        ++s_nColPlusRow;
        s_nRow = ( s_nColPlusRow < g_nRows ) ? s_nColPlusRow : g_nRows-1;
        s_nCol = s_nColPlusRow - s_nRow;    
    }
    else 
    {
        --s_nRow;
        ++s_nCol;
    }
}

void InsertSort(ELEM_T **a, int lb, int ub ) //в функцию даже не вникал, нагло передрал из ссылки 
//приведенной выше (вернее давно вникал, а сейчас позабыл, а врубаться не хочется, да и не зачем :))
{
    ELEM_T t;
    int i, j;

   /***********************
    * сортируем a[lb..ub] *
    ***********************/
    for (i = lb ; i < ub; i++) {
        t = *a[i];

        /* Сдвигаем элементы вниз, пока */
        /*  не найдем место вставки.    */
        for (j = i-1; j >= lb && (*a[j] < t); j--)
            *a[j+1] = *a[j];

        /* вставка */
        *a[j+1] = t;
    }
}

void PrintMatrix()
{
    for( int nRow = 0; nRow < g_nRows; ++nRow )
    {
        for( int nCol = 0; nCol < g_nCols; ++nCol )
            std::cout<<std::setw(4)<<g_matrix[nRow][nCol];
        std::cout<<"\n";
    }
}

Dov

Дата 21.6.2007, 08:18 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

zkv,

Хоть и надурил, но красиво. smile

Как говорится, не важен способ, важен результат. smile

--------------------

mefager

Дата 23.6.2007, 11:50 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 14
Регистрация: 24.2.2007

Репутация: нет
Всего: нет

Цитата(zkv @ 21.6.2007, 01:14

)

немного не выдержал стиль и нет последовательности в действиях, не берите с меня пример, видящие человеки

Цитата(Dov @ 21.6.2007, 08:18

)

zkv,
Хоть и надурил, но красиво.
Как говорится, не важен способ, важен результат.

А в чём прикол? Можете объяснить? smile

Вродибы всё работает. smile

zkv

Дата 23.6.2007, 11:56 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 21
Всего: 92

Цитата(mefager @ 23.6.2007, 11:50

)

А в чём прикол? Можете объяснить?

ну немного нестандартно сделал...

mefager

Дата 23.6.2007, 12:45 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 14
Регистрация: 24.2.2007

Репутация: нет
Всего: нет

Цитата(zkv @ 23.6.2007, 11:56

)

ну немного нестандартно сделал...

А можно каким-то образом расшифровать эту загадочную фразу? smile

Ну хоть намекните.

zkv

Дата 23.6.2007, 15:41 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 21
Всего: 92

mefager, ну я не стал сортировать элементы в матрице, в вектор тоже не стал растягивать, а просто создал вектор указателей на элементы матрицы, притом нацелил их сразу в указанном задании порядке, потом просто отсортировал вектор по значениям элементов матрицы на которые указывают его (вектора) элементы.

Так лучше? smile

Лучше попробуй код разобрать, спрашивай, что непонятно, там один только сложный момент, эта функция:

Код


void GetNextDiagPos( int *pnRow, int *pnCol )
{
    static int s_nRow = 0, s_nCol = 0, s_nColPlusRow = 0;
    *pnRow = s_nRow;
    *pnCol = s_nCol;
    if( (s_nCol == s_nColPlusRow) || (s_nCol == g_nCols-1) || (s_nRow == 0) )
    {
        ++s_nColPlusRow;
        s_nRow = ( s_nColPlusRow < g_nRows ) ? s_nColPlusRow : g_nRows-1;
        s_nCol = s_nColPlusRow - s_nRow;    
    }
    else 
    {
        --s_nRow;
        ++s_nCol;
    }
}

она находит нужный порядок следования элементов в матрице. Сложновата получилась - сам ее немного побаиваюсь smile

Это сообщение отредактировал(а) zkv - 23.6.2007, 15:42

Dov

Дата 23.6.2007, 16:43 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Цитата(zkv @ 23.6.2007, 15:41

)

создал вектор указателей на элементы матрицы, притом нацелил их сразу в указанном задании порядке, потом просто отсортировал вектор по значениям элементов матрицы на которые указывают его (вектора) элементы

Да, именно это я и назвал "дуриловом". smile

Ведь изначально нужно было отсортировать исходную матрицу, а потом уже  расположить элементы матрицы по диагоналям.
zkv же, создав массив указателей на элементы матрицы, изменил порядок действий, сначала расположив указатели по диагоналям матрицы, а потом отсортировал их по значениям. Таким образом, конечный результат был достигнут "неправильным", но очень красивым способом.   smile

Ну, а я, используя наработки zkv, решил немного переделать эту прогу, с тем, что бы она работала в указанном автором темы порядке. То есть, сначала идёт сортировка элементов матрицы, а уже потом расположение элементов матрицы по диагоналям. В сущности, мне пришлось переделать только ф-цию GetNextDiagPos. Теперь она вычисляет позицию элемента в диагоналях матрицы и возвращает ссылку на него, после чего по этим ссылкам элементам матрицы присваиваются "новые" значения матрицы, предварительно отсортированные в этой же матрице, а потом сохранённые в одномерном массиве.
Вроде всё. smile

Код


#include <iostream.h>
#include <iomanip.h>

#define ROWS 3
#define COLS 5

int &   GetNextDiagPos (int  matr[][COLS], int& row, int& col, int& rowBeg, int& colBeg);
void    PrintMatrix    (int  matr[][COLS]);
void    InsertSort     (int* ar, int size);

int main()
{
    int matrix[ROWS][COLS] = {
        {7, 8, 4, 10, 12},
        {1, 3, 9, 11, 14},   
        {2, 5, 6, 15, 13}
    };    
    int arr[ROWS * COLS];
    int i, rowCur, colCur, rowStart, colStart;   
    
    cout << "\nInitial matrix:\n";
    PrintMatrix(matrix);        
    
    InsertSort(*matrix, ROWS * COLS);
    
    cout << "\nSorted matrix:\n";
    PrintMatrix(matrix);    
    
    for(i = 0; i < ROWS * COLS; i++)
        arr[i] = matrix[0][i];

    rowStart = rowCur = ROWS - 1;
    colStart = colCur = COLS - 1;    
    while(--i)
        GetNextDiagPos(matrix, rowCur, colCur, rowStart, colStart) = arr[i];
    
    cout << "\nResult matrix:\n";
    PrintMatrix(matrix);
    
    return 0;
}

int & GetNextDiagPos(int matr[][COLS], int& row, int& col, int& rowBeg, int& colBeg)
{
    if(row == ROWS || col == -1)
    {
        row = rowBeg;
        col = colBeg;
        row != 0 ? rowBeg = --row : colBeg = --col;    
    }        
    
    return matr[row++][col--];
}

void InsertSort(int* ar, int size)
{    
    int i, j, tmp;
    
    for (i = 1; i < size; i++)
    {
        tmp = ar[i];       
        for (j = i - 1; j >= 0 && (ar[j] < tmp); j--)
            ar[j + 1] = ar[j];       
        ar[j + 1] = tmp;
    }
}

void PrintMatrix(int matr[][COLS])
{
    for(int i = 0; i < ROWS; i++)
    {
        for( int j = 0; j < COLS; j++)
            cout << setw(4) << matr[i][j];
        cout<<"\n";
    }
}

--------------------

zkv

Дата 23.6.2007, 17:38 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Участник Клуба
Сообщений: 2133
Регистрация: 23.7.2006
Где: Санкт-Петербург

Репутация: 21
Всего: 92

Цитата(Dov @ 23.6.2007, 16:43

)

Таким образом, конечный результат был достигнут "неправильным", но очень красивым способом.

Пожалуй твой вариант проще для восприятия, что важнее всего в программе (мое мнение), так что будем считать твой вариант решением, а мой переводом задания smile

Dov

Дата 23.6.2007, 18:08 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Нет, zkv. Решением мы будем считать всё, что сгодится автору темы, независимо от способа решения. smile

Побольше решений!!!
Хороших и разных... smile

--------------------

mefager

Дата 24.6.2007, 07:44 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 14
Регистрация: 24.2.2007

Репутация: нет
Всего: нет

zkv, Dov. Вот теперь понятно, спасибо. smile

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »