Модераторы: bsa

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> нахождение максимального из повторяющихся элем. 
V
    Опции темы
LeD4eG
Дата 25.10.2010, 21:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

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



здравствуйте!
помогите, пожалуйста, с реализацией мысли. задача состоит в следующем: найти максимальный элемент из повторяющихся более одного раза в матрице из целых чисел произвольного размера.
так как статус на форуме "новичок" соответствует моему статусу в С++, мной был получен следующий метод решения:
1. создаём в динамической памяти двумерный массив, вводим элементы и бла-бла-бла;
2. находим максимальный, проходим по матрице, если он встречается ещё раз, то он и будет максимальным из повторяющихся.

но есть две проблемы:
1) это, мягко скажем, не совсем то, что требовалось в задаче;
2) я не знаю, что делать, если этот максимальный элемент второй раз не встретиться.....

есть ещё соображения:
1. преобразовать матрицу в одномерный массив;
2.  проходим каждый элемент и считаем сколько он раз встречается.
3. элементы, которые встречаются один раз удаляем (в ноль), повторения оставшихся элементов тоже удаляем. находим максимальный из оставшихся.

также был такой план:
1. пройтись по матрице, найти повторяющиеся элементы и сохранить их в одномерный массив;
2. найти максимальный в одномерном массиве.

но для второго и третьего варианта у меня не хватает опыта. чуть позже я кину код своих идей. но эти попытки провалились. читал схожие темы на нашем форуме. но создание векторов для меня слишком далеко.....поэтому не смог применить эти знания. 
помогите  smile 
--------------------
Ты не успел стать для кого-то главным, кому-то очень нужным.....
PM MAIL   Вверх
Crafty
Дата 25.10.2010, 22:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Цитата(LeD4eG @  25.10.2010,  22:46 Найти цитируемый пост)
преобразовать матрицу в одномерный массив;
 
Не нужно ничего преобразовывать матрица фактически и есть одномерный массив.
Теперь просто сортируем массив по убыванию и ищем повторяющиеся числа, если такие есть то выходим из цикла.
PM MAIL   Вверх
vnf
Дата 25.10.2010, 22:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

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



Вариант 3 
Код

int max()
{
    #define SIZE 10 
    int array2[SIZE*SIZE]; // это матрица с числами
    int array1[SIZE*SIZE]; // массив для повторяющихся, размер с запасом
    // ищем в array2 повторяющиеся и сохраняем в array1
    int k=0;
    for(int i=0;i<SIZE*SIZE;++i)
    {
         for(int j=i+1;j<SIZE*SIZE;++j) 
             if(array2[i]==array2[j])
             {
                array1[k] = array2[i];
                ++k;
                break;
             }
    }
    // ищем максимальный в array1
    int max = 0;
    for(int i=0;i<=k;++i)
    {
        if(array1[i]>max)max = array1[i];
    }
    return max;
}



Это сообщение отредактировал(а) vnf - 25.10.2010, 22:22
PM MAIL   Вверх
djamshud
Дата 25.10.2010, 22:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Пердупержденный
***


Профиль
Группа: Завсегдатай
Сообщений: 1655
Регистрация: 23.11.2009

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



Можно перевести фразу "максимальный элемент из повторяющихся более одного раза в матрице" на более русский язык?

Добавлено через 3 минуты и 3 секунды
Если речь о "последнем" (крайнем правом нижнем) максимальным, то все просто:
Код


int *max=&matrix[0][0]
for(...)
for(...)
if(matrix[i][j]>=*max)max=&matrix[i][j];



--------------------
'Cuz I never walk away from what I know is right
Alice Cooper - Freedom
PM   Вверх
LeD4eG
Дата 25.10.2010, 22:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

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



Цитата(djamshud @  25.10.2010,  22:26 Найти цитируемый пост)
Можно перевести фразу "максимальный элемент из повторяющихся более одного раза в матрице" на более русский язык?

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

Добавлено через 1 минуту и 59 секунд
Цитата(Crafty @  25.10.2010,  22:17 Найти цитируемый пост)
фактически и есть одномерный массив.

да, в памяти он так и представляется. я думал представить массив этих массивов в один одномерный массив.
--------------------
Ты не успел стать для кого-то главным, кому-то очень нужным.....
PM MAIL   Вверх
Dov
Дата 26.10.2010, 01:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


аСинизатор
***


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

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



Цитата(LeD4eG @  25.10.2010,  20:46 Найти цитируемый пост)
1) это, мягко скажем, не совсем то, что требовалось в задаче;

почему?

Цитата(LeD4eG @  25.10.2010,  20:46 Найти цитируемый пост)
2) я не знаю, что делать, если этот максимальный элемент второй раз не встретиться.....

а ты его не назначаешь максимальным, пока он не встретится второй раз... 


--------------------
Тут вечности запах томительный,
И свежие фрукты дешевые, 
А климат у нас – изумительный, 
И только соседи – #уевые. 
                           Игорь Губерман.
PM   Вверх
Bugmaker
Дата 26.10.2010, 09:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

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



Вообще напрашивается следующая мысль: пробегаем по матрице, и если встречается элемент, превышающий пременную max, то пробегаем по матрице еще раз и ищем встречается ли он там повторно. Если да, то переназначаем max, если нет - игнорируем.

Примерно так.
Код
int max=0;
int matrix[10][10]
for(int i=1;i<10;i++)
{
  for(int j=1;j<10;j++)
 {
   if(matrix[i][j]>=max)
     {
     for(int i1=1;i1<10;i1++)
     for(int j1=1;j1<10;j1++)
       if((matrix[i][j]=max) and(i!=i1) and (j!=j1))
     max=matrix[i][j];
     }
}
}


Думаю подход ясен. Коряво конечно, но работать будет)


Модератор: Не забываем пользоваться кнопочкой "Код"

Это сообщение отредактировал(а) bsa - 28.10.2010, 21:19
PM MAIL   Вверх
LeD4eG
Дата 26.10.2010, 22:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

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



результаты обработки предложений:
Bugmaker, я реализовал твоё предложение. вместе присваивания максимальному элементу значения 0, решил, что будет лучше запоминать индексы i,j максимального элемента, поскольку массив может состоять из отрицательных величин и этот метод не сработает. также подправил небольшую ошибку, которая сильно влияла на результат (максимальным получался первый элемент).чтобы не быть голословным код:
Код

#include<iostream>
#include<windows.h>
using namespace std;
char* Rus(const char* text);
int main(){
    int nrow,ncol;
    cout<<Rus("Введите количество строк и столбцов: ")<<endl;
    cin>>nrow>>ncol;
    int i,j;
    int **a=new int *[nrow];
    for(i=0;i<nrow;i++) a[i]=new int [ncol];
    cout<<Rus("Введите элементы массива: ")<<endl;
    for(i=0;i<nrow;i++)
        for(j=0;j<ncol;j++) cin>>a[i][j];
    cout<<Rus("Вы ввели следующий массив: ")<<endl;
    for(i=0;i<nrow;i++){
        for(j=0;j<ncol;j++) cout<<setw(4)<<a[i][j]<<' ';
        cout<<endl;
    }
    int imax=0,jmax=0;
    for(i=0;i<nrow;i++){
        for(j=0;j<ncol;j++){
            if(a[i][j]>a[imax][jmax]){
                for(int i1=0;i1<nrow;i1++){
                    for(int j1=0;j1<ncol;j1++){
                        if((a[i1][j1]==a[imax][jmax])&&(i!=i1)&&(j!=j1)){imax=i;jmax=j;}
                    }
                }
            }
        }
    }
    cout<<Rus("Максимальный из повторяющихся равен: ");
    cout<<a[imax][jmax];
    cout<<"\n";
    return 0;
    }
