2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Нахождение максимального количества пар в списке
Сообщение03.11.2018, 20:42 


14/09/18
15
Здравствуйте! Во время решения задачи (на python) столкнулся с проблемой.
Дан отсортированный по возрастанию список чисел. Необходимо найти максимальное возможное количество пар чисел $(a, b)$, для которых верно неравенство $b =< 2a$
Например, для списка [1, 3, 4] максимальным количеством таких пар будет 1.
Попытки решения:
1. Прикинул полный перебор. Не подойдёт, максимальная возможная длина списка равна 50000.
2. Пробовал разбить на пары при помощи itertools.combinations(), но думаю, это не имеет смысла, ведь пары тоже придётся комбинировать.
Пожалуйста, помогите. Заранее благодарен.
P. S. Обращение к модераторам: надо ли список оформить тегом code? Если надо, я могу оформить.

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение03.11.2018, 20:57 
Заслуженный участник


09/05/12
25179
leon_ard в сообщении #1351490 писал(а):
P. S. Обращение к модераторам: надо ли список оформить тегом code? Если надо, я могу оформить.
Не обязательно. Но далее лучше для такого рода вставок использовать моноширинный шрифт (см. тэг "tt"), получится так: [1, 3, 4]

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение03.11.2018, 21:11 
Заслуженный участник


27/04/09
28128
leon_ard
Зафиксируйте первый или второй элемент пары — каким может быть оставшийся? Теперь увеличьте или уменьшите его немного — каких изменений можно ожидать от множества допустимых значений оставшегося? Это должно навести на мысль о линейном алгоритме.

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение03.11.2018, 21:19 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
leon_ard в сообщении #1351490 писал(а):
Необходимо найти максимальное возможное количество пар чисел $(a, b)$, для которых верно неравенство $b =< 2a$
Я так понимаю, числа $a$ и $b$ - не обязательно стоят рядом, так? Лучше это условие в явном виде указывать.

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение03.11.2018, 21:26 
Заслуженный участник


09/05/12
25179
leon_ard в сообщении #1351490 писал(а):
Дан отсортированный по возрастанию список чисел. Необходимо найти максимальное возможное количество пар чисел $(a, b)$, для которых верно неравенство $b =< 2a$
Например, для списка [1, 3, 4] максимальным количеством таких пар будет 1.
Кстати, в условии явно что-то не оговорено или неправильно сформулировано. Для такого списка пар, удовлетворяющих условию, больше: (3,1), (4,1), (4,3), (3,4). Или дополнительно неявно предполагается, что $a \le b$?

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 02:59 


21/05/16
4292
Аделаида
rockclimber в сообщении #1351500 писал(а):
Я так понимаю, числа $a$ и $b$ - не обязательно стоят рядом, так?

В переписке выяснилось, что обязательно :-) Индекс b на один больше индекса a.
leon_ard в сообщении #1351490 писал(а):
1. Прикинул полный перебор. Не подойдёт, максимальная возможная длина списка равна 50000.

Ну и почему не подойдёт? Сложность перебора - O(n). $n=50000$ сойдет. Вот если было бы 10 миллиардов...

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 03:02 
Заслуженный участник


09/05/12
25179
kotenok gav в сообщении #1351545 писал(а):
В переписке выяснилось, что обязательно :-) Индекс b на один больше индекса a.
Тогда это очевидный линейный перебор. Меньше - невозможно, больше - не нужно.

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 08:37 


14/09/18
15
Pphantom в сообщении #1351495 писал(а):
leon_ard в сообщении #1351490 писал(а):
P. S. Обращение к модераторам: надо ли список оформить тегом code? Если надо, я могу оформить.
Не обязательно. Но далее лучше для такого рода вставок использовать моноширинный шрифт (см. тэг "tt"), получится так: [1, 3, 4]
Хорошо
rockclimber в сообщении #1351500 писал(а):
leon_ard в сообщении #1351490 писал(а):
Необходимо найти максимальное возможное количество пар чисел $(a, b)$, для которых верно неравенство $b =< 2a$
Я так понимаю, числа $a$ и $b$ - не обязательно стоят рядом, так? Лучше это условие в явном виде указывать.
Приношу извинения, действительно забыл обговорить это условие. Числа $a$ и $b$ рассматриваются так, что $b > a$ (но их индексы могут отличаться на любое число). Поэтому варианты (3, 1), (4, 1) и (4, 3) не подойдут.
kotenok gav в сообщении #1351545 писал(а):
leon_ard в сообщении #1351490 писал(а):
1. Прикинул полный перебор. Не подойдёт, максимальная возможная длина списка равна 50000.

Ну и почему не подойдёт? Сложность перебора - O(n). $n=50000$ сойдет. Вот если было бы 10 миллиардов...
Не совсем так. Индекс $b$ может быть больше индекса $a$ на любое число, поэтому сложность перебора считаем по формуле $N = n_1n_2...n_n$, что намного больше 10 миллиардов

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 08:54 


21/05/16
4292
Аделаида
Но в переписке вы говорили, что они стоят рядом.

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 09:08 


14/09/18
15
Наверное, я тогда написал не очень понятно. Я подразумевал, что индекс $b$ строго больше индекса $a$

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 09:20 


21/05/16
4292
Аделаида
Тогда надо брать цент. пару и уменьшать a с увелечением b, пока не нарушится неравенство.

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 12:18 


14/09/18
15
Что считать центральной парой в этом списке [1, 3, 4]?
А в этом [3, 4, 10]?

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 12:26 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
kotenok gav в сообщении #1351565 писал(а):
огда надо брать цент. пару и уменьшать a с увелечением b, пока не нарушится неравенство.
Надо перебрать все возможные $a$ и все возможные $b$. arseniiv выше написал, как.

arseniiv в сообщении #1351498 писал(а):
Это должно навести на мысль о линейном алгоритме.
Что вы имеете в виду под линейным алгоритмом? Перебор за линейное время?

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 12:42 
Заслуженный участник


27/04/09
28128
Зачем брать центральную пару? Ну можно же заметить, что если $a'>a$, то $b\leqslant 2a\Rightarrow b\leqslant 2a'$. Что это говорит о возможности считать пары?

rockclimber в сообщении #1351586 писал(а):
Что вы имеете в виду под линейным алгоритмом? Перебор за линейное время?
Угу. Если вы намекаете на кое-что, что мы тут не будем упоминать явно, чтобы не заспойлить решение целиком, то раз здесь нужно лишь посчитать число удовлетворяющих пар, а не перебирать их, квадратичность превращается в линейность.

P. S. Хм, хотя «найти максимальное возможное количество пар» можно понимать и как перебор… Тогда не линейный, конечно.

 Профиль  
                  
 
 Re: Нахождение максимального количества пар в списке
Сообщение04.11.2018, 12:48 
Заслуженный участник


09/05/12
25179
Остался, пожалуй, только один вопрос, ответ на который влияет на реализацию: под словом "список" в исходном условии понимался именно соответствующий тип данных или массив тоже сойдет?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group