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

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

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

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

21.06.2011, 20:58. Просмотров 734. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.06.2011, 20:58     В файл вывести седловые точки матрицы
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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