У нас есть количество бит. Чтобы понять, сколько вариантов чисел мы можем записать двоичным числом длинной в это количество бит, нужно количество вариантов для одной цифры возвести в степень количества бит: 2^10 = 1024. - ответ
P.S. На самом деле, это максимальное количество для данного количества бит. Но это же не значит, что мы будет использовать все цифры? Например, если у тебя в корзине лежит 1023 шарика, то меньше, чем 10 битами ты зашифровать один шарик не сможешь физически. А вот если из 512, то сможешь - девятью. (2^9 = 512) Поэтому правильней было бы задавать подобные ответы диапазонами. Например, для данного [513, 1024]. Но об этом редко кто задумывается.
Программа на питоне, перебирающая варианты и возвращающая все ответы минимальной длины: def number_of_adds(n): def next_seq(seq): new_elems = set() for i in range(len(seq)): for j in range(i, len(seq)): new_elem = seq[i] + seq[j] if new_elem > seq[-1] and new_elem not in new_elems: new_elems.add(new_elem) yield seq + [new_elem]
current_stage = None next_stage = [[1]] answer = [] while len(answer) == 0: current_stage = next_stage next_stage = [] for chain in current_stage: next_stage.extend(next_seq(chain)) answer = [seq[1:] for seq in next_stage if seq[-1] == n] return answer
def print_solution(n): answer = number_of_adds(n) print("Для {} есть {} решений(-я, -е):".format(n, len(answer))) for i in range(len(answer)): print("{}. {}".format(i + 1, " ".join(map(str, answer[i] print()
print_solution(27)
Запустив, находим, что необходимо 6 сложений. За 6 сложений можно получить 27X, например, так: X + X = 2X 2X + X = 3X 3X + 3X = 6X 6X + 6X = 12X 12X + 12X = 24X 24X + 3X = 27X
P.S. На самом деле, это максимальное количество для данного количества бит. Но это же не значит, что мы будет использовать все цифры? Например, если у тебя в корзине лежит 1023 шарика, то меньше, чем 10 битами ты зашифровать один шарик не сможешь физически. А вот если из 512, то сможешь - девятью. (2^9 = 512) Поэтому правильней было бы задавать подобные ответы диапазонами. Например, для данного [513, 1024]. Но об этом редко кто задумывается.
def number_of_adds(n):
def next_seq(seq):
new_elems = set()
for i in range(len(seq)):
for j in range(i, len(seq)):
new_elem = seq[i] + seq[j]
if new_elem > seq[-1] and new_elem not in new_elems:
new_elems.add(new_elem)
yield seq + [new_elem]
current_stage = None
next_stage = [[1]]
answer = []
while len(answer) == 0:
current_stage = next_stage
next_stage = []
for chain in current_stage:
next_stage.extend(next_seq(chain))
answer = [seq[1:] for seq in next_stage if seq[-1] == n]
return answer
def print_solution(n):
answer = number_of_adds(n)
print("Для {} есть {} решений(-я, -е):".format(n, len(answer)))
for i in range(len(answer)):
print("{}. {}".format(i + 1, " ".join(map(str, answer[i]
print()
print_solution(27)
Запустив, находим, что необходимо 6 сложений. За 6 сложений можно получить 27X, например, так:
X + X = 2X
2X + X = 3X
3X + 3X = 6X
6X + 6X = 12X
12X + 12X = 24X
24X + 3X = 27X