我必须找到一定范围(x,y(内满足三角形不等式的解的数量
x和y只是整数,并且(0<x<y<10000(
对于示例区间(2,5(,正确答案为3
示例说明:
有4个组合:
2 3 4
23 5
24 5
3 4 5
三角形不等式对于除一个(2,3,5(之外的所有组合都成立,因此正确答案为3。
我刚刚找到了一种从牛顿符号(下面的代码(计算所有组合的方法
但我不知道如何只找到这些值满足三角形不等式
from math import factorial
### n = (y-x)+1
### n! / ((n-k)! * k!)
# math.factorial(x) = x!
x = int(input("Enter x: "))
y = int(input("Enter y: "))
if(y-x+1 < 3 ):
result = 0
else:
k = 3
n = y-x+1
number_of_combinations = int(factorial(n) / (factorial(n-k)*factorial(k)))
print(f"Number of combinations:{number_of_combinations}")
提前感谢您对的帮助
您可以使用itertools.combinations
创建所有3个组合,并简单地对它们进行计数迭代。
来自文档:
组合元组按照字典顺序发出到输入可迭代的顺序。因此,如果输入可迭代为排序后,组合元组将按排序顺序生成。
因此,如果您有一个区间,这意味着它是排序的,所以您可以将每个元组中的前两个元素与第三个元素进行比较。
from itertools import combinations
lst = list(range(2,6))
count = 0
for x,y,z in combinations(lst, 3):
count += x+y > z
与一行代码相同:
count = sum(x+y > z for x,y,z in combinations(lst, 3))
输出:
3
如果你需要满足它的元组,那么:
out = [(x,y,z) for x,y,z in combinations(lst, 3) if x+y > z]
输出:
[(2, 3, 4), (2, 4, 5), (3, 4, 5)]
试试这个:
interval = [
int(input('Enter first endpoint: ')),
int(input('Enter second endpoint: ')),
]
for z in range(interval[0] + 2, interval[1] + 1):
for y in range(interval[0] + 1, z):
for x in range(z - y + 1, y):
print(x, y, z)