Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [C++]Найти первые n максимальных элементов матрицы


Автор: Treod 2.1.2008, 23:49

Помогите плиз составить алгоритм по нахождению первых n максимальных элементов матрицы... Если есть возможность, выложите код на с++. Каким образом запоминать предыдущие макс. элементы? Заносить в массив и затем проверять? Помогите плиз!

Автор: orthrus 3.1.2008, 07:46
Если массив одномерный, то прога будет следующая:

Код

#include <iostream>

#define M 20 //кол-во элементов в матрице
#define N 3  //кол-во искомых макс. чисел

void print_mass(int* mass, int m) //фун-я печатающая массив
{
    for (int i = 0; i < m; ++i) std::cout << mass[i] << " ";
    std::cout << std::endl;
}

int find_max(int* mass, int m, int max) //функция ищущая макс. элемент который меньше max
{
    int t = 0;
    for (int i = 1; i < m; ++i){
        if (max > mass[i]) {
            if (t < mass[i]) t = mass[i];
        }
    }
    return t;
}

int main()
{
    int mass[M];
    int max[N];
    std::srand(time(0));
    for (int i = 0; i < M; ++i) mass[i] = std::rand()%500;
    print_mass(mass,M);

    max[0] = find_max(mass,M,1000);
    for (int i = 1; i < N; ++i)
        max[i] = find_max(mass,M,max[i-1]);
    print_mass(max,N);

    return 0;
}


Автор: Treod 4.1.2008, 19:02
У вас t присваивается значение 0. Но ведь максимальным элементом может быть и отрицательное число...

Автор: orthrus 4.1.2008, 19:10
Присвойте этой переменной отр. значение, например -1000.

Автор: mr.Anderson 4.1.2008, 19:19
orthrus, более правильный вариант при поиске минимума - выставить стартовое значение переменной как первый элемент массива.

Автор: PPS05 4.1.2008, 19:28
Да, но в данном случае t должно быть меньше max, не факт, что это первый элемент массива. Как вариант, выставить для t наименьшее возможное значение для данного типа. orthrus, а может проще отсортировать с помощью qsort?

Автор: Treod 4.1.2008, 20:13

Выставлять как самое наименьшее значение -1000 не вариант, ибо матрица может состоять из любых чисел... 
Выложите плиз универсальный рабочий вариант с коментами

Автор: PPS05 4.1.2008, 21:35
Вот, вроде работает.

Код


#include <stdio.h>
#include <stdlib.h>

// Размеры матрицы...
const int N1 = 4, N2 = 4;
// ...и сама матрица
int F[N1][N2] = 
{
    {1, 5, 9, -90},
    {98, 76, -9, 0},
    {87, 87, 34, 0},
    {0, 76, 87, 98}
};

// Количество первых максимальных элементов
const int K = 3;

// Временный массив, в нем запомним все элементы матрицы
int T[N1*N2];

// Эта функция будет передана qsort как параметр
// Ее задача - сравнить два элемента
int compareFunc(const void * a, const void * b)
{
    if ( *((int*)a) < *((int*)b) )
        return 1;
    if ( *((int*)a) == *((int*)b) )
        return 0;
    return -1;
}

int main(void)
{
    int i, j;
    for (i=0; i<N1; i++)
        for (j=0; j<N2; j++)
            // Здесь мы хотим запомнить все элементы матрицы в массив T
            T[i*N2 + j] = F[i][j];
    // Сортируем...
    qsort(T, N1 * N2, sizeof(T[0]), compareFunc);
    // Дальше - выводим (решение на случай, если нужно ИСКЛЮЧАТЬ
    // повторяющиеся элементы
    // Будем помещать элементы в тот же массив T
    // Первый элемент оставляем само собой
    // В j храним номер, куда будем помещать следующее число
    j = 1;
    for (i=1; (i<N1*N2) && (j<K); i++)
        // Здесь исключаем повторения
        if (T[i] != T[i-1])
            T[j++] = T[i];
    // А здесь просто вывод
    for (i=0; i<j; i++)
        printf("%d ", T[i]);

    return 0;
}

Автор: Treod 5.1.2008, 11:58
PPS05, огромнейшее спасибо... Как же я сразу не додумался, что проще отсортировать массив по убыванию и исключить повторения. Еще раз спасибо. Вопрос решен, тему можно закрыватьsmile

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)