ACM编程竞赛入门：凑钱算法与阶乘问题解析

"acm编程比赛入门题目集，包含算法学习和编程能力提升的练习" 在ACM编程比赛中，参赛者通常需要解决各种算法问题，以此提高编程技能和逻辑思维能力。这里提到的两个题目是很好的入门示例，它们分别涉及到了动态规划和数论的知识点。 首先，"最少钱币数"问题是一个典型的动态规划问题。动态规划是一种通过构建子问题的最优解来求解原问题的方法。在这个问题中，我们需要找到用最少数量的钱币来凑成给定的金额。关键在于构建状态转移方程，通常是dp[i]表示用现有面值的钱币凑成金额i所需的最少钱币数。初始状态dp[0]=0，因为凑成0元不需要任何钱币。对于每个面值k，我们可以更新dp数组，dp[j] = min(dp[j], dp[j-k]+1)，其中j >= k。这样，我们可以通过遍历所有可能的金额和面值，找出凑成目标金额的最少钱币数。对于输入的样例，当目标金额为15时，我们可以发现使用2个面值为2的钱币是最优解。 第二个问题是"Feli的生日礼物"，它涉及到计算阶乘的最后一位非零数字。这是一个数论问题，而不是简单的数学运算，因为n!的值可能会非常大，超出计算机常规数据类型的范围。要找出n!的最后一位非零数字，我们可以利用阶乘性质和模运算。首先，我们知道任何大于10的数与10取模后，结果要么是0要么是1，这决定了最后一位数字。然后，我们可以考虑n!中的质因数2和5的数量，因为2的倍数总是比5的倍数多，所以决定最后非零数字的是5的倍数。计算n/5, n/25, n/125等，将这些商的和作为5的倍数的数量，从而确定n!中5的因子的个数。由于2的因子总是更多，我们只需关注5的因子，计算n!对10的幂次取模的结果即可找到最后一位非零数字。对于较大的n值，我们可以使用高精度计算避免溢出。 这两个问题展示了ACM竞赛中常见的算法类型，通过解决这些问题，参赛者可以逐步提升自己的算法设计和实现能力，同时对动态规划和数论有更深入的理解。在准备ACM比赛的过程中，不断实践和总结这些基础知识是非常重要的。