DjangoBB LoFi version

Полная версия: Помогите продумать алгоритм, пожалуйста.

Начало » Центр помощи » Помогите продумать алгоритм, пожалуйста.

KindBeetle

Сен. 16, 2016 15:31:10

Я новичок. Не судите строго.
Нужно проверить, можно ли получить число n из k простых чисел. К примеру 15 можно получить из суммы 2 + 13.
Простые числа у меня получаются только списком (или словарем). Т. е. проверить я могу только перебором.
К примеру список простых чисел prime
Тогда:

 prime = [2, 3, 5, 7, 11, 13....]
n = 10 # число, которое нужно получить
k = 2 # количество слагаемых
a = 0
for i in simple:
    for j in simple:
        if i + j == n:
            a = a + 1
        else:
            a = a
if a > 0:
    print("True")
else:
    print("False")

Так вот, а как проверить, можно ли получить число n из k слагаемых (простых чисел), если количество слагаемых не определенное число, а переменная от 1 до 100? И n, соответственно, больше 200. Допустим 1523.

ZerG

Сен. 16, 2016 16:45:15

ОБерните код в тег - нечитабельно

KindBeetle

Сен. 17, 2016 08:49:36

ZerG
ОБерните код в тег - нечитабельно

исправил.

Shaman

Сен. 17, 2016 10:55:42

 from itertools import combinations
primes = [2, 3, 5, 7, 11, 13]
n = 12 # число, которое нужно получить
k = 2 # количество слагаемых
a = 0
for i in combinations(primes, k):
    if sum(i) == n:
        a = a + 1
if a > 0:
    print("True")
else:
    print("False")

Соответственно, берём код combinations и делаем из него вариант для начинающих

 combs = []
iterable = [2, 3, 5, 7, 11, 13]
r = k = 2
 
pool = tuple(iterable)
n = len(pool)
assert r <= n
indices = list(range(r))
combs.append(tuple(pool[i] for i in indices))
while True:
    for i in reversed(range(r)):
        if indices[i] != i + n - r:
            break
    else:
        break
    indices[i] += 1
    for j in range(i+1, r):
        indices[j] = indices[j-1] + 1
    combs.append(tuple(pool[i] for i in indices))
 
print(combs)

KindBeetle

Сен. 18, 2016 15:32:15

Shaman, нашел неточность.
В данном варианте он перебирает разные варианты. К примеру при К = 3 ответ будет True, т.к. 2+3+5 = 10, но при К = 5 False, хотя 10 можно получить из К простых чисел. 2+2+2+2+2=10. Нету условия, что каждое слагаемое должно быть отличным от других.
Пробую разобраться.