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

Для матрицы размером NxM вывести на экран все седловые точки. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.83
saserlend
10 / 10 / 1
Регистрация: 25.11.2011
Сообщений: 138
08.12.2011, 00:40     Для матрицы размером NxM вывести на экран все седловые точки. #1
Для матрицы размером NxM вывести на экран все седловые точки. Элемент матрицы называется седловой точкой, если он является наименьшим в своей строке и одновременно наибольшим в своем столбце или наоборот.
Вот код, увы работать не хочет.
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
#include <stdio.h>
#include <malloc.h>
void main()
{
int **p,i,j,k,i,n,1,i2,j1,t,m;
//Razmernost' stroki
scanf("%d",&k);
p=(int**)malloc(k*sizeof(int*));
//Razmernost' stolbca
scanf("%d",&n);
for (i=0;i<n;i++)
*(p+i)=(int*)malloc(n*sizeof(int));
//vvod matricy
for (i=0;i<k;i++)
for (j=0;j<n;j++) scanf("%d",(*(p+i)+j));
/*Poisk sedlovoi tochki*/
for(i=0;i<k;i++)
{
t=*(*(p+i)+0);
i1=i; j1=0;
for(j=1;j<n;j++)
if(*(*(p+i)+j)>t)
{
t=*(*(p+i)+j);
i1=i;j1=j;}
 m=0;
for(i2=0;i2<k;i2++)
if(*(*(p+i1)+j1)>=*(*(p+i2)+j1) && i1!=i2)
m=1; if(!m){printf("\nNaidena sedlovays tochka %d c koordinatami: %d-stroka,%d-stolbec",*(*(p+i1)+j1),i1+1,j1+1);
break;}}
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
08.12.2011, 01:27     Для матрицы размером NxM вывести на экран все седловые точки. #2
вот лови код он работает правильно но меня не ругать я писал его на 1 курсе а править не хочу
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
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
class Matr        //klass
{
int **A,n,*max,*min;
public:
Matr(int _n):n(_n){}        //konstructor
void creat()                    //fun dlya dinamic videleniya pamyati
{
    A=new int*[n];               //dlya matrici
    for(int i=0;i<n;i++)
        A[i]=new int[n];
         for(int i=0;i<n;i++)
         {
            for(int j=0;j<n;j++)
         {
            A[i][j]=random(10);
            }
            }
         max=new int[n];                 //dlya massivov
         min=new int[n];
}
void poisk()                  //fun dlya naxojdenoya min v strokax i max v stolbcax
{
for(int i=0;i<n;i++)
{
    min[i]=A[i][0];
    for(int j=0;j<n;j++)
   {
      if(min[i]>A[i][j])
      {
        min[i]=A[i][j];
      }
    }
}
for(int i=0;i<n;i++)
{
    max[i]=A[i][0];
    for(int j=0;j<n;j++)
   {
      if(max[i]<A[j][i])
      {
        max[i]=A[j][i];
      }
    }
}
}
void vivod()                    //fun vivodim vsy matricy
{
    for(int i=0;i<n;i++)
        {
             cout<<endl;
          for(int j=0;j<n;j++)
            {
                printf("%3d",A[i][j]);
        }
        }
      cout<<endl;
 
      }
int vibor()
 {
 cout<<endl;
 for(int j=0;j<n;j++)
 {
    for(int i=0;i<n;i++)
   {
         if(max[j]==min[i])             //esli est sovpadeniya v massivax znachit eto i budet sedlovoi tochkoi
       {cout<< max[j];
       return 0;}
    }
 }
 
}
 
};
int main()
{int n;
cout<<"vvedite razmer matrici";
cin>>n;
randomize();
Matr ob(n);
ob.creat();
ob.poisk();
ob.vivod();
ob.vibor();
cout<<endl;
system("pause");
return 0;
}
и тут для квадратных матриц так что поменяй переменные в циклах
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
08.12.2011, 08:33     Для матрицы размером NxM вывести на экран все седловые точки. #3
очень понравилась задача, решил. Если у вас не получится то потом выложу.
Цитата Сообщение от saserlend Посмотреть сообщение
если он является наименьшим в своей строке и одновременно наибольшим в своем столбце или наоборот.
т.е. строго меньше остальных или строго больше. пытался описать алгоритм, но на словах получится такая путаница, что сам разобрать не смогу. Короче не хочу давать на блюдце, попытайтесь решить, нужен нестандартный ход мысли.

Добавлено через 3 минуты
Цитата Сообщение от A555 Посмотреть сообщение
creat()
строка 9. Linux api не ваша работа?
saserlend
10 / 10 / 1
Регистрация: 25.11.2011
Сообщений: 138
08.12.2011, 11:07  [ТС]     Для матрицы размером NxM вывести на экран все седловые точки. #4
Вообще как я думаю должен быть цикл в цикле. 2 Цикла по поиску мин и макс в строках и столбцах а потом их сравнение и в случае совпадения вывод. Но я первый курс а большенство тут пока не очень для меня понятно пишут. но в качестве ознакомления я бы посмотрел на вашу работу.
Ну и советы послушай бы
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
08.12.2011, 17:50     Для матрицы размером NxM вывести на экран все седловые точки. #5
посмотрите, попробуйте сделать. В кратце решается так:
цикл от 0 до количества строк
ищем индекс столбца, в котором лежит наименьшее число строки [i]
в столбце с найденным индексом ищем индекс строки, в которой лежит наибольшее число
если найденный индекс строки совпадает с i, то число седловое
те же манипуляции только наоборот, сначала поиск индекса столбца где лежит наибольшее число
в столбце с найденным индексом поиск строки где лежит наименьшее число,
если найденный индекс строки == i - число есть седловое.
продолжаем цикл.
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
08.12.2011, 18:47     Для матрицы размером NxM вывести на экран все седловые точки. #6
я там написал работающий код )
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
08.12.2011, 19:08     Для матрицы размером NxM вывести на экран все седловые точки. #7
A555, простите, но я с вами не согласен. Во - первых разберемся с термином "наименьший", я трактую как такой элемент, который меньше всех остальных. Если Таких элементов 2 и более, то наименьшего элемента нет. Это тонкость и я могу ошибаться, в случае если я ошибаюсь, то алгоритм становится намного быстрее, но и также появляется неопределенность вида "как указать программе, какой из двух минимумов вибрать для сравнения? первый? последний? все?", проверка на строгий минимум или строгий максимум эту неопределенность снимает. Во - вторых ваша программа выводит число, если оно является минимумом в одной строке и максимумом в другой. Никакой связки индексов не прослеживается, а по сути сами числа нам не нужны. Это просто не та программа, я когда решал ее даже как селет не брал в расчет.
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
08.12.2011, 20:09     Для матрицы размером NxM вывести на экран все седловые точки. #8
Цитата Сообщение от alkagolik Посмотреть сообщение
A555, простите, но я с вами не согласен. Во - первых разберемся с термином "наименьший", я трактую как такой элемент, который меньше всех остальных. Если Таких элементов 2 и более, то наименьшего элемента нет. Это тонкость и я могу ошибаться, в случае если я ошибаюсь, то алгоритм становится намного быстрее, но и также появляется неопределенность вида "как указать программе, какой из двух минимумов вибрать для сравнения? первый? последний? все?", проверка на строгий минимум или строгий максимум эту неопределенность снимает. Во - вторых ваша программа выводит число, если оно является минимумом в одной строке и максимумом в другой. Никакой связки индексов не прослеживается, а по сути сами числа нам не нужны. Это просто не та программа, я когда решал ее даже как селет не брал в расчет.
блин всё простите ща исправлю)) не почиталл даже свой код он работает полностью верно_) просто он находит не селовую а минимальный в троках и максимальный в столбцах их совпадения сек

