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

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

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

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

24.12.2013, 00:54. Просмотров 187. Ответов 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++ Помогите оптимизировать код
C++ оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб)
C++ Нужно оптимизировать
Оптимизировать перебор C++
C++ Как оптимизировать код?
C++ Оптимизировать функцию
C++ Оптимизировать код
C++ Оптимизировать алгоритм, чтобы уменьшить количество операций для проверок деления
C++ Оптимизировать и минимализировать код
C++ Оптимизировать алгоритм проверки ударения слов
C++ Вывести все правильные скобочные выражения (оптимизировать алгоритм, ускорить работу кода)
Оптимизировать код C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4663 / 2489 / 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     Оптимизировать алгоритм
Ответ Создать тему
Опции темы

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