Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.83
saserlend
11 / 11 / 1
Регистрация: 25.11.2011
Сообщений: 145
#1

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

08.12.2011, 00:40. Просмотров 3426. Ответов 13
Метки нет (Все метки)

Для матрицы размером 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;}}
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.12.2011, 00:40
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Для матрицы размером NxM вывести на экран все седловые точки. (C++):

В матрице NxM найти все седловые точки - C++
Для матрицы размером NxM вывести на экран все седловые точки. (Элемент матрицы называется седловой, если он является наименьшим в своей...

Для заданной матрицы определить все седловые точки - C++
Ребят, пожалуйста очень надо, нифига не знаю.=(( 1. Массив целых чисел. Найти сумму чётных элементов массива. Отсортировать в...

Седловые точки матрицы - C++
Найти седловые точки матрицы. Седловой точкой называется элемент, являющийся минимальным в строке и максимальным в столбце. Я тут...

Седловые точки матрицы - C++
Доброго времени суток,уважаемые программисты. Возникла такая проблема. Имеется следующий код: #include &lt;stdio.h&gt; #include...

Определить седловые точки матрицы - C++
Доброго времени суток. Задали написать программу на C++, вот задание: &quot;Дана целочисленная матрица. Определить: 1) Кол-во отрицательных...

Найти седловые точки матрицы - C++
Ввести данные в прямоугольную матрицу, вывести матрицу на экран. В матрице найти седловые точки (найти номер строки и столбца для каждой...

13
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
08.12.2011, 01:27 #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
alkagolik
Заблокирован
08.12.2011, 08:33 #3
очень понравилась задача, решил. Если у вас не получится то потом выложу.
Цитата Сообщение от saserlend Посмотреть сообщение
если он является наименьшим в своей строке и одновременно наибольшим в своем столбце или наоборот.
т.е. строго меньше остальных или строго больше. пытался описать алгоритм, но на словах получится такая путаница, что сам разобрать не смогу. Короче не хочу давать на блюдце, попытайтесь решить, нужен нестандартный ход мысли.

Добавлено через 3 минуты
Цитата Сообщение от A555 Посмотреть сообщение
creat()
строка 9. Linux api не ваша работа?
0
saserlend
11 / 11 / 1
Регистрация: 25.11.2011
Сообщений: 145
08.12.2011, 11:07  [ТС] #4
Вообще как я думаю должен быть цикл в цикле. 2 Цикла по поиску мин и макс в строках и столбцах а потом их сравнение и в случае совпадения вывод. Но я первый курс а большенство тут пока не очень для меня понятно пишут. но в качестве ознакомления я бы посмотрел на вашу работу.
Ну и советы послушай бы
0
alkagolik
Заблокирован
08.12.2011, 17:50 #5
посмотрите, попробуйте сделать. В кратце решается так:
цикл от 0 до количества строк
ищем индекс столбца, в котором лежит наименьшее число строки [i]
в столбце с найденным индексом ищем индекс строки, в которой лежит наибольшее число
если найденный индекс строки совпадает с i, то число седловое
те же манипуляции только наоборот, сначала поиск индекса столбца где лежит наибольшее число
в столбце с найденным индексом поиск строки где лежит наименьшее число,
если найденный индекс строки == i - число есть седловое.
продолжаем цикл.
0
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
08.12.2011, 18:47 #6
я там написал работающий код )
0
alkagolik
Заблокирован
08.12.2011, 19:08 #7
A555, простите, но я с вами не согласен. Во - первых разберемся с термином "наименьший", я трактую как такой элемент, который меньше всех остальных. Если Таких элементов 2 и более, то наименьшего элемента нет. Это тонкость и я могу ошибаться, в случае если я ошибаюсь, то алгоритм становится намного быстрее, но и также появляется неопределенность вида "как указать программе, какой из двух минимумов вибрать для сравнения? первый? последний? все?", проверка на строгий минимум или строгий максимум эту неопределенность снимает. Во - вторых ваша программа выводит число, если оно является минимумом в одной строке и максимумом в другой. Никакой связки индексов не прослеживается, а по сути сами числа нам не нужны. Это просто не та программа, я когда решал ее даже как селет не брал в расчет.
0
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
08.12.2011, 20:09 #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 минут
и ещё там не всё верно)) работает правильно но написать можно гораздо лучше)
0
alkagolik
Заблокирован
08.12.2011, 20:57 #9
A555, тоже не то. Если брать ваш алгоритм за основу, то нам понадобятся не 2, а 4 массива. 2 массива строгих минимумов строк и столбцов и 2 массива строгих максимумов строк и столбцов, но подход неверный потому что таким образом мы не сможем определить является ли минимум\максимум единственным с строке\столбце или нет. Следствие, можно перестроить так, что в массивы будут закладываться индексы, а в случае отсутствия наименьшего\наибольшего числа в строке\столбце - отрицательные значения. Дальше искать каким образом эти индексы связать друг с другом для сравнения. Сложность алгоритма будет выше чем алгоритма без использования вспомогательных массивов, и ресурсов тоже больше. Хотя сам алгоритм поиска наименьших\наибольших значений и так зашкаливает.
0
A555
51 / 51 / 2
Регистрация: 04.04.2011
Сообщений: 209
08.12.2011, 21:02 #10
Цитата Сообщение от alkagolik Посмотреть сообщение
A555, тоже не то. Если брать ваш алгоритм за основу, то нам понадобятся не 2, а 4 массива. 2 массива строгих минимумов строк и столбцов и 2 массива строгих максимумов строк и столбцов, но подход неверный потому что таким образом мы не сможем определить является ли минимум\максимум единственным с строке\столбце или нет. Следствие, можно перестроить так, что в массивы будут закладываться индексы, а в случае отсутствия наименьшего\наибольшего числа в строке\столбце - отрицательные значения. Дальше искать каким образом эти индексы связать друг с другом для сравнения. Сложность алгоритма будет выше чем алгоритма без использования вспомогательных массивов, и ресурсов тоже больше. Хотя сам алгоритм поиска наименьших\наибольших значений и так зашкаливает.
а читая твоё сообщение мой мозг включаеться и я понимаю) где не правильно даже стыдно)
0
alkagolik
Заблокирован
08.12.2011, 21:07 #11
вот например как сделать поиск наименьшего числа в массиве меньше чем O(2n) не используя сортировку? Наименьшим считаем число, которое строго меньше всех остальных чисел в массиве. Если число меньше равно любому другому элементу, то вернем - 1, если оно строго меньше остальных - вернем его индекс в массиве. Я пока не вижу алгоритма лучше чем О(2n).

