Как посчитать сумму двух наибольших элементов(наибольшую сумму двух элементов) в случайно сгенерированном списке, при условии, что полученное значение должно при делении на 3(или любое другое число) давать остаток 1? Или, например, сумма двух наибольших элементов, при условии, что их частное равно 10.
from random import randint as rnd random_list = [rnd(0, 1000) for x in range(20)] random_list.sort(reverse=True) print(random_list) [985, 937, 918, 905, 891, 791, 714, 709, 698, 637, 569, 541, 501, 464, 318, 270, 264, 176, 159, 107]
В голову пришла следующая идея: использовать метод combinations из модуля itertools, который выдает комбинации длиной r из iterable без повторяющихся элементов. В моем случае r = 2. Полученные пары мы суммируем, а дальше уже все просто.
from itertools import combinations
from random import randint as rnd
random_list = [rnd(0, 1000) for x in range(20)]
print(random_list)
tuples = list(combinations(random_list, 2))
sums = [(x[0] + x[1]) for x in tuples if (x[0] + x[1])%3 == 1]
for x in tuples:
try:
if x[0] + x[1] == max(sums):
print('Сумма равна: '+str((x[0] + x[1])), 'из элементов списка random_list: '+(str(x[0])+
' с индексом '+str(random_list.index(x[0])))+' и', (str(x[1])+' с индексом '+str(random_list.index(x[1]))))
except ValueError:
print('Таких чисел нет')
[534, 875, 608, 5, 899, 76, 355, 242, 756, 771, 451, 20, 852, 300, 523, 991, 886, 258, 846, 683]
Сумма равна: 1843 из элементов списка random_list: 852 с индексом 12 и 991 с индексом 15
Чтобы найти наибольшую сумму maxsum из двух разных элементов списка L, такую что maxsum % 3 == 1, есть линейный алгоритм:
import heapq
import math
def maxsum_modulo3_1(L):
remainder = [], [], [] # all remainder[r] % 3 == r
for x in L:
remainder[x % 3].append(x)
# 00 01 02
# 11 12
# 22
maxsum = sentinel = -math.inf # less than any integer sum
if remainder[0] and remainder[1]: # (0 + 1) % 3 == 1
maxsum = max(remainder[0]) + max(remainder[1])
if len(remainder[2]) > 1: # (2 + 2) % 3 == 1
maxsum = max(maxsum, sum(heapq.nlargest(2, remainder[2])))
if maxsum is sentinel:
raise ValueError("can't find any sum % 3 == 1")
return maxsum
-
сперва все элементы сортируются по их остаткам от деления на 3:
all remainder[r] % 3 == r
-
затем находятся наибольшие элементы, которые могут образовать сумму, которая делится на три с остатком один, если они есть:
(remainder[0] and remainder[1]) or len(remainder[2]) > 1
в противном случае, если не существует ни одной суммы, удовлетворяющей условию, то выбрасывается исключение
-
наибольшая сумма возвращается.
>>> maxsum_modulo3_1([10, 8, 8, 0]) 16
import random
list_ = list(range(50))
random.shuffle(list_)
def maximum_n2(n_max, *slist, d=3):
'''raise TypeError: (m % d) != 1'''
for n in slist:
m = n_max + n
if (m % d) == 1:
return m
return maximum_n2(*slist)
max_n2 = maximum_n2(*sorted(list_, reverse=True))
print(max_n2)
В общем случае требуется перебор, потому что можно представить себе массив, у которого вообще не будет пары таких элементов.
Поэтому лучшее, что можно сделать — это выполнять проверки «сверху вниз», отсортировав предварительно массив, чтобы при нахождении такой пары дальше не проверять…
