力扣(LeetCode)之排列硬币

题目：

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。
给你一个数字 n ，计算并返回可形成 完整阶梯行 的总行数。

示例:

输入：n = 5
输出：2
解释：因为第三行不完整，所以返回 2 。

输入：n = 8
输出：3
解释：因为第四行不完整，所以返回 3 

方法一：暴力算法

我们通过迭代求解出从从1-n的所有硬币的数量和总和。

# 暴力算法
def fun1(n):
    for i in range(1, n+1):
        n = n-i
        if n <= i: return i 

方法二：二分查找

我们可以把上面的暴力算法进行优化，我们可以将题目看成在1-n中寻找一个值，满足前x项的和等于获刚好小于n。其具体代码如下：

# 二分查找
def fun2(n):
    start = 0 
    end = n 
    while start <= end:
        mid = int(start + (end-start)/2)
        cost = int(((mid+1)*mid)/2)
        if cost == n: 
            return mid 
        elif cost > n:
            end = mid - 1
        else:
            start = mid + 1 
    return end

方法三：牛顿迭代

我们把前x行的等差数列的求和公式：(x^2 + x)/2 = n。x为项数也等于行数，满足两个因数相等，就能求出x的值。其具体代码如下：

# 牛顿迭代
def fun3(n):
    if n == 0 : return 0
    return int(recurse(n, n)) # 取整

def recurse(x, n):
    # 等差数列的求和公式：(x^2 + x)/2 = n。x为项数也等于行数
    # 我们将该公式进行转变: x^2 = 2n -x, 既可以转变为我们求2n -x的平方根
    # 于是可以使用牛顿迭代吗进行求解x
    res =  (x + (2*n - x)/ x)/2 # 牛顿迭代法中的两个因数
    if res == x :
        return x # 不断求平均最后由于精度问题，两个因数一定会相等
    else:
        return recurse(res, n)