char bufRus[256];
char* Rus(const char* text){
    CharToOem(text, bufRus);
    return bufRus;
}        


vnf, при реализации твоей метода (хотя стоит признаться, что я хотел его реализовать изначально) у меня получились странные результаты..... smile при написании кода с первого раза массив заполнялся числами -89460...при повторной попытке компутер начинает задумываться над своей жизнью (ВОТ ТАК я написал вирус! smile ). 
Код

int mass [100];
    int k=0;
    for(i=0;i<nrow;i++){
        for(j=0;j<ncol;j++){
            for(int p=i+1;p<nrow;p++){
                for(int l=j+1;l<ncol;l++){
                    if(a[i][j]==a[p][l]){
                        mass[k]=a[i][j];
                        ++k;
                    }
                }
            }
        }
    }
    cout<<Rus("Был получен массив: ")<<endl;
    for(k=0;k<100;k++) cout<<mass[k];
    cout<<"\n";

почему я написал так:
при попытке проходить по i и j=i+1 возникает ошибка о невозможности преобразования int* i в int. применял процедуру разыменования - компутер снова задумался.....
я не знаю закрывать ли тему. в принципе задача решена. хоть и автор идеи считает, что его метод кривоват. я бы хотел всё-таки ещё попробовать реализовать и третий метод (находим повторяющиеся, записываем в массив находим там максимум)
но всё равно спасибо всем, кто помог.
--------------------
Ты не успел стать для кого-то главным, кому-то очень нужным.....
PM MAIL   Вверх
Crafty
Дата 26.10.2010, 23:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Цитата(Crafty @  25.10.2010,  23:17 Найти цитируемый пост)
Теперь просто сортируем массив по убыванию и ищем повторяющиеся числа, если такие есть то выходим из цикла. 

Код

#include <iostream>
#include <algorithm>

bool grt(const int a, const int b)
{
  return a > b;
}
int main()
{
  const size_t size = 12;
  int a[size] = { 5, 5, 44, 4, 3, 1, 6, 1, 12, 10, 2, 6};
  std::sort(a, a+size, grt); // сортируем массив по убыванию
  bool check = false; // проверяет найдены ли совпадающие числа
  size_t i;
  for (i = 1; i != size; ++i)
    if (a[i] == a[i-1])
    {
      check = true;
      break;
    }
  if (check)
    std::cout << "Максимальный совпадающий элемент равен " << a[i] << std::endl;
  else
    std::cout << "Повторяющихся элементов не найдено." << std::endl;
  
  return 0;
}
  

PM MAIL   Вверх
kamre
Дата 27.10.2010, 00:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Еще вариант:

Код

#include <set>
#include <iostream>

template<typename Iter, typename T>
bool find_max_dup(Iter first, Iter last, T & result)
{
    bool found = false;
    std::set<T> uniq;
    for (; first != last; ++first) {
        const T & t = *first;
        if (uniq.find(t) == uniq.end()) {
            uniq.insert(t);
        } else {
            if (!found)
                result = t;
            else if (result < t)
                result = t;
            found = true;
        }
    }
    return found;
}

int main(int argc, char **argv)
{
    int values[] = { 7, 9, 5, 8, 12, 4, 5, 8, 2, 4, 7, 8, 9, 0 };
    int result;
    if (find_max_dup(values, values + 14, result))
        std::cout << "max duplicate: " << result << std::endl;
    else
        std::cout << "no duplicates!" << std::endl;
    return 0;
}


PM MAIL   Вверх
mes
Дата 27.10.2010, 00:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


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

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



легкие штрихи :
Цитата(Crafty @  26.10.2010,  22:47 Найти цитируемый пост)
  std::sort(a, a+size, grt);

Код

std::sort(a, a+size, std::greater<int>());


