Python-сообщество

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.

Отредактировано KindBeetle (Сен. 17, 2016 08:50:00)

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. Нету условия, что каждое слагаемое должно быть отличным от других.
Пробую разобраться.

Отредактировано KindBeetle (Сен. 18, 2016 15:33:03)

Python-сообщество

Уведомления

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

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

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

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

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

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

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

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

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

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

Board footer