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

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

Войти
Регистрация
Восстановить пароль
 
Wolkodav
601 / 454 / 32
Регистрация: 18.09.2012
Сообщений: 1,685
#1

Оптимизировать алгоритм - C++

24.12.2013, 00:54. Просмотров 194. Ответов 1
Метки нет (Все метки)

Приятель подкинул задачку:
Получить новую матрицу В, элемент b[i][j] которой равен наименьшему из элементов a[k][l] исходной матрицы, где k меняется от i до n, а l – от 1 до j. С у четом, что Матрица А исходная.
Он предложил решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void preobr (int **A, int **&B,const int n,const int m)
{
B=new int*[n];
for (int i=0; i<n; i++)
    B[i]=new int [m];
for (int i=0; i<n; i++)
    for (int j=0; j<m; j++)
    {
        int min=A[i][j];
        for (int k=i; k<n; k++)
            for (int l=0; l<j; l++)
                if (A[k][l]<min) min=A[k][l];
                    B[i][j]=min;
    }
}
Преподователь сказала, что нужно сделать оптимальнее
Чтобы трудоемкость была не n^4, а 3*n^2. Ничего лучше не придумали, может хоть кто-нибудь идейку подскажет?

Добавлено через 1 час 54 минуты
Нету идей?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.12.2013, 00:54     Оптимизировать алгоритм
Посмотрите здесь:

Оптимизировать алгоритм проверки ударения слов - C++
Здравствуйте, уважаемые участники форума. На образовательном сайте решал задание, система решение приняла. Так как я неопытный в...

оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб) - C++
Здравствуйте. По заданию требовалось составить программу для подсчета вхождений разных сочетаний букв с алфавита от 1 буквы до 4 в...

Оптимизировать алгоритм, чтобы уменьшить количество операций для проверок деления - C++
Всего один вопрос. Как оптимизировать алгоритм, чтобы уменьшить количество операций для проверок деления? #include &lt;iostream&gt; #include...

Вывести все правильные скобочные выражения (оптимизировать алгоритм, ускорить работу кода) - C++
есть код, нужно cout и cin перевести на printf и scanf дополнительных библиотек не подключать! проблема в том что при вводе 14 работает...

Оптимизировать код - C++
Первое число входного потока - количество чисел Дальше идут те самые числа Надо найти кол-во пар чисел, для которых выполняется nums &lt;=...

Оптимизировать перебор - C++
Неделю учу С++, так что прошу не гадить. Надо уменьшить время работы. Задача: Вступление — Брат мой, Магистр Ордена хочет узнать...

Нужно оптимизировать - C++
Есть задание, есть готовый код. Но он не проходит скоростной режим, нужно оптимизировать, помогите плз) #include &lt;iostream&gt; ...

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

Оптимизировать код - C++
Доброго времени суток, как можно оптимизировать код что бы он быстрее работал ? Дана последовательность из n чисел a1, a2,..., an. C...

Как оптимизировать код? - C++
Вот такой код, написанный для микроконтроллера импульсного блока питания. Просто интересно мнение, что можно поменять и изменить для...

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

Как оптимизировать код? - C++
Как оптимизировать код, чтобы работала программа быстрее #include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;iomanip&gt; using namespace...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
24.12.2013, 07:51     Оптимизировать алгоритм #2
Цитата Сообщение от Wolkodav Посмотреть сообщение
может хоть кто-нибудь идейку подскажет?
идея здесь только одна может быть. внимательно читаем условие и понимаем что нужно искать минимальное число в прямоугольном секторе ограниченном точками A[n-1][0] и A[i][j] (точки находятся на концах диагонали прямоугольника). Так вот если идти не с 0-ой строки вниз, а наоборот с n-1 строки вверх то получится, что для очередной точки B[i][j] можно минимум вычислить так: выбрать минимально значение из трех значений: A[i][j], B[i+1][j], B[i][j-1].
И все, единственное остается проверять что не выходим за границы матрицы, когда берем значения: B[i+1][j], B[i][j-1].
Yandex
Объявления
24.12.2013, 07:51     Оптимизировать алгоритм
Ответ Создать тему
Опции темы

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