Форум программистов, компьютерный форум CyberForum.ru

Поиск в матрице, задача - C++

Восстановить пароль Регистрация
 
LeShChEnKo
1 / 1 / 0
Регистрация: 06.10.2013
Сообщений: 17
13.01.2014, 21:57     Поиск в матрице, задача #1
Итак форум ваш мне очень понравился по тому как мало людей которые дают ненужные советы, а только дельные слова.
Сама проблема заключается в том что я еще немного недопонял с++. Где то месяц назад я участвовал в школьной олимпиаде и мне встретилась интересная задача, я ее не сделал, но получилось так что проконало как робочая программа. Но мне все же интересно как ее решить.
Сама задача из памяти - есть целочисельная матрица. Найти число которое повторяется хотя бы 2 раза ну или более. Вывести на экран самое встречаемое число в матрице. Если таких чисел нет то собственно это и написать.
Задача вроде как и не сложная, но у меня не удалось ее решить.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.01.2014, 21:57     Поиск в матрице, задача
Посмотрите здесь:

Задача по матрице C++
C++ Поиск островов в матрице
Поиск в матрице C++
C++ Поиск минимального элемента в матрице
Поиск нулевых значений в матрице C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MicM
 Аватар для MicM
820 / 487 / 90
Регистрация: 29.12.2009
Сообщений: 1,097
Завершенные тесты: 1
13.01.2014, 22:58     Поиск в матрице, задача #2
Цитата Сообщение от LeShChEnKo Посмотреть сообщение
Если таких чисел нет то собственно это и написать.
LeShChEnKo, под эти подразумевается что в матрице есть несколько чисел, которые повторяются более 2 раз и одновременно одинаковое количество раз?
newb_programmer
 Аватар для newb_programmer
237 / 237 / 19
Регистрация: 03.09.2011
Сообщений: 553
13.01.2014, 22:59     Поиск в матрице, задача #3
LeShChEnKo, ну я вот как то так набросал...и вроде даже работает =))))
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
 
int main() 
{ 
    srand(time(0));
    const int n=5;
    int arr[n][n];
    int i,j,k,r=0,res=0,num=0;
    for (i=0;i<n;i++) {
        for (j=0;j<n;j++) {
            arr[i][j]=rand()%10;
            cout<<arr[i][j]<<" ";
        }
        cout<<endl;
    }
    for (i=0;i<n;i++) {
        for (j=0;j<n;j++) {
            r=0;
            for (k=j+1;k<n;k++) {
                if (arr[i][j]==arr[i][k])
                    r++;
            }
            if (res<r) {
                res=r;
                num=arr[i][j];
            }
        }
    }
    if (!res)
        cout<<"No repeated numbers!\n";
    else
        cout<<"Num = " << num <<endl;
 
    system("pause");
    return 0;
}
LeShChEnKo
1 / 1 / 0
Регистрация: 06.10.2013
Сообщений: 17
13.01.2014, 23:05  [ТС]     Поиск в матрице, задача #4
Цитата Сообщение от MicM Посмотреть сообщение
LeShChEnKo, под эти подразумевается что в матрице есть несколько чисел, которые повторяются более 2 раз и одновременно одинаковое количество раз?
именно

Добавлено через 2 минуты
Цитата Сообщение от newb_programmer Посмотреть сообщение
LeShChEnKo, ну я вот как то так набросал...и вроде даже работает =))))
Спасибо большое, но проблема есть, некоторые числа повторяються одинаковое количество раз, можно их вивести все?
__General__
24 / 24 / 3
Регистрация: 04.01.2014
Сообщений: 91
Завершенные тесты: 2
13.01.2014, 23:09     Поиск в матрице, задача #5
LeShChEnKo, а в задаче не было никаких ограничений на значения, которые могут принимать элементы матрицы?

1)Если были существенные ограничения, допустим, известно, что элементы матрицы не отрицательны и не превышают 1000, то можно было бы объявить массив Count[1000] - массив счетчиков. Далее во вложенном цикле просмотрим все элементы матрицы, и заполним наш массив:
Count[i] - сколько раз в матрице встретилось число i.
Остается найти максимум в массиве Count, и если он не меньше двух, то вывести его индекс, а если меньше - сказать, что такого элемента нет.

2)(универсальный способ)
Если же ограничений на элементы матрицы не было, то есть если элементом матрицы может быть любое число, которое помещается в int, то объявлять массив счетчиков - слишком расточительно с точки зрения использования памяти (массив в 4 млрд целых чисел весит около 16 гигабайт, если я не просчитался).
В этом случае можно, например, написать свою структуру:
C++
1
2
3
4
5
struct element
{
    int value;
    int num_in_matrix;
};
В первом элементе структуры хранится само число - элемент матрицы, во втором - сколько раз он в ней встречается.
Далее можно объявить массив-вектор-список (что хотите) структур element (аналог массива счетчиков), и за один проход по матрице заполнить его. Дальше находим элемент массива, у которого достигает максимального значения поле num_in_matrix, и выводим значения его поля value, либо говорим, что такого элемента нет.
MicM
 Аватар для MicM
820 / 487 / 90
Регистрация: 29.12.2009
Сообщений: 1,097
Завершенные тесты: 1
13.01.2014, 23:10     Поиск в матрице, задача #6
Вот моя реализация:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <iomanip>
using std::setw;
using std::cout;
using std::endl;
 
struct strct
{
    int a;
    int count;
};
 
const int n = 5;
 
int main()
{
    setlocale (LC_ALL,"Russian");
    srand (time(0));
    int a[n][n];
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
        {
            a[i][j]=rand()%30+1;
            cout <<setw(3) <<a[i][j];
        }
        cout <<endl;
    }
    strct mas[n*n];
    int k = 0;
    bool flag;
    for (int i=0; i<n; i++)
    {
        flag = false;
        for (int j=0; j<n; j++)
        {
            for (int c=0; c<k; c++)
                if (mas[c].a==a[i][j])
                {
                    ++mas[c].count;
                    flag = true;
                    break;
                }
            if (!flag)
            {
                mas[k].a = a[i][j];
                mas[k].count = 1;
                ++k;
            }
        }
    }
    strct tmp;
    do
    {
        flag = true;
        for (int i=0; i<k-1; i++)
        {
            if (mas[i].count < mas[i+1].count)
            {
                flag = false;
                tmp = mas[i];
                mas[i] = mas[i+1];
                mas[i+1] = tmp;
            }
        }
    }
    while (!flag);
    flag = true;
    for (int i=1; i<k; i++)
        if (mas[i].count==mas[0].count)
        {
            flag = false;
            break;
        }
    if (flag)
        cout <<mas[0].a <<endl;
    else cout <<"Таких чисел нет!\n";
    return 0;
}
newb_programmer
 Аватар для newb_programmer
237 / 237 / 19
Регистрация: 03.09.2011
Сообщений: 553
13.01.2014, 23:30     Поиск в матрице, задача #7
Цитата Сообщение от LeShChEnKo Посмотреть сообщение
некоторые числа повторяються одинаковое количество раз, можно их вивести все?
вот примерный код, с использованием вектора, вроде все правильно, но вектор почемуто не очищается...хз почему с векторами не работал раньше))))
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>
using namespace std;
 
int main() 
{ 
    srand(time(0));
    const int n=5;
    vector<int> temp(n*n);
    int arr[n][n];
    int i,j,k,r=0,res=0,num=0;
    for (i=0;i<n;i++) {
        for (j=0;j<n;j++) {
            arr[i][j]=rand()%10;
            cout<<arr[i][j]<<" ";
        }
        cout<<endl;
    }
    for (i=0;i<n;i++) {
        for (j=0;j<n;j++) {
            r=0;
            for (k=j+1;k<n;k++) {
                if (arr[i][j]==arr[i][k])
                    r++;
            }
            if (res==r) {
                temp.push_back(arr[i][j]);
            }
            else if(res<r){
                temp.clear();
                temp.push_back(arr[i][j]);
                res=r;
            }
        }
    }
    int t=temp.size();
    if (!res)
        cout<<"No repeated numbers!\n";
    else {
        cout<<"Number:\n";
        for(i=0;i<t;i++)
            cout<<temp[i]<<endl;
    }
 
    system("pause");
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.01.2014, 21:40     Поиск в матрице, задача
Еще ссылки по теме:

У меня задача,в матрице,заменить первый отрицательный элемент максимальным элементом. Проходить по матрице слева направо,сверху вниз C++
C++ Поиск матрицы в матрице
Поиск в матрице символов C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
LeShChEnKo
1 / 1 / 0
Регистрация: 06.10.2013
Сообщений: 17
14.01.2014, 21:40  [ТС]     Поиск в матрице, задача #8
Цитата Сообщение от MicM Посмотреть сообщение
Вот моя реализация:
Спасибо большое!
Работает на ура, будем разбираться)
Yandex
Объявления
14.01.2014, 21:40     Поиск в матрице, задача
Ответ Создать тему
Опции темы

Текущее время: 10:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru