程序设计比赛试题：凑钱问题与阶乘求解

"这是一份ACM入门题集，包含了两个编程题目，旨在帮助学习者掌握ACM竞赛中的算法和编程技巧。" 【题目一：最少钱币数】 这是一个经典的组合优化问题，通常称为“找零问题”或“硬币找零问题”。问题的核心是求解如何使用最少数量的钱币来组成特定的金额。在这个问题中，给定了一组不同面值的钱币，并要求找出凑成指定金额所需的最小钱币数。题目中提供了几个限制条件： 1. 钱币面值互不相同。 2. 待凑的钱数M范围是1到2000。 3. 币种个数K范围是1到10。 4. 每种钱币面值Ki的范围是1到1000。 5. 输入M=0时结束。 解决此类问题的一种常见方法是动态规划。首先，可以创建一个二维数组dp，其中dp[i][j]表示使用前i种钱币凑成金额j所需的最少钱币数。初始状态可以设置为dp[0][0]=0，表示不使用任何钱币时，凑成0元无需钱币。然后，对于每种面值Ki，遍历所有可能的金额j，更新dp[i][j]的值。如果j>=Ki，那么dp[i][j]的值可以是dp[i-1][j]（不使用当前面值的钱币）或者dp[i-1][j-Ki]+1（使用一个Ki面值的钱币）的较小者。最后，dp[K][M]即为所求的最少钱币数。 【题目二：Feli的生日礼物】 该题属于数论问题，具体来说是关于阶乘尾部非零数字的问题。题目要求计算n!（n的阶乘）的最后一位非零数字。由于n的阶乘随着n的增长会变得非常大，直接计算n!并寻找非零位是不可行的。因此，需要使用数学方法来简化计算。 解决这个问题的一种策略是利用阶乘末尾零的性质。n!中0的个数由n内2和5的因子个数决定，因为10=2×5。2的因子个数总是大于或等于5的因子个数，所以只需关注5的因子个数。可以计算n中能被5整除的数、25整除的数、125整除的数等，将这些数的5的因子个数累加起来，即可得到n!中0的个数。n!的最后一位非零数字就是n!除以10的幂次后得到的余数。 在实际编程实现时，可以编写一个函数来计算阶乘，并通过上述方法找到最后一位非零数字。对于大数计算，可以使用大整数库或自定义的模拟大数运算。 这两个题目都是ACM竞赛中常见的问题类型，练习它们有助于提升编程能力和算法理解，特别是动态规划和数论应用。