Добавлено через 1 минуту
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
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
class Matr        //klass
{
int **A,n,*max,*min;
public:
Matr(int _n):n(_n){}            //konstructor
void creat()                    //fun dlya dinamic videleniya pamyati
{
        A=new int*[n];               //dlya matrici
        for(int i=0;i<n;i++)
        A[i]=new int[n];
         for(int i=0;i<n;i++)
         {
                for(int j=0;j<n;j++)
         {
                A[i][j]=random(10);
            }
            }
         max=new int[n];                 //dlya massivov
         min=new int[n];
}
void poisk()                  //fun dlya naxojdenoya min v strokax i max v stolbcax
{
for(int i=0;i<n;i++)
{
        min[i]=A[i][0];
        for(int j=0;j<n;j++)
   {
      if(min[i]>A[i][j])
      {
        min[i]=A[i][j];
      }
        }
}
for(int i=0;i<n;i++)
{
        max[i]=A[i][0];
        for(int j=0;j<n;j++)
   {
      if(max[i]>A[j][i])
      {
        max[i]=A[j][i];
      }
        }
}
}
void vivod()                    //fun vivodim vsy matricy
{
        for(int i=0;i<n;i++)
                {
                         cout<<endl;
          for(int j=0;j<n;j++)
                {
                                printf("%3d",A[i][j]);
                }
                }
      cout<<endl;
 
      }
int vibor()
 {
 cout<<endl;
 for(int j=0;j<n;j++)
 {
        for(int i=0;i<n;i++)
   {
                 if(max[j]==min[i])             //esli est sovpadeniya v massivax znachit eto i budet sedlovoi tochkoi
       {cout<< max[j];
       return 0;}
    }
 }
 
}
 
};
int main()
{int n;
cout<<"vvedite razmer matrici";
cin>>n;
randomize();
Matr ob(n);
ob.creat();
ob.poisk();
ob.vivod();
ob.vibor();
cout<<endl;
system("pause");
return 0;
}
вот там только 1 знак равернуть

