找到最近的三角数的最快方法？

Question

在Python中，我需要一个函数，这个函数接收一个整数，然后返回这个整数减去离它最近的三角形数的绝对值。现在我做法是先生成一个包含所有小于等于这个整数的三角形数的列表。

def closest(myList, myNumber):
    c = min(myList, key=lambda x:abs(x-myNumber))

然后用这个列表来找到离这个整数最近的三角形数。

最终得到的结果列表应该是这样的：

[0, 0, 1 , 0 , 1 ,1 , 0 , 1, 2 , 1, 0 , 1, 2, 2, 1, 0, etc.]

如果你有其他更快的方法来生成相同的结果，也可以试试。

Answer 1

我有一个解决方案，不需要先计算每个三角形数字，但我不确定这是否是最好的方法。

三角形数字的公式是：

    A(n) = n*(n-1)/2       (n is integer)

对于输入的x，它应该位于A(n)和A(n+1)的中间。

    A(n) <= x <= A(n+1)

对于A(n)，我们有：

    n * (n - 1) / 2 <= x
    (n - 1)^2 < n * (n-1) <= 2*x
    n < sqrt(2*x) + 1

对于A(n+1)，我们有：

    (n + 1)^2 > (n + 1) * n >= 2*x
    n > sqrt(2*x) - 1

现在，如果我们有输入数字x，我们可以快速找到n，使得x位于[A(n), A(n+1)]之间。然后我们只需要计算[x与A(n)的距离和x与A(n+1)的距离]，并选择较小的那个作为最终的输出。

Answer 2

这可能不是最好的方法，但应该比你之前的方法快：

def triangle_around(n):
    k = int((2*n)**0.5)
    p = (k**2 + k) / 2 
    while p < n:
        k, p = k + 1, p + k + 1 
    return (p - k, p)

def close_triangle(n):
    t = triangle_around(n)
    return min(t[1] - n, n - t[0])

print close_triangle(8)    # gives 2

Answer 3

在我的解决方案中，我利用了一个事实：设 K = sqrt(2*N)。如果 N 是一个三角数，那么它就是第 K 个三角数。我们知道第 K 个三角数的计算公式是 K*(K+1)/2。

下面是我用 Python 写的解决方案：

from math import sqrt
from math import floor
def close_triangle(n):
m = floor(sqrt(2*n))
t1 = m*(m+1)/2       #next triangular number to n
m = m-1
t2 = m*(m+1)/2       #previous triangular number to n
diff1 = t1-n
diff2 = n - t2
if diff1 < diff2 :
  return t1
else:
  return t2
print "Nearest trianguler number";
print close_triangle(13)

Answer 4

你可以利用 triangle-root 这个特性，快速找到一个数字最近的三角形数，然后再轻松计算出你想要的值。

from math import sqrt

def triangle_number(tnumber):
    '''
    returns the tnumberth triangle number (I.E 3 = 6)
    '''
    return (tnumber*(tnumber+1))/2

def triangle_root(number):
    '''
    returns the triangle root of a number (I.E 6 = 3)
    '''
    return (sqrt(8*number+1)-1)/2

def nearest_root(number):
    '''
    Calculates the nearest whole triangle root to a number (I.E. 5 = 3)
    '''
    t_root = triangle_root(number)
    return round(t_root)

def find_delta(number):
    '''
    Given a number, returns abs(n-nearest_triangle)
    '''
    return abs(number - triangle_number(nearest_root(number)))

当然，你可以把这个过程简化成一个函数，这样会更高效，我只是为了让你更清楚，所以把步骤分开了。

Answer 5

一点数学知识可以让我们找到更分析化的解决方案：

from math import sqrt
def close_triangle2(n):
    m=int(0.5*(-1+sqrt(1+8*n))) #solve it for the explicit formula
    tan0=(m*m+m)/2              #the closest one is either this
    tan1=(m*m+3*m+2)/2          #or this
    if (n-tan0)>(tan1-n):
        return tan1-n
    else:
        return n-tan0

当数字很大的时候，它会比@perreal的循环版本稍微快一点：

In [87]:

%timeit close_triangle(111111111)
100000 loops, best of 3: 5 µs per loop
In [86]:

%timeit close_triangle2(111111111)
100000 loops, best of 3: 4.13 µs per loop

如果你在想：

In [94]:

close_triangle2((30**10 * (30**10+1)) / 2 + 100)
Out[94]:
100L
In [95]:

close_triangle((30**10 * (30**10+1)) / 2 + 100)
Out[95]:
100L

In [102]:

%timeit close_triangle((30**10 * (30**10+1)) / 2 + 100)
10000 loops, best of 3: 17.9 µs per loop
In [103]:

%timeit close_triangle2((30**10 * (30**10+1)) / 2 + 100)
100000 loops, best of 3: 12 µs per loop