当前位置: 面试刷题>> 硬币摆放 (经典算法题500道)


题目描述补充

题目:硬币摆放

给定一个整数 n,表示有 n 枚相同的硬币,要求将这些硬币摆放成直角三角形的形状,其中每一层比上一层多一个硬币,直到最后一层。请计算并返回能够摆放成这样的直角三角形所需的最少层数,或者说明给定的硬币数量 n 无法构成这样的直角三角形。

解题思路

这个问题可以通过计算等差数列的和来解决。直角三角形的硬币摆放方式可以看作是一个等差数列,其中首项为1,公差为1,末项(即每层的硬币数)未知,但可以通过总硬币数 n 来求解。

等差数列的前 k 项和公式为: $$ S_k = \frac{k(a_1 + a_k)}{2} $$ 其中,$ S_k $ 是前 k 项和,$ a_1 $ 是首项,$ a_k $ 是第 k 项。

由于这是一个等差为1的数列,且首项为1,我们可以设第 k 项(即最后一层的硬币数)为 k(因为每一层比上一层多一个硬币)。因此,我们可以将公式改写为: $$ S_k = \frac{k(1 + k)}{2} $$

我们需要找到一个 k,使得 $ S_k \geq n $ 且尽可能接近 n(即不超过 n 的最小整数解)。

示例代码

PHP

function minLayersForCoins($n) {
    $k = 0;
    while (true) {
        $sum = ($k * ($k + 1)) / 2;
        if ($sum >= $n) {
            return $k;
        }
        $k++;
    }
}

echo minLayersForCoins(10);  // 输出 4,因为 1+2+3+4=10

Python

def min_layers_for_coins(n):
    k = 0
    while True:
        sum_k = (k * (k + 1)) // 2
        if sum_k >= n:
            return k
        k += 1

print(min_layers_for_coins(10))  # 输出 4

JavaScript

function minLayersForCoins(n) {
    let k = 0;
    while (true) {
        const sumK = (k * (k + 1)) / 2;
        if (sumK >= n) {
            return k;
        }
        k++;
    }
}

console.log(minLayersForCoins(10));  // 输出 4

码小课分享

码小课网站上有更多关于算法和数据结构的相关内容分享,涵盖了从基础到进阶的各类编程知识和技巧,帮助大家更好地学习和掌握编程技能。欢迎访问码小课网站,与更多编程爱好者一起学习和交流。

推荐面试题