Все возможные способы сложения числа в последовательности так, чтобы оно стало заданным числом
Мне дали диапазон n и число k. Подсчитайте возможные способы, чтобы два (не одинаковых) числа в этом диапазоне в сумме составили число k. И можно ли это сделать без вложенных циклов? Вот мой подход, единственное, что я использую вложенный цикл, который требует времени и не удобен для компьютера. Противоположные пары, такие как (A, B) и (B, A), по-прежнему считаются за 1.
n, k = int(input()), int(input())
cnt = 0
for i in range(1, n+1):
for s in range(1, n+1):
if i == 1 and s == 1 or i == n+1 and s==n+1:
pass
else:
if i+s==k:
cnt += 1
print(int(cnt/2))
пример входных данных (первая строка — n, вторая — k)
8
5
объяснение(1, 4 и 2, 3), поэтому я должен напечатать 2
Ответы 4
Если я вас правильно понял, это будет всего один цикл while, считая до k:
counter = 0
while counter<min(n,k)/2:
if counter+(k-counter) == k: # This is always true actually...
print(counter,k-counter)
counter+=1
- Начиная с 0 до k, эти пары будут счетчиком, а k - счетчиком (дополнение к k, поэтому результат вычитания счетчика из k)
- Мы должны уметь считать до меньшего из двух
nиk, потому что числа большеkне складываются вk - На самом деле мы должны сосчитать до половины, потому что после этого мы получим симметричные результаты.
Итак, учитывая, что вы не хотите печатать каждую пару, на самом деле:
count = int(min(n,k)//2)
Проблема комбинаторики. Следующий код использует встроенную библиотеку Python для генерации всех возможных комбинаций.
from itertools import combinations
n = 10
k = 5
n_range = [i for i in range(1, n+1)]
result = []
for i in n_range:
n_comb = combinations(n_range, i)
for comb in n_comb:
if sum(comb) == k:
result.append(comb)
print(result)
Для этого вам нужен только один цикл:
n = int(input('N: ')) # range 1 to n
k = int(input('K: '))
r = set(range(1, n+1))
c = 0
while r:
if k - r.pop() in r:
c += 1
print(c)
зачем вы итерируете и проверяете числовые комбинации, когда вы можете математически вывести количество допустимых пар, используя сами n и k?
в зависимости от того, больше ли n или k, количество пар можно рассчитать напрямую
У каждого числа i в диапазоне n есть совпадающая пара k-i и в зависимости от того, больше ли n или k, нам нужно проверить, находятся ли оба k-i и i в диапазоне n и не равны.
для случая n>=k допустимый диапазон от 1 до k-1 а для другого случая допустимый диапазон от k-n до n и количество диапазона от a до b равно b-a+1
поскольку в обоих случаях пары симметричны, количество диапазонов должно быть уменьшено вдвое.
поэтому весь код становится
n= int(input())
k=int(input())
if n>=k:print(int((k-1)/2))
if n<k:print(int((2*n-(k-1))/2))
Что решить некоторые дела быстрее! Ну, я редактирую это, чтобы код работал лучше.
если 2*n < k+1: напечатать(0) если 2*n == k+1: напечатать(1)
Правило заключалось в том, чтобы не использовать вложенные циклы