Используя python, как я могу объединить или объединить два списка, чтобы их значения не перекрывались?

Question

Прежде всего, я прошу прощения за мой неточный словарный запас. Я абсолютный новичок. В любом случае, я пытаюсь решить эту проблему: http://projecteuler.net/problem=1

Если говорить кратко, я пытаюсь написать скрипт, который найдет сумму всех кратных 3 или 5 ниже 1000.

Мой (чрезвычайно простой) подход был с этой программой:

##Multiples of 3
x = range(3, 1000, 3)

##Multiples of 5
y = range(5, 1000, 5)

a = sum(x)
b = sum(y)
n = a + b

print n

Я понял, что это было неправильно, потому что есть числа вроде 15, которые включены дважды (это кратное как 5, так и 3) Так есть ли способ исправить это, или я подхожу к этой проблеме с совершенно неправильной точки зрения? Или мне нужно просто больше учиться, прежде чем пытаться решить эту проблему? Я также прошу прощения, если это было объяснено в предыдущем посте, но я немного осмотрелся.

Answer 1

Это называется принципом исключения включения, поэтому вы можете делать как

##Multiples of 3
x = range(3, 1000, 3)

##Multiples of 5
y = range(5, 1000, 5)

##multiple of 15 are counted twice
z=range(15,1000,15)


a = sum(x)
b = sum(y)
c = sum(z)
n = a + b -c
print(n)

, но красота заключается в использовании генераторов или списочных представлений

a = sum(i for i in range(1000) if i%3 == 0 or i%5 == 0 )
print(a)

Где% - по модулю и остаток в целочисленном делении.Хорошая вещь в этом состоит в том, что коды читаются очень бегло и являются прямым переводом правил и могут быть прочитаны слева направо.

Время выполнения обоих алгоритмов зависит от n в этом случае равно 1000. Если n будет, например,1000000000 вам придется долго ждать завершения.Если вы примените немного математики, вы можете обнаружить, что

sum(a for a in range(a1,a2,n)) 

на самом деле арифметическая прогрессия , и общая сумма может быть вычислена за постоянное время независимо от того, насколько велико n.http://en.wikipedia.org/wiki/Project_Euler#Example_problem_and_solutions

Answer 2

Вы можете использовать set для устранения дубликатов:

>>> len(x)
333
>>> len(y)
199
>>> s = set(x + y)
>>> len(s)
532

Тогда вы можете sum члены набора вместо.

Answer 3

Простой метод:

sum(set(x+y))

set s обладает достаточным количеством функций, которые вы найдете полезными для задач PE.

Вы также можете сделать это простым циклом по всему диапазону довольно легко.

Answer 4

Для объединения отсортированных последовательностей вы можете использовать heapq.merge:

import heapq
print list(heapq.merge(xrange(3, 20, 3), xrange(5, 20, 5)))
# -> [3, 5, 6, 9, 10, 12, 15, 15, 18]

Чтобы удалить дубликаты, вы можете использовать unique_justseen рецепт из документации itertools :

print list(unique_justseen([3, 5, 6, 9, 10, 12, 15, 15, 18]))
# -> [3, 5, 6, 9, 10, 12, 15, 18]

В этом случае unique_justseen() можно упростить до:

from itertools import groupby, imap
from operator  import itemgetter

def unique_justseen(iterable):
    return imap(itemgetter(0), groupby(iterable))

Эти функции не требуют, чтобы входные аргументы были последовательностями. Они принимают произвольные итерации (включая бесконечные), например, чтобы генерировать бесконечную последовательность, кратную 3 или 5:

import heapq
from itertools import count, takewhile

m3, m5 = count(3, 3), count(5, 5) 
m3_5 = heapq.merge(m3, m5)
uniq_m3_5 = unique_justseen(m3_5) # *all* unique multiples of 3 or 5

Чтобы найти решение:

print sum(takewhile(lambda x: x < 1000, uniq_m3_5))
# -> 233168
# check that it is correct
print sum(set(range(3, 1000, 3) + range(5, 1000, 5)))
# -> 233168
print sum(x for x in xrange(1000) if x % 3 == 0 or x % 5 == 0)
# -> 233168
print sumk(3, 1000) + sumk(5, 1000) - sumk(15, 1000)
# -> 233168

Где sumk():

def sumk(k, n):
    m = (n-1)//k
    return k*m*(m+1)//2

Формула взята из ссылки Википедии , предоставленной @ralu.

Answer 5

Вы ищете наборы .

##Multiples of 3
x = range(3, 1000, 3)

##Multiples of 5
y = range(5, 1000, 5)

x = list(set(x) - set(y))

В зависимости от того, что вы делаете, вам придется изменить код.Выше все удаляет все в y из x.Это как списки, но вы можете делать арифметику на предметах.

Answer 6

Я не знаю, является ли это менее эффективным, но создание двух наборов и выполнение логических операций с обоими для удаления дубликатов кажется излишним, поскольку определение набора является

неупорядоченнымколлекция из различных объектов, которые могут быть изменены
(выделение добавлено)

, поэтому просто добавьте оба диапазона в один набор и дайте "создать"установить удалить дубликаты:

sum(set(range(3, 1000, 3) + range(5, 1000, 5)))