Блог

Сколькими способами положительное целое n может быть представлено в виде суммы трех разных положительных целых чисел. Два метода отличаются, если один содержит число, которого нет в другом.

Мне удалось получить следующий скрипт для подсчета количества способов записи n в виде суммы трех чисел, но при этом не учитывается другое условие в consiredation.

 def nways(n):  
  
    if (n <= 2):  
        return False
    else:           
        ways = (n - 1) * (n - 2) / 2
          
    return ways
  

Например, если n = 8, мне нужно было бы вернуть 2, так как 1 2 5 = 8 и 1 3 4 = 8, но текущая функция возвращает 21…

Каким был бы правильный алгоритм и математика, стоящие за этим?

Решение

 def nways(n):
    nways = 0
    for i in range(1, n-2):
        min_j, max_j = i 1, (n-i-1)//2
        nways  = (max_j - min_j   1) if max_j >= min_j else 0
    return nways
  

Этот алгоритм потребляет O(N) время и O(1) пространство.

Объяснение

Давайте обозначим три положительных числа как i , j , k .

И поскольку все они разные, эти три числа должны быть больше или меньше друг друга. Мы предполагаем, что наименьшее число равно i , среднее — j , наибольшее — k . Итак, тогда отношение было бы i < j < k .

Возьмем n = 18 , например

• мы начинаем с i = 1 , затем j k должно быть 17 .
  • Так (j,k) может быть от (2,12) , (3,14) , … до (8,9) .
  • Обратите внимание, (j,k) не может быть (9,8) , (10,7) потому что j<k
  • Следовательно, min_j было бы i 1 (в данном случае 2 ), max_j было бы (n-i-1)//2 (в данном случае 8 )
  • Количество (j, k) комбинаций — это, max_j - min_j 1 что в данном случае является 7 парами
• мы продолжаем с i = 2 , тогда j k должно быть 16 .
  • min_j было бы i 1 (в данном случае 3 ), max_j было бы (n-i-1)//2 (в данном случае 7 )
  • Количество (j, k) комбинаций — это, max_j - min_j 1 что в данном случае является 5 парами

Мы пробуем все возможные значения i , затем складываем все комбинации (j, k) pair, после чего получаем ответ.

Вы могли бы использовать грубую силу с некоторыми другими работами:

• проверьте, отличаются ли три термина
• хранить набор уникальных терминов
• длина этого набора является вашим результатом

 def ways(n):
  tuple_sum_set = set()

  for i in range(1, n 1):
    for j in range(1, n 1):
      for k in range(1, n 1):
        if i   j   k == n and len(set([i, j, k])) == 3:
          tuple_sum_set.add(tuple(sorted([i,j,k])))

  print(tuple_sum_set)
  return len(tuple_sum_set)

print(ways(8))
  

Демонстрация:https://repl.it/repls/ChocolateHelplessLivecd

Вы можете внести некоторые довольно значительные оптимизации в уже отличный ответ @ hgb123, чтобы по-прежнему использовать грубую силу, но будьте немного умнее в этом:

 def ways(n):
  tuple_sum_set = set()

  for i in range(1, n-2):
    for j in range(i 1, n-2):
      for k in range(j 1, n-2):
        if i   j   k == n:
          tuple_sum_set.add((i,j,k))

  print(tuple_sum_set)
  return len(tuple_sum_set)
  

(Если вы проголосуете за этот ответ, пожалуйста, проголосуйте за @hgb123, так как это производное от его ответа)

Совсем другим подходом было бы использование решателя ограничений. Вот пример:

 import constraint as con

n = 8

p = con.Problem()
p.addVariables(['x','y','z'],range(1,n-2))
p.addConstraint(con.ExactSumConstraint(n))
p.addConstraint(lambda a, b, c : a < b < c, ("x", "y", "z"))
sols = p.getSolutions()

print(len(sols))
sols
  

Это дает:

 2
[{'x': 1, 'y': 3, 'z': 4}, {'x': 1, 'y': 2, 'z': 5}]
  

Я не знаю простой формулы, которая предсказывает количество решений.