Добавлено через 1 минуту
A555, все путем. Стыдно когда видно, а если не видно, то нормалек.
0
alkagolik
Заблокирован
11.12.2011, 05:03 #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
1
Coral
2 / 2 / 0
Регистрация: 17.01.2014
Сообщений: 6
20.01.2014, 17:15 #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. Он не максимальный в строке.
0
alkagolik
Заблокирован
20.01.2014, 18:21 #14
Coral, индексация с нуля, т.е. строка 9 -- это фактически 10.
0
20.01.2014, 18:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.01.2014, 18:21
Привет! Вот еще темы с ответами:

Разбить на подпрограммы (седловые точки матрицы) - C++
Приветствую. Вот код, в консоли программа выводит на экран седловые точки матрицы MxN (минимальные в столбце и максимальные в строке). ...

СЕДЛОВЫЕ точки матрицы( ПОмогите исправить) - C++
//sedlov tochka//////////////////////////// for(i=0;i&lt;n;i++) { min=a; for(j=0;j&lt;m;j++) { if(a&lt;min) ...

Заменить в текстовой строке все запятые на точки и вывести результат на экран - C++
Народ как сделать в обычном borland c следющее: Заменить в текстовой строке все запятые на точки и вывести результат на экран

Задана матрица размером NxM. Определить количество "особых" элементов матрицы - C++
Помогите написать программу. Задана матрица размером NxM. Определить количество &quot;особых&quot; элементов матрицы, считая элемент &quot;особым&quot;, если...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru