python - Codility最后界元素

Question

如何解决以下递归关系

为非负整数定义函数F（K）如下：


当K = 0时F（K）= 0
当K> 0时F（K）= F（K-1）+ K


编写一个函数：

def solution(N)

给定一个非负整数N，则返回最大非负整数L，使得F（L）≤N。

例如，给定N = 17，该函数应返回5，因为对于所有大于5的整数K，F（5）= 15且F（K）> 17。

针对以下假设编写高效的程序：


N是在[0..1,000,000,000]范围内的整数。

Answer 1

您在F（K）中给出的级数只是从0 ... K开始的所有正数之和。这是具有直接公式1/2 * K * (K+1)的高斯级数。因此，您基本上想找到1/2 * K (K+1) = N的K并将其四舍五入。重写给出：K^2 + K - 2N = 0使用二次公式给出正数：K = (-1 + sqrt(1+8*N))/2.因此在python中：

from math import *

def solution(N):
   K = (-1+sqrt(1+8*N))/2
   return int(K) #int truncates downwards

由于此算法使用直接公式，因此速度非常快