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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ не получается сделать задание с оператором -> http://www.cyberforum.ru/cpp-beginners/thread323950.html
//тема про оператор стрелка -> я так понимаю задание надо сделать с использованием этого оператора //напишите программу, в которой определен вектор указателей на строки. Организуйте //перебор вектора с отображением каждой строки и ее размера #include <iostream> #include <vector> #include <string> using namespace std; int main() {
C++ Вопрос связанный с экзаменом(строки,генератор случайных чисел,матрицы) ребят, нужна ваша помощь) 22.06.11 г, то бишь завтра, в 13-40 экзамен по программированию. Требуется решить 1 задачу на С++ и ответить на ряд вопросов. На вопросы то я отвечу, теория мне всегда легко давалась, а вот с практикой посложнее. Суть просьбы: нужен человек, который смог бы помочь. Пример задач, который будет на экзамене я могу выслать, дабы человечек, который возьмется, знал за... http://www.cyberforum.ru/cpp-beginners/thread323931.html
C++ Student+ Wolfram Alpha от Wolfram Researh.
Student+ Wolfram Alpha от Wolfram Researh. Оглавление: Внимательно прочитайте данную инструкцию от начала до конца! 1. Основные операции 2. Знаки сравнения 3. Логические символы
Вывод определенного количества знаков до запятой C++
Как в С++ с помощью оператора cout выводить число с нужным мне количеством знаков ДО запятой? Т.е. например выводятся числа < 100, при этом числа от 0 до 9 выводятся в виде 00 - 09. Т.е. нужен аналог std::setprecision(), только наоборот)
C++/CLI WinForms Не получается построить график в PictureBox http://www.cyberforum.ru/cpp-beginners/thread323897.html
Народ здрасьте!! Может кто подскажет? Пытаюсь нарисовать график в PictureBox, и проблема в том, что не могу обратиться к его элементам из другого файла. Я неплохо программирую на классическом C, но в ООП только полез. Код такой: /*------------------------------------------------------------------------*/ #include <Windows.h> #include <math.h> #include "Form1.h" #define SizeAr 32000 using...
C++ Перестановка блоков матрийцы Дана действительная квадратная матрица порядка 2n. Получить новую матрицу, переставляя её блоки размера n на n, заполнение матрицы и её порядок происходит вручную. подробнее

Показать сообщение отдельно
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
21.06.2011, 20:58     В файл вывести седловые точки матрицы
Доброго времени суток.
В 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 13:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru