Форум программистов, компьютерный форум, киберфорум
Java для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
0 / 0 / 0
Регистрация: 20.02.2021
Сообщений: 17
1

Решить задачу с уровнем сложности меньше чем О(n^2)

05.03.2021, 19:34. Просмотров 2351. Ответов 31
Метки java (Все метки)


Нужно решить задачу,
У нас есть n гирь, расположенных от самого легкого до самого тяжелого (их веса указаны в поле веса). Несколько гирь могут иметь одинаковый вес. Для простоты мы предполагаем, что вес каждого груза является целым числом в граммах. Реализуйте метод, который возвращает, можем ли мы выбрать любые 2 веса, чтобы сумма их весов была точно h.

Java
1
2
3
4
5
6
7
public class SpravneZavazia {
 
        public static boolean obsahujeVyberSHmotnostou(int[] zavazia, int h) {
                return true;
        }
 
}
Нужно решить данное задание лучшем чем o(n^2)
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.03.2021, 19:34
Ответы с готовыми решениями:

Найти сумму баллов за задачу у n учеников меньше чем за остальные
Вводятся баллы за задачи нескольких учеников. Нужно определить наилегчайшую задачу(сумма баллов за...

что, где и как нужно изменить чтоб решить задачу? ->Сколько лет доходов было меньше 1000, но больше 500 у.е? когда фирма понесла наибольший убыток?
Program Pr_11; Type mas=array of real; Var k:integer; y: mas; S,sa:real; kol: integer;...

Решить задачу симплекс-методом и написать двойственную к ней задачу
решите пожалуйста

Помогите решить задачу сломал голову не знаю как решить.
1)Определить максимальный элемент в каждой строке матрицы и заменить все элементы 2 столбца на этот...

31
280 / 140 / 63
Регистрация: 21.05.2016
Сообщений: 432
05.03.2021, 21:56 2
Цитата Сообщение от matuf Посмотреть сообщение
возвращает, можем ли мы выбрать любые 2 веса, чтобы сумма их весов была точно h.
Для отсортированного массива можно пойти от обратного и попробовать представить какие массивы длины > 2 будут удовлетворять такому условию.
0
327 / 253 / 107
Регистрация: 14.06.2016
Сообщений: 513
05.03.2021, 22:22 3
Лучший ответ Сообщение было отмечено Arsegg как решение

Решение

Java
1
2
3
4
5
6
7
    public static boolean obsahujeVyberSHmotnostou(int[] zavazia, int h) {
        Set<Integer> weights = new HashSet<>();
        for (int w : zavazia)
            if (weights.contains(h - w)) return true;
            else weights.add(w);
        return false;
    }
0
2970 / 2512 / 778
Регистрация: 05.07.2013
Сообщений: 12,162
05.03.2021, 22:24 4
Берём первое число х, второе должно быть h-x, массив отсортирован - бинарный поиск
0
3275 / 2337 / 425
Регистрация: 28.04.2012
Сообщений: 7,821
05.03.2021, 23:01 5
Цитата Сообщение от xoraxax Посмотреть сообщение
Берём первое число х, второе должно быть h-x, массив отсортирован - бинарный поиск
И в худшем случае, когда подходят только последнее+предпоследнее будет O(n logn)

Вот O(n):
0
Миниатюры
Решить задачу с уровнем сложности меньше чем О(n^2)  
3275 / 2337 / 425
Регистрация: 28.04.2012
Сообщений: 7,821
05.03.2021, 23:09 6
Цитата Сообщение от xoraxax Посмотреть сообщение
Берём первое число х, второе должно быть h-x, массив отсортирован - бинарный поиск
А, возможно, я не так понял, для чего тут бинарный поиск и что с его результатом делать ) Тогда да, нужно использовать бинарный поиск.
0
280 / 140 / 63
Регистрация: 21.05.2016
Сообщений: 432
05.03.2021, 23:10 7
Цитата Сообщение от korvin_ Посмотреть сообщение
Вот O(n):
Да и если, например, без HashSet:
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
        public static boolean obsahujeVyberSHmotnostou(int[] zavazia, int h) {
            int lowest = 0;
            int highest = zavazia.length - 1;
            
            while (lowest < highest) {
                System.out.println(zavazia[lowest] + " " + zavazia[highest]);
                if (zavazia[lowest] + zavazia[highest] != h)
                    return false;
                
                if (zavazia[lowest] + zavazia[highest] > h)
                    highest--;
                else 
                    lowest++;
            }
            return true;
 
        }
0
2970 / 2512 / 778
Регистрация: 05.07.2013
Сообщений: 12,162
05.03.2021, 23:11 8
korvin_, наверно так, твой вариант выглядит лучше
0
3275 / 2337 / 425
Регистрация: 28.04.2012
Сообщений: 7,821
05.03.2021, 23:26 9
Цитата Сообщение от xoraxax Посмотреть сообщение
твой вариант выглядит лучше
В мой вариант можно добавить предложенный тобой бинарный поиск, немного адаптированный: в случае неудачи он должен вернуть пару индексов элементов, например для шага 1 индексы элементов 9 и 11. Тогда мы берём меньшее или большее число (в зависимости от того в какую сторону двигаемся) и повторяем бинарный поиск в противоположную сторону, чтобы найти индексы для 3 и 5 на втором шаге. В худшем случае, как я понимаю, будет O(n), но в остальном это будет быстрее, хоть и не O(logn).

Добавлено через 3 минуты
Цитата Сообщение от Tavashi Посмотреть сообщение
Java
1
2
                if (zavazia[lowest] + zavazia[highest] != h)
                    return false;
наоборот.

