Как разбить числа от 1 до n на три множества так, чтобы сумма чисел в каждом была одинаковой?
Вам дано число n. Разбейте все натуральные числа от 1 до n на три множества так, чтобы сумма чисел в каждом множестве была одинаковой. Не понимаю с какой стороны зайти
Я сделал, однако алгоритм не работает так как надо: Такой должен быть вывод при n = 5
2
1 4
2
2 3
1
5
Это мой код:
n = int(input())
def divide_numbers(n):
if n * (n + 1) / 2 % 3 == 0:
numbers = [i for i in range(1, n+1)]
total_sum = sum(numbers)
set_sum = total_sum // 3
sets = [[], [], []]
for num in numbers:
if sum(sets[0]) + num <= set_sum and len(sets[0])<2:
sets[0].append(num)
elif sum(sets[1]) + num <= set_sum and len(sets[1])<2:
sets[1].append(num)
else:
sets[2].append(num)
return sets
else:
return -1
a = divide_numbers(n)
if a != -1:
first = a[0]
len_first = len(first)
second = a[1]
len_second = len(second)
thired = a[2]
len_thired = len(thired)
print(len_first)
print(*first)
print(" ")
print(len_second)
print(*second)
print(" ")
print(len_thired)
print(*thired)
else: print(a)
Для примера в своем коде я взял n = 5, ниже - вывод:
2
1 2
1
3
2
4 5
Я знаю, что где-то ошибся, не выполняется условие, что сумма множества должна быть одинаковой.
Я сделал, однако алгоритм не работает так как надо: Такой должен быть вывод при n = 5
2
1 4
2
2 3
1
5
Это мой код:
n = int(input())
def divide_numbers(n):
if n * (n + 1) / 2 % 3 == 0:
numbers = [i for i in range(1, n+1)]
total_sum = sum(numbers)
set_sum = total_sum // 3
sets = [[], [], []]
for num in numbers:
if sum(sets[0]) + num <= set_sum and len(sets[0])<2:
sets[0].append(num)
elif sum(sets[1]) + num <= set_sum and len(sets[1])<2:
sets[1].append(num)
else:
sets[2].append(num)
return sets
else:
return -1
a = divide_numbers(n)
if a != -1:
first = a[0]
len_first = len(first)
second = a[1]
len_second = len(second)
thired = a[2]
len_thired = len(thired)
print(len_first)
print(*first)
print(" ")
print(len_second)
print(*second)
print(" ")
print(len_thired)
print(*thired)
else: print(a)
Для примера в своем коде я взял n = 5, ниже - вывод:
2
1 2
1
3
2
4 5
Я знаю, что где-то ошибся, не выполняется условие, что сумма множества должна быть одинаковой.
Ответы (2 шт):
Пункт 0. Очевидно, что при N < 5 ничего сделать нельзя.
Пункт 1. Если N(N+1) не делится на 3, то сделать это нельзя. Или, по-другому, N mod 3 != 1. Таким образом, либо N делится на 3, либо будет остаток 2. Не нарушая общности рассуждений, в случае остатка 2 добавим 0 к набору чисел (выводить его не надо).
Пункт 2. Делим N+1 на 3. Смотрим на число. Есть 2 варианта - оно чётное или нечётное.
Пункт 2.1 Если в пункте 2 нечётное. Рассмотрим блок
1 5 9
2 6 7
3 4 8
(если в пункте 1 был остаток 2, то уменьшите все значения на 1 и не забудьте что не надо выводить 0).
Пункт 3. После выполнения пункта 2 мы получили, что нужно разложить по 3 массивам чётное число троек (или сразу было чётным, или мы разложили 3 тройки). Рассмотрим блок
a a+5
a+1 a+4
a+2 a+3
Такими блоками заполним все числа.
Пример. Пусть мы хотим разложить 14 чисел. Пункт 0 - ок. Пункт 1 - остаток 2. Пусть 2 - частное 5 Пункт 2.1 делаем, в ответ пишем
(0) 4 8
1 5 6
2 3 7
Пункт 3. Первое число, которое не разложили это 9. Добавляем к ответу
(0) 4 8 | 9 14
1 5 6 | 10 13
2 3 7 | 11 12
Думаю принцип понятен. Сложность чисто на вывод массивов, можно сразу выводить без использования доп памяти.
Ошибка в неправильном алгоритме. Самое неприятное место - условие and len(sets[0])<2. Оно запрещает помещать в первое множество больше двух чисел. Это точно не будет работать для больших n. Возможно, ваш алгоритм можно привести в порядок, но не понятно на какой логике он основан.
Дальше мой ответ повторяет соседний, но изложен по-другому.
Обозначим pn разбиение на группы для n чисел, если оно существует. Из pn строится pn+6 добавлением к подмножествами попарных сумм: (n + 1) + (n + 6) = (n + 2) + (n + 5) = (n + 3) + (n + 4).
Этот переход даёт основания для индукции по n с шагом 6. База индукции:
n = 0 => 0 = 0 = 0 - три пустых множества;
n = 1, 2, 3, 4 - решения нет, проверяется перебором;
n = 5 => 5 = 1 + 4 = 2 + 3;
n = 6 - решается сведением к случаю n = 0;
n = 7 - решения нет, сумма чисел n(n + 1)/2 = 28 не делится на 3;
n = 8 => 4 + 8 = 2 + 3 + 7 = 1 + 5 + 6;
n = 9 => 1 + 5 + 9 = 3 + 4 + 8 = 2 + 6 + 7.
Все решения по модулю шести:
- n = 6k, k ≥ 0 - серия начинается с нуля;
- n = 6k + 1 - решений нет, (6k + 1)(6k + 2)/2 не делится на три;
- n = 6k + 2, k ≥ 1 - серия начинается с восьми;
- n = 6k + 3, k ≥ 1 - серия начинается с девяти;
- n = 6k + 4 - решений нет, (6k + 4)(6k + 5)/2 не делится на три;
- n = 6k + 5, k ≥ 0 - серия начинается с пяти.
Код:
def split(n):
# база индукции
base = (
(0, (set(), set(), set())),
(None, (None, None, None)),
(8, ({4, 8}, {2, 3, 7}, {1, 5, 6})),
(9, ({1, 5, 9}, {3, 4, 8}, {2, 6, 7})),
(None, (None, None, None)),
(5, ({5}, {1, 4}, {2, 3}))
)
start, (s1, s2, s3) = base[n % 6]
if start is None or n < start:
return None
# индукционный шаг
for m in range(start, n, 6):
s1.update((m + 1, m + 6))
s2.update((m + 2, m + 5))
s3.update((m + 3, m + 4))
return s1, s2, s3
def show(sets):
if sets is None:
print('No partition')
else:
print(*('+'.join(map(str, sorted(s))) for s in sets), sep=' = ')
def self_test(m):
for n in range(m):
sets = split(n)
if sets is not None:
assert n % 3 != 1
assert sets[0] & sets[1] == set()
assert sets[0] & sets[2] == set()
assert sets[1] & sets[2] == set()
assert sets[0] | sets[1] | sets[2] == set(range(1, n + 1)), sets
assert all(sum(s) == n * (n + 1) // 2 // 3 for s in sets)
assert sum(map(len, sets)) == n
print(n, ':', end=' ')
show(sets)
# self_test(25)
show(split(int(input())))
Если раскомментировать self_test будет так:
0 : = = 1 : No partition 2 : No partition 3 : No partition 4 : No partition 5 : 5 = 1+4 = 2+3 6 : 1+6 = 2+5 = 3+4 7 : No partition 8 : 4+8 = 2+3+7 = 1+5+6 9 : 1+5+9 = 3+4+8 = 2+6+7 10 : No partition 11 : 5+6+11 = 1+4+7+10 = 2+3+8+9 12 : 1+6+7+12 = 2+5+8+11 = 3+4+9+10 13 : No partition 14 : 4+8+9+14 = 2+3+7+10+13 = 1+5+6+11+12 15 : 1+5+9+10+15 = 3+4+8+11+14 = 2+6+7+12+13 16 : No partition 17 : 5+6+11+12+17 = 1+4+7+10+13+16 = 2+3+8+9+14+15 18 : 1+6+7+12+13+18 = 2+5+8+11+14+17 = 3+4+9+10+15+16 19 : No partition 20 : 4+8+9+14+15+20 = 2+3+7+10+13+16+19 = 1+5+6+11+12+17+18 21 : 1+5+9+10+15+16+21 = 3+4+8+11+14+17+20 = 2+6+7+12+13+18+19 22 : No partition 23 : 5+6+11+12+17+18+23 = 1+4+7+10+13+16+19+22 = 2+3+8+9+14+15+20+21 24 : 1+6+7+12+13+18+19+24 = 2+5+8+11+14+17+20+23 = 3+4+9+10+15+16+21+22
Всё тоже самое можно сделать в константной памяти. Алгоритм прежний, код изменился - вместо множеств генераторы, которые порождают множества:
def part(n):
# база индукции
base = (
(( ), ( ), ( )),
None ,
((1, 5, 6), (2, 3, 7), (4, 8 )),
((1, 5, 9), (2, 6, 7), (3, 4, 8)),
None ,
((1, 4 ), (2, 3 ), (5, ))
)
# индукционный шаг
step = (1, 6), (2, 5), (3, 4)
bases = base[n % 6]
if bases is None:
return None
start = sum(map(len, bases))
assert start % 6 == n % 6
if n < start:
return None
def gen(base, step):
# база индукции
yield from base
for m in range(start, n, 6):
# индукционный шаг
yield from (m + s for s in step)
return tuple(gen(b, s) for b, s in zip(bases, step))
def show(parts):
if parts is None:
print('No partition')
else:
print(*('+'.join(map(str, p)) for p in parts), sep=' = ')
def self_test(m):
for n in range(m):
partition = part(n)
if partition is None:
assert n % 3 == 1 or n in (2, 3)
parts = None
else:
parts = tuple(map(tuple, partition))
assert n % 3 != 1
assert all(len(p) == len(set(p)) for p in parts)
assert set(parts[0]) & set(parts[1]) == set()
assert set(parts[0]) & set(parts[2]) == set()
assert set(parts[1]) & set(parts[2]) == set()
assert set(sum(parts, ())) == set(range(1, n + 1)), parts
assert all(sum(s) == n * (n + 1) // 2 // 3 for s in parts)
assert sum(map(len, parts)) == n
print(n, ':', end=' ')
show(parts)
# self_test(25)
show(part(int(input())))