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

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

Войти
Регистрация
Восстановить пароль
 
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
#1

В файл вывести седловые точки матрицы - C++

21.06.2011, 20:58. Просмотров 755. Ответов 0
Метки нет (Все метки)

Доброго времени суток.
В input.txt лежат n(количество строк),m(количество столбцов) и элементы матрицы.
В output.txt нужно вывести количество седловых точек.
Седловой точкой этой матрицы назовем элемент, который одновременно является минимумом в своей строке и максимумом в своем столбце.
Полное условие
У меня получилось что-то такое
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <fstream>
int w[750][750],i,j,n,m,d,k,x,r;
main(){
    std::fstream v("input.txt");
    for (v >> n >> m;i < n;++i) //считывание
        for (j=0; j < m;)
            v >> w[i][j++];
    
    for (i = 0; i < n; ++i){
        for (j = 0,d = 1001; j < m; ++j)//нахожу минимальный элемент в строке
            if (w[i][j] < d) d=w[i][j];
        //для каждого минимального элемента проверяю,
        //является ли он максимальный элементом в столбце
        for (j = 0; j < m; ++j)
        if ( w[i][j] == d ){
            for (k = x = 0; k < n; ++k)
                if ( w[k][j] > d) {x = 1; break; }
            if (!x) ++r;  
        }
    }
    std::ofstream("output.txt") << r;
}
Не проходит по времени.
Нужен более оптимальный алгоритм...

Добавлено через 39 минут
Либо немного соптимизировать этот
Сгенерировал файлик с матрицей 750х750, моя прога работала 2.5 секунды(а надо за 1 секунду уложиться)

Добавлено через 46 минут
Оптимизировал этот, но все еще не проходит по времени.
Теперь минимальный элемент строки вычисляется во время заполнения матрицы и заносится в массив.
Что еще можно оптимизировать - ума не приложу
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <fstream>
int w[750][750],i,j,n,m,d,k,x,r,q[750],c;
main(){
    std::fstream v("input.txt");
    for (v >> n >> m;i < n;++i)
        for (j=0,q[i] = 999; j < m;++j){
            v >> w[i][j];
            if (w[i][j] < q[i]) q[i] = w[i][j];
        }
    for (i = 0; i < n; ++i){
        for (j = 0; j < m; ++j)
            if ( w[i][j] == q[i] ){
                for (k = x = 0; k < n; ++k)
                    if ( w[k][j] > w[i][j]) {x = 1; break; }
                if (!x) ++r;  
            }
    }
    std::ofstream("output.txt") << r;
}
Добавлено через 23 минуты
Дооптимизировал =)
Теперь проходит.
Возможно, кому-нибудь понадобиться.
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
#include <fstream>
int w[750][750],i,j,n,m,d,k,x,r,q[750],e[750];
main(){
    std::fstream v("input.txt");
    for (v >> n >> m;i < n;++i)
        for (j=0,q[i] = 999; j < m;++j){
            v >> w[i][j]; //ввод матрицы
            if (w[i][j] < q[i]) q[i] = w[i][j];
            //и одновременное забивание наименьшего элемента в строке
            //в специально отведенный под это массив
        }
    
    //заполнение массива наибольших элементов столбцов      
    for (j = 0; j < m; ++j)
        for (i = 0,e[j]=-999; i < n; ++i) 
            if (w[i][j] > e[j]) e[j] = w[i][j];
    
     
    //если минимальный элемент строки совпадает с максимальным столбца
    //то увеличиваем счетчик
    for (i = 0; i < n; ++i)
        for (j = 0; j < m; ++j)
            if (q[i] == e[j])   
                ++r;
    std::ofstream("output.txt") << r;
}
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2011, 20:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос В файл вывести седловые точки матрицы (C++):

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

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

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

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

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

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

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.06.2011, 20:58
Привет! Вот еще темы с ответами:

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

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

Седловые точки - C++
я прогу написа, но если в матрице более одной седловой точки или несколько минимальных чисел в одной строке то не работает, помогите...

седловые точки - C++
Проверьте пожалуйста правильно ли все. не могу разобраться... Дана целочисленная матрица. Определить номера строк и столбцов всех...


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

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

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