第 2 题 下⾯C++代码⽤于将输⼊⾦额换成最少币种组合⽅案,其实现算法是( )。
答案:B
解析:贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优(最有利)的选择,以期望最终能够达到全局最优解。在这段代码中,每次循环都选择当前面值最大的硬币进行尽可能多的使用,从而达到最少硬币数量的组合方案。
算法实现分析:
数组coins 存储了面值从大到小的硬币面额{100, 50, 20, 10, 5, 2, 1}。
函数find_coins() 中使用了一个循环遍历所有硬币面额。在每次循环中,计算当前金额money 可以使用的当前面额硬币数量,并更新剩余金额money。
循环结束后,coins_used 数组存储了每种面额硬币的使用数量,以达到组合最少硬币数量的目的。
选择最优:由于每次都选择当前最大面额的硬币,贪心算法能够在保证每次选择最优的情况下,快速得到全局最优解,即使用最少数量的硬币来组合金额。
根据代码实现方式和贪心算法的特性,这段C++代码确实属于贪心算法。