Цитата Сообщение от Tavashi Посмотреть сообщение
Java
1
return true;
наоборот.
0
280 / 140 / 63
Регистрация: 21.05.2016
Сообщений: 432
05.03.2021, 23:31 10
Цитата Сообщение от korvin_ Посмотреть сообщение
наоборот.
Нет, нам же надо найти случай когда любые два элемента != сумме h.
Иначе true - любые два элемента массива есть сумма h.
0
3275 / 2337 / 425
Регистрация: 28.04.2012
Сообщений: 7,821
06.03.2021, 00:29 11
Цитата Сообщение от Tavashi Посмотреть сообщение
Нет, нам же надо найти случай когда любые два элемента != сумме h.
Иначе true - любые два элемента массива есть сумма h.
Что?
0
280 / 140 / 63
Регистрация: 21.05.2016
Сообщений: 432
06.03.2021, 01:32 12
Цитата Сообщение от korvin_ Посмотреть сообщение
Что?
В задаче "любые два" элемента из массива образуют сумму h. Проверять, соответственно, нужно все пары. То есть, если в задаче было бы условие "найдутся такие два элемента, что их сумма равна h", тогда нужно было бы делать наоборот и находить только одну такую пару.
0
2970 / 2512 / 778
Регистрация: 05.07.2013
Сообщений: 12,162
06.03.2021, 01:37 13
Tavashi, выбрать 2 любых элемента (а и б), таких, что их сумма равна ха (а + б = х)
0
280 / 140 / 63
Регистрация: 21.05.2016
Сообщений: 432
06.03.2021, 01:45 14
Использование HashSet в редких случаях может увеличить асимптотическую сложность до O(log(n)).

Добавлено через 4 минуты
Цитата Сообщение от xoraxax Посмотреть сообщение
выбрать 2 любых элемента (а и б), таких, что их сумма равна ха (а + б = х)
Ок. Понял задачу иначе. Намудрил ...
0
1991 / 1097 / 358
Регистрация: 02.09.2015
Сообщений: 2,894
06.03.2021, 10:03 15

Не по теме:

Tavashi, xoraxax, korvin_ - товарищи, ну вы что? vcrop уже решил за линию.



Добавлено через 5 минут

Не по теме:

Цитата Сообщение от Tavashi Посмотреть сообщение
Использование HashSet в редких случаях может увеличить асимптотическую сложность до O(log(n)).
Если в бакете элементов меньше 8, то сложность линейная - O(N).

0
3275 / 2337 / 425
Регистрация: 28.04.2012
Сообщений: 7,821
06.03.2021, 10:31 16
Arsegg,
во-первых, ценой значительно большего расхода памяти (в худшем случае примерно O(n)),
во-вторых, с бинарным поиском в среднем будет примерно O(logn)
0
1991 / 1097 / 358
Регистрация: 02.09.2015
Сообщений: 2,894
06.03.2021, 13:58 17
Цитата Сообщение от korvin_ Посмотреть сообщение
с бинарным поиском в среднем будет примерно O(logn)
Чтобы задействовать бин поиск, нужно предварительно отсортировать массив: O(n * log(n)).

Добавлено через 7 минут
Цитата Сообщение от korvin_ Посмотреть сообщение
ценой значительно большего расхода памяти
Учитывая, что входной массив O(N) - разница в константу особой роли не сыграет.

Добавлено через 3 минуты
korvin_, ближе к вечеру могу представить улучшенный вариант уважаемого vcrop без доп. памяти: O(1) - и временем работы O(N), специально для вас.

Добавлено через 6 минут
Цитата Сообщение от korvin_ Посмотреть сообщение
с бинарным поиском в среднем будет примерно O(logn)
И с бинарным поиском, даже если на вход подавать отсортированный массив, время работы будет O(N * log(N)), т. к. будет N запросов на бин. поиск O(log(n).
0
xoraxax
06.03.2021, 14:14
  #18

Не по теме:

Тему не читай ответ пиши

0
3275 / 2337 / 425
Регистрация: 28.04.2012
Сообщений: 7,821
06.03.2021, 16:05 19
Arsegg, перечитай тему, спокойно, медленно, каждое сообщение.
0
1991 / 1097 / 358
Регистрация: 02.09.2015
Сообщений: 2,894
06.03.2021, 18:07 20
Цитата Сообщение от matuf Посмотреть сообщение
можем ли мы выбрать любые 2 веса, чтобы сумма их весов была точно h.
korvin_, значит ли это, что все суммы любых двух весов должны быть точно равны h или что можно найти такие два веса, что их сумма точно равна h?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.03.2021, 18:07

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Решить задачу 2-SAT (задачу выполнимости)
Здравствуйте. Помогите, пожалуйста, разобраться. Пытаюсь реализовать алгоритм, решающий задачу...

Timer.Interval: чем меньше интервал, тем меньше точность
Нужно написать программу, которая каждую мс будет выполнять определенное действие. За основу решил...

Очень нужно решить задание,сдаю первую сессию и возникли сложности...
Ув. участники форума! Не могу решить задачу такого рода: По трем заданным матрицам A(N,N), В(N,N)...

Вычислить произведение значений, которые меньше чем -1 или больше, чем 4
Вычислить произведение значений, которые меньше чем -1 или больше, чем 4.

Вычислить сумму и количество отрицательных элементов массива, которые больше чем b и меньше чем a
Требуется помощь в написании программы по обработке одномерного массива в Delphi. Условие:...

Рекурсия: определите подмножество данных чисел, дающих сумму меньше, чем Z и с количеством членов большим чем K
имеется n различных натуральных чисел. определите подмножество данных чисел, дающих сумму меньше,...


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

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

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