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

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

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

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

24.12.2013, 00:54. Просмотров 213. Ответов 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 минуты
Нету идей?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.12.2013, 00:54
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Оптимизировать алгоритм (C++):

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

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

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

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

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

1
valeriikozlov
Эксперт С++
4677 / 2503 / 322
Регистрация: 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].
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.12.2013, 07:51
Привет! Вот еще темы с ответами:

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

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

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

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


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

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

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