程序设计比赛入门：最少钱币数与Feli的生日礼物

"acm入门题集" 这篇摘要涵盖了两道ACM程序设计竞赛中的典型问题。首先，我们来看第一道题目——"最少钱币数"。这是一道经典的动态规划问题，通常在ACM竞赛中出现，旨在训练参赛者的算法思维和优化能力。 问题的核心是给定一系列不同面值的钱币，求解凑成特定金额所需的最少钱币数量。题目明确指出，每种钱币的供应量是无限的，这意味着我们可以自由地使用任意数量的某种面值的钱币。例如，给定面值为2、5、10、20、50和100的钱币，目标金额是15元，最优解是使用两个2元硬币，因为这是最少的钱币组合。 为了解决这个问题，我们可以采用动态规划的方法，定义一个数组dp，其中dp[i]表示凑成i元需要的最少钱币数。初始化dp[0] = 0，表示凑成0元不需要任何钱币。然后，对于每一个面值ki，从ki到M遍历，更新dp[j]的值，如果dp[j - ki]存在且小于dp[j]，则更新dp[j]为dp[j - ki] + 1。这样，dp[M]就会得到凑成M元的最少钱币数。 第二个问题是"Feli的生日礼物"，这涉及到阶乘的计算。题目要求计算一个非常大的数n的阶乘n!的最后一位非零数字。由于实际计算n!会超出计算机的整型范围，所以不能直接计算。然而，我们可以利用阶乘尾数的性质来解决问题。对于n!的最后一位非零数字，我们可以通过分析2的倍数、5的倍数对阶乘尾数的影响来找到答案。2的倍数会引入更多的0，而5的倍数会使尾部的0增加。因此，最后一位非零数字取决于n中2的因子和5的因子哪个更多。由于2的因子总是比5的因子多，我们只需要计算n中5的因子数量即可。 为了解决这个问题，我们可以对n进行分解，计算2的幂次和5的幂次，只关注5的幂次，因为这是影响阶乘尾数的关键。对于较大的n，这种方法能够高效地找出最后一位非零数字，而不必进行完整的阶乘计算。 这两道题目展示了ACM竞赛中常见的问题类型，包括动态规划和高精度计算，是初学者提升编程和算法技能的良好练习。通过解决这些问题，参赛者可以锻炼其逻辑思维，优化代码能力和处理大数据的能力。