Цитата(Crafty @  26.10.2010,  22:47 Найти цитируемый пост)
bool check = false; // проверяет найдены ли совпадающие числа
  size_t i;
  for (i = 1; i != size; ++i)
    if (a[i] == a[i-1])
    {
      check = true;
      break;
    }
  if (check)


Код

  size_t i=0;
  for (i = 1; i < size; ++i)  // <, так как size может =0;
    if (a[i] == a[i-1]) break;

  if (i!=size)




Это сообщение отредактировал(а) mes - 27.10.2010, 00:46


--------------------
PM MAIL WWW   Вверх
Dov
Дата 27.10.2010, 01:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


аСинизатор
***


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

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



Код
int checkDup(int * arr, int ind, int size)
{
    for(int i = ind + 1; i < size; i++)
        if(arr[i] == arr[ind])
            return ind;
        
    return -1;
}

bool getMax(int * arr, int size, int &maxelem)
{
    int n;

    for(int i = 0; i < size; i++)    
        if((n = checkDup(arr, i, size)) >= 0)
            break;
    
    if(n == -1)
        return false;
    
    maxelem = arr[n];
    for(int i = n + 1; i < size; i++)
        if(arr[i] > maxelem && checkDup(arr, i, size) > 0)
            maxelem = arr[i];
        
    return true;
}

int main()
{
    srand((unsigned)time(NULL));

    int (*matr)[1];
    int rows, cols, max, size;

    cout << "Enter rows and cols:\n";
    cin >> rows >> cols;

    size = rows * cols;
    matr = new int[size][1];

    for(int i = 0; i < size; i++)
        *matr[i] = rand() % 30 + 1;

    cout << "matrix:\n";
    for(int i = 0; i < size; i++)
    {
        cout << setw(4) << *matr[i];
        if((i + 1) % cols == 0)
            cout << endl;
    }

    if(getMax(*matr, size, max))
        cout << "\nmax: " << max << endl;
    else
        cout <<"\nthere is no duplicates...\n\n";

    delete [] matr;

    return 0;
}



--------------------
Тут вечности запах томительный,
И свежие фрукты дешевые, 
А климат у нас – изумительный, 
И только соседи – #уевые. 
                           Игорь Губерман.
PM   Вверх
LeD4eG
Дата 28.10.2010, 20:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


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

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



тема изучена и закрыта. спасибо всем за помощь! smile 
--------------------
Ты не успел стать для кого-то главным, кому-то очень нужным.....
PM MAIL   Вверх
Crafty
Дата 2.11.2010, 18:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


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

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



Ещё немного подправил свой вариант.
Код

#include <iostream>
#include <functional>
#include <algorithm>

int main()
{
  const size_t size = 12;
  int a[size] = { 5, 5, 44, 4, 3, 1, 6, 1, 12, 10, 2, 6 };
  std::sort(a, a+size, std::greater<int>());   // сортируем массив по убыванию
  int *it = std::adjacent_find(a, a + size);    // adjacment_find возвращает итератор на первую пару
  if (it != a + size)
    std::cout << "Максимальный совпадающий элемент равен " << *it << std::endl;
  else
    std::cout << "Повторяющихся элементов не найдено." << std::endl;
  
  return 0;
}
  

PM MAIL   Вверх
Dov
Дата 2.11.2010, 20:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


аСинизатор
***


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

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



Цитата(Crafty @  2.11.2010,  17:43 Найти цитируемый пост)
Ещё немного подправил свой вариант.

 smile 

Челу нужен двумерный динамический массив. Исходя из этого и нужно "подправлять".   smile 



--------------------
Тут вечности запах томительный,
И свежие фрукты дешевые, 
А климат у нас – изумительный, 
И только соседи – #уевые. 
                           Игорь Губерман.
PM   Вверх
Страницы: (3) Все [1] 2 3 
Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.

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


 




[ Время генерации скрипта: 0.1437 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.