VPF::[C++]Найти первые n максимальных элементов матрицы

Treod

Дата 2.1.2008, 23:49 (ссылка)

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

Загрузка ...

Бывалый

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

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

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

orthrus

Дата 3.1.2008, 07:46 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 400
Регистрация: 30.10.2007
Где: г. Усть-Илимск(Ир кутская обл.)

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

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

Код


#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;
}

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

У того, кто ничего не делает, всегда много помощников.© Л.Н. Толстой
user posted image

Treod

Дата 4.1.2008, 19:02 (ссылка)

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

Загрузка ...

Бывалый

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

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

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

orthrus

Дата 4.1.2008, 19:10 (ссылка)

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

Загрузка ...

Опытный

Присвойте этой переменной отр. значение, например -1000.

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

У того, кто ничего не делает, всегда много помощников.© Л.Н. Толстой
user posted image

mr.Anderson

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

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

Загрузка ...

iOS Lead Developer

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

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

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

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

PPS05

Дата 4.1.2008, 19:28 (ссылка)

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

Загрузка ...

Опытный

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

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

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

Это сообщение отредактировал(а) PPS05 - 4.1.2008, 19:33

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

Ушел с форума и не вернулся.

Treod

Дата 4.1.2008, 20:13 (ссылка)

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

Загрузка ...

Бывалый

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

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

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

PPS05

Дата 4.1.2008, 21:35 (ссылка)

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

Загрузка ...

Опытный

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

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

Вот, вроде работает.

Код



#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 (ссылка)

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

Загрузка ...

Бывалый

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

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

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

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