VPF::Просмотр матрицы (возрастание+удаленность от (0,))

Hohhi

Дата 16.5.2009, 10:58 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 171
Регистрация: 25.2.2006
Где: Молдова

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

Здраствуйте! Необходимо реализовать ЭФФЕКТИВНЫЙ алгоритм прохода по двумерному массиву в порядке возрастания его элементов+ если имеется несколько минимальных элементов в порядке их удаленности их от левого верхнего элемента, то есть точки (0,0). То есть имея матрицу:
7 8 5 3
2 4 5 9
6 3 1 2
Пройти её должны в следующем порядке:
10 11 7 4
2 6 8 12
6 3 1 2

Пока что придумал только вариант в лоб, но он мне не нравится:

Код


int kolvo[1000]; // пусть в массиве будут кол-во вхождении каждого элемента
inc c[100][100]; //собственно матрица для поиска
//здесь заполняем массив kolvo, то есть в цикле увеличиваем соотв. элемент массива kol-vo

while(в kolvo есть не нули)
{
    while (kolvo[i])
    {
                  // идти параллельно главной диагонали в поиске kolvo[i]
                  при нахождении обработать и декрементировать kolvo[i]
    }
}

Опять же, идея далеко не эффективна, помогите оптимизировать

Это сообщение отредактировал(а) Hohhi - 16.5.2009, 10:58

nworm

Дата 16.5.2009, 19:25 (ссылка)

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

Загрузка ...

Опытный

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

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

а почему первый элемент 10?

Hohhi

Дата 16.5.2009, 19:37 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 171
Регистрация: 25.2.2006
Где: Молдова

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

nworm, первый элемент 1 в третьей строке и третьем столбце
а элемент 7 из первой строки и первого столбца необходимо пройти десятым

nworm

Дата 16.5.2009, 20:09 (ссылка)

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

Загрузка ...

Опытный

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

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

1) За один проход по массиву получаем упорядоченное множество

(ai,bi,Ri)

ai - номер элемента
bi - элемент
Ri - расстояние от левого верхнего угла.

(11,1,R1) (5,2,R2) (12,2,R3) (4,3,R4) (10,3,R5) (6,4,R6) (3,5,R7) (7,5,R8) (9,6,R9) (1,7,R10) (2,8,R11) (8,9,R12)

Структура этого множество - какое-нибудь дерево (или массив).

2) Идём по массиву от минимального bi к максимальному bi.
Итоговый массив формируем по формуле:
A[ai]=bi

Hohhi

Дата 16.5.2009, 20:55 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 171
Регистрация: 25.2.2006
Где: Молдова

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

Цитата

nworm, Итоговый массив формируем по формуле:
A[ai]=bi

может вот так ?

Код


A[i]=bi

да и потом цель не сфоримровать массив, а опираясь на него провести некие действия в соответствующем порядке.
Идея со структурой неплохая, была и у меня. Пожалуй, первое поле ai бесполезно, и лучше бы иметь в нем некую структуру с индексами элемента то, есть:
((3,3),1,R1) ((1,2),2,R2) ((3,4),2,R3)
тогда необходимость хранить расстояние исчезает. Далее, действительно, стоит, наверно отсортировать массив для элементов с одинаковыми bi. И пройти по элементам чётко по полученному массиву. Тоже не очень эффективно, но получше

Это сообщение отредактировал(а) Hohhi - 16.5.2009, 20:55

nworm

Дата 16.5.2009, 21:53 (ссылка)

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

Загрузка ...

Опытный

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

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

можно сортировать, можно вставки в древесные структуры пробовать, в зависимости от особенностей задачи

Hohhi

Дата 17.5.2009, 22:11 (ссылка)

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

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 171
Регистрация: 25.2.2006
Где: Молдова

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

Вот подошедший вполне вариант, написанный на скорую руку. Конечно, сортировка вставкой, совсем не лучшее, но тут она сойдёт. Кому надо, вот код:

Код


#include <iostream.h>
#include <conio.h>
int min(int value1, int value2)
{
     return ( (value1 < value2) ? value1 : value2);
}
class Matrix
{
    private:
        int m;
        int n;
    public:
    int** matr;
        Matrix(int, int);
        void Print_Matrix();
        void Initialize(int);
        void NUL();
        int Get_m()
        {
            return m;
        }
        int Get_n()
        {
            return n;
        }

        ~Matrix();

};

void Matrix::NUL()
{
    for (int i=0;i<m;i++)
        for (int j=0;j<n;j++)
            matr[i][j]=0;
}
Matrix::Matrix(int m,int n)
{
    this->m=m;
    this->n=n;
    matr=new int *[m];
    for(int i=0;i<n;i++)
        matr[i]=new int [n];

}
void Matrix::Initialize(int ml)
{
    int tmp_m=m, tmp_n=n;
    if (ml==1)
        tmp_n--;
    else if (! ml)
        tmp_m--;
    for (int i=0;i<tmp_m;i++)
        for (int j=0;j<tmp_n;j++)
        cin>>matr[i][j];
}
void Matrix::Print_Matrix()
{
    for (int i=0;i<m;i++)
        for (int j=0;j<n;j++)
    {
        cout<<matr[i][j]<<"  ";
        if (j==n-1)
            cout<<endl;
    }
}

Matrix::~Matrix()
{
            for (int i=0;i<m;i++)
                delete[] matr[i];
            delete[] matr;
}

struct Point {
    int i,j;
    int dist(){return i+j; }
};

struct info
{
    Point p;
    int element;
};

int main()
{
    int m,n;
    cout<<"Enter m:";
    cin>>m;
    cout<<"Enter n:";
    cin>>n;
    int* a=new int [m+1];
    int* b=new int [n+1];
    cout<<"Enter the elements of A:";
    for (int i=0;i<m;i++)
        cin>>a[i];
    cout<<"Enter the elements of B:";
    for (i=0;i<n;i++)
        cin>>b[i];
    int sumaj=0,sumbi=0;
    for (i=0;i<m;i++)
        sumaj+=a[i];
    for (i=0;i<n;i++)
        sumbi+=b[i];
    int more_less=-1;
    if (sumaj>sumbi)
    {
        b[n++]=sumaj-sumbi;
        more_less=1;
    }
    else if (sumaj<sumbi)
    {
        a[m++]=sumbi-sumaj;
        more_less=0;
    }
    Matrix x(m,n),c(m,n);
    x.NUL(); c.NUL();
    cout<<"Enter the matrix C:";
    c.Initialize(more_less);
    c.Print_Matrix();
    info arr[10000];   int k=0;
    for (i=0;i<c.Get_m();i++)
        for (int j=0;j<c.Get_n();j++)
        {
            arr[k].element=c.matr[i][j];
            arr[k].p.i=i;
            arr[k++].p.j=j;
        }
    for (j=1;j<k;j++)
    {
        info key=arr[j];
        i=j-1;
        while ((i>=0)&&( ((arr[i].element>key.element)&&(arr[i].element))||
                                         ( (arr[i].element==key.element)&&(arr[i].p.dist()>key.p.dist()) )))
            arr[i+1]=arr[i--];
        arr[i+1]=key;
    }
    for (j=0;j<k;j++)
    {
        cout<<arr[j].element<<" "<<arr[j].p.dist()<<endl;
    }
    for (j=0;j<k;j++)
    {
        int minimum=min(a[arr[j].p.i],b[arr[j].p.j]);
        a[arr[j].p.i]-=minimum;
        b[arr[j].p.j]-=minimum;
        x.matr[arr[j].p.i][arr[j].p.j]=minimum;
    }
    x.Print_Matrix();
    delete[] a;
    delete[] b;

}

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