Добавлено через 13 минут
и ещё там не всё верно)) работает правильно но написать можно гораздо лучше)
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
08.12.2011, 20:57     Для матрицы размером NxM вывести на экран все седловые точки. #9
A555, тоже не то. Если брать ваш алгоритм за основу, то нам понадобятся не 2, а 4 массива. 2 массива строгих минимумов строк и столбцов и 2 массива строгих максимумов строк и столбцов, но подход неверный потому что таким образом мы не сможем определить является ли минимум\максимум единственным с строке\столбце или нет. Следствие, можно перестроить так, что в массивы будут закладываться индексы, а в случае отсутствия наименьшего\наибольшего числа в строке\столбце - отрицательные значения. Дальше искать каким образом эти индексы связать друг с другом для сравнения. Сложность алгоритма будет выше чем алгоритма без использования вспомогательных массивов, и ресурсов тоже больше. Хотя сам алгоритм поиска наименьших\наибольших значений и так зашкаливает.
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
08.12.2011, 21:02     Для матрицы размером NxM вывести на экран все седловые точки. #10
Цитата Сообщение от alkagolik Посмотреть сообщение
A555, тоже не то. Если брать ваш алгоритм за основу, то нам понадобятся не 2, а 4 массива. 2 массива строгих минимумов строк и столбцов и 2 массива строгих максимумов строк и столбцов, но подход неверный потому что таким образом мы не сможем определить является ли минимум\максимум единственным с строке\столбце или нет. Следствие, можно перестроить так, что в массивы будут закладываться индексы, а в случае отсутствия наименьшего\наибольшего числа в строке\столбце - отрицательные значения. Дальше искать каким образом эти индексы связать друг с другом для сравнения. Сложность алгоритма будет выше чем алгоритма без использования вспомогательных массивов, и ресурсов тоже больше. Хотя сам алгоритм поиска наименьших\наибольших значений и так зашкаливает.
а читая твоё сообщение мой мозг включаеться и я понимаю) где не правильно даже стыдно)
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
08.12.2011, 21:07     Для матрицы размером NxM вывести на экран все седловые точки. #11
вот например как сделать поиск наименьшего числа в массиве меньше чем O(2n) не используя сортировку? Наименьшим считаем число, которое строго меньше всех остальных чисел в массиве. Если число меньше равно любому другому элементу, то вернем - 1, если оно строго меньше остальных - вернем его индекс в массиве. Я пока не вижу алгоритма лучше чем О(2n).

Добавлено через 1 минуту
A555, все путем. Стыдно когда видно, а если не видно, то нормалек.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
11.12.2011, 05:03     Для матрицы размером NxM вывести на экран все седловые точки. #12
смотрю так и приутих энтузиазм. Жаль. Функции find_min, find_max далеки от совершенства, можно доработать
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
int *create ( size_t num, size_t size )
{
    int *t;
    if ( ( t = malloc(num * size) ) == NULL )
        exit ( EXIT_FAILURE );
    else
        return t;
}
 
void print_matrix ( int **matr, size_t row, size_t coll )
{
    for ( int i = 0; i < row; ++i )
    {
        for ( int j = 0; j < coll; ++j )
            printf( "%2i ", matr[ i ][ j ] );
        puts("");
    }
}
 
void init_matrix ( int **matr, size_t row, size_t coll )
{
    for ( int i = 0; i < row; ++i )
        for ( int j = 0; j < coll; ++j )
            matr[ i ][ j ] = j - i;
}
 
int find_min ( int **arr, size_t i, size_t j, size_t row, size_t coll, _Bool flag )
//flag = 1 - ищем СТРОГИЙ минимум строки, иначе столбца
{
    int min = arr[ i ][ j ];
    int tmp, iter = 0;
    if ( flag )
    {
        while ( iter < coll ){
            if ( arr[ i ][ iter ] <= min ){
                min = arr[ i ][ iter ];
                tmp = iter;
            }
            ++iter;
        }
        iter = 0;
        while ( iter < coll ){
            if ( arr[ i ][ iter ] == min && iter != tmp )
                return -1;
            ++iter;
        }
    }
    else
    {
        while ( iter < row ){
            if ( arr[ iter ][ j ] <= min ){
                min = arr[ iter ][ j ];
                tmp = iter;
            }
            ++iter;
        }
        iter = 0;
        while ( iter < row ){
            if ( arr[ iter ][ j ] == min && iter != tmp )
                return -1;
            ++iter;
        }
    }
    return tmp;
}
 
int find_max ( int **arr, size_t i, size_t j, size_t row, size_t coll, _Bool flag )
//flag = 1 - ищем СТРОГИЙ максимум строки, иначе столбца
{
    int max = arr[ i ][ j ];
    int tmp, iter = 0;
    if ( flag )
    {
        while ( iter < coll ){
            if ( arr[ i ][ iter ] >= max ){
                max = arr[ i ][ iter ];
                tmp = iter;
            }
            ++iter;
        }
        iter = 0;
        while ( iter < coll ){
            if ( arr[ i ][ iter ] == max && iter != tmp )
                return -1;
            ++iter;
        }
    }
    else
    {
        while ( iter < row ){
            if ( arr[ iter ][ j ] >= max ){
                max = arr[ iter ][ j ];
                tmp = iter;
            }
            ++iter;
        }
        iter = 0;
        while ( iter < row ){
            if ( arr[ iter ][ j ] == max && iter != tmp )
                return -1;
            ++iter;
        }
    }
    return tmp;
}
 
void find_num_points ( int **matr, size_t row, size_t coll )
{
    int min, max;
    int i, j;
 
    for ( i = 0; i < row; ++i )
    {
        if( ( min = find_min(matr, i, 0, row, coll, 1) ) >= 0 )
            if ( ( max =  find_max(matr, 0, min, row, coll, 0) ) >= 0 )
                if ( max == i )
                    printf ("строка %i, столбец %i число = %2i\n", i, min,  matr[ i ][ min ] );
 
        if( ( max = find_max(matr, i, 0, row, coll, 1) ) >= 0 )
            if ( ( min =  find_min(matr, 0, max, row, coll, 0) ) >= 0 )
                if ( min == i )
                    printf ("строка %i, столбец %i число = %2i\n", i, min,  matr[ i ][ min ] );
    }
}
 
int main ( void )
{
    size_t size = 10;
    int **matrix;
 
    matrix = (int **) create( size, sizeof(int*) );
    for (int i = 0; i < size; ++i)
        matrix[ i ] = (int *)create( size, sizeof(int) );
 
    init_matrix( matrix, size, size );
    print_matrix( matrix, size, size );
    find_num_points( matrix, size, size );
 
    for ( int i = 0; i < size; ++i )
        free( matrix[ i ] );
    free( matrix );
 
    return EXIT_SUCCESS;
}
пример
Код
 0  1  2  3  4  5  6  7  8  9 
-1  0  1  2  3  4  5  6  7  8 
-2 -1  0  1  2  3  4  5  6  7 
-3 -2 -1  0  1  2  3  4  5  6 
-4 -3 -2 -1  0  1  2  3  4  5 
-5 -4 -3 -2 -1  0  1  2  3  4 
-6 -5 -4 -3 -2 -1  0  1  2  3 
-7 -6 -5 -4 -3 -2 -1  0  1  2 
-8 -7 -6 -5 -4 -3 -2 -1  0  1 
-9 -8 -7 -6 -5 -4 -3 -2 -1  0 
строка 0, столбец 0 число =  0
строка 9, столбец 9 число =  0
Coral
 Аватар для Coral
0 / 0 / 0
Регистрация: 17.01.2014
Сообщений: 6
20.01.2014, 17:15     Для матрицы размером NxM вывести на экран все седловые точки. #13
Цитата Сообщение от alkagolik Посмотреть сообщение
пример
Код
 0  1  2  3  4  5  6  7  8  9 
-1  0  1  2  3  4  5  6  7  8 
-2 -1  0  1  2  3  4  5  6  7 
-3 -2 -1  0  1  2  3  4  5  6 
-4 -3 -2 -1  0  1  2  3  4  5 
-5 -4 -3 -2 -1  0  1  2  3  4 
-6 -5 -4 -3 -2 -1  0  1  2  3 
-7 -6 -5 -4 -3 -2 -1  0  1  2 
-8 -7 -6 -5 -4 -3 -2 -1  0  1 
-9 -8 -7 -6 -5 -4 -3 -2 -1  0 
строка 0, столбец 0 число =  0
строка 9, столбец 9 число =  0
Может быть строка 10 и стоблец 10 это вторая седловая точка?
Потому что элемент (9,9) - 0. Он не максимальный в строке.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.01.2014, 18:21     Для матрицы размером NxM вывести на экран все седловые точки.
Еще ссылки по теме:

Определить седловые точки матрицы C++
СЕДЛОВЫЕ точки матрицы( ПОмогите исправить) C++
C++ Найти седловые точки матрицы

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

Или воспользуйтесь поиском по форуму:
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
20.01.2014, 18:21     Для матрицы размером NxM вывести на экран все седловые точки. #14
Coral, индексация с нуля, т.е. строка 9 -- это фактически 10.
Yandex
Объявления
20.01.2014, 18:21     Для матрицы размером NxM вывести на экран все седловые точки.
Ответ Создать тему
Опции темы

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