提高找出用给定的棍子可以制作多少个可能的三角形的性能

Question

我正在进行一项评估，要求将给定的“n”作为输入，这是一根棍子的长度；你能拼出多少个三角形？ (3 < n < 1,000,000)

例如：

input: N=8
output: 1
explanation:
(3,3,2)

input: N=12 
output: 3
explanation:
(4,4,4) (4,5,3) (5,5,2)

现在我写的代码返回了 33% 的准确率，因为网络评估抛出了时间限制错误。

ans = 0
n = int(input())
for a in range(1, n + 1):
   for b in range(a, n - a + 1):
    c = n - a - b
    if a + b > c >= b:
        ans += 1
print(ans)

代码 b:

ans = 0
n = int(input())
for i in range(1,n):
 for j in range(i,n):
  for c in range(j,n):
     if(i+j+c==n and i+j>c):
           ans+=1
print(ans)

如何让它更快？

Answer 1

https://mathworld.wolfram.com/AlcuinsSequence.html

import math
n = int(input())
print(round(n ** 2 / 48)) if n % 2 == 0 else print(round((n + 3)** 2 / 48))

Answer 2

这是我想出的一个直观的 O(n) 算法：

def main():
  n = int(input())
  if n < 3:
    print(0)
    return
  ans = n % 2
  for a in range(2, n//2+1):
    diff = n - a
    if diff // 2 < a:
      break
    if diff % 2 == 0:
      b = diff // 2
    else:
      b = diff // 2 + 1
    b = max(b - a // 2, a)
    c = n - b - a
    if abs(b - c) >= a:
      b += 1
      c -= 1
    ans += abs(b-c)//2 + 1
  print(ans)

main()

我找到 b 和 c 的上限和下限并计算该范围内的值。

Answer 3

我想到了一个完全不同的方法：

我们取最小的边称它为a。永远不能超过n/3，否则另一边就是最小的
我们试着找出下一个最小的边(b)：
1. 我们看看减少 a 后还剩下什么。
2. 我们将其除以 2 以找到我们将从中开始前进的中间点
3. 我们将看看在长度之间的差异为 a（或与中间的差异为 a/2）之前我们能走多远，因为这是最小的 b 边可能并满足 a+b>c 的长度。基本上，第二小的边比中间小a/2。
4. 最小的边是我们计算的最大值或者a，以防b==a。 b 永远不能低于 a，因为它违反了我们的第一个规则，即 a 是最小的。
我们从中间和最小的一边算出差异。这就是我们对其他 2 个方面有多少种可能的解决方案。
将每个 a 的所有内容加在一起，这就是我们的解决方案。

floor、ceil 和 % 是针对 a 为奇数、中间为 .5 或 +1 的修复如果 b+c 是偶数，那么可能会导致 b==c。

代码：

import math
n = int(input("Enter a number: "))

total = 0

# a is the shortest side
for a in range(1, (n//3)+1):
    length_left = n-a
    middle_number = length_left/2
    
    # Shortest potential side b where the distance between b and c is smaller than a (c-b < a)
    b = middle_number-(math.ceil(a/2)-1)-((length_left % 2)/2)

    # We calculate how far it is from the middle
    max_distance_from_middle = middle_number - max(b, a)

    # Add another 1 if the length is even, in case b==c
    adding = math.floor(max_distance_from_middle) + (1 if length_left % 2 == 0 else 0)
    total += adding

print(total)

或者在丑陋的一行中：

n = int(input("Enter a number: "))
print(sum(math.floor((n-a)/2 - max((n-a)/2 - math.ceil(a/2) + 1 - (((n-a) % 2)/2), a)) + 1 - ((n-a) % 2) for a in range(1, (n//3)+1)))

Answer 4

Alcuin 序列展开：O(1)

Alcuin 序列 [参见：https://en.wikipedia.org/wiki/Alcuin%27s_sequence] 是下面多项式的级数展开，其中 n个系数对应第n个答案，即周长为n.

的唯一整数三角形的最大数量

这个算法的实现只是一个公式。整数序列在线百科全书 (OEIS) 提供了许多实现此目的的公式，其中最简单的是：

round(n^2 / 48)（偶数）
round((n+3)^2 / 48)（奇数）

[参见：https://oeis.org/A005044]

这显然具有恒定的时间复杂度，因为所需的唯一函数是模 2、整数平方和舍入，每个都是恒定时间（在某些定义下）。

实施

展开：

def triangles(n):
    if n % 2 == 0:
        return round(n ** 2 / 48)
    else:
        return round((n + 3) ** 2 / 48)

1-班轮：

def triangles(n): return round(n ** 2 / 48) if n%2==0 else round((n + 3) ** 2 / 48)

甚至：

def triangles(n): return round((n + 3 * n%2) ** 2 / 48)

额外

不需要 import。

正如 OP 所质疑的，为什么我们要除以 48？虽然我不能明确回答这个问题，但让我们得到一个直观的理解。我们正在对数字进行平方，因此它显然会大大扩展。当我们达到 5 时，将得到 64 (8^2)。因此，必须有一个常数（尽管是倒数）来限制抛物线的增长，因此 / 48.

当我们绘制 OP 的方法时，它给出了交替抛物线。这就解释了为什么 +3 和 +0 来来回回。

提高找出用给定的棍子可以制作多少个可能的三角形的性能

Improving performance of finding out how many possible triangles can be made with a given stick

python

time-complexity

Alcuin 序列展开：O(1)

实施

额外