单选题 适中
#21107

下面C++代码用于将输入金额换成最少币种组合方案,其实现算法是( )。 # include <iostream> using namespace std ; #…

下面C++代码用于将输入金额换成最少币种组合方案,其实现算法是( )。

#include <iostream>
using namespace std;

#define N_COINS 7
int coins[N_COINS] = {100, 50, 20, 10, 5, 2, 1}; //货币面值,单位相同
int coins_used[N_COINS];

void find_coins(int money) {
	for (int i = 0; i < N_COINS; i++) {
		coins_used[i] = money / coins[i];
		money = money % coins[i];
	}
	return;
}
int main() {
	int money;
	cin >> money; //输入要换算的金额
	
	find_coins(money);
	for (int i = 0; i < N_COINS; i++)
		cout << coins_used[i] << endl;
		
	return 0;
}
未登录也能判分,登录后才会记录
答案与解析
正确答案:B
解析

贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优(最有利)的选择,以期望最终能够达到全局最优解。在这段代码中,每次循环都选择当前面值最大的硬币进行尽可能多的使用,从而达到最少硬币数量的组合方案。

算法实现分析:

数组coins 存储了面值从大到小的硬币面额{100, 50, 20, 10, 5, 2, 1}。

函数find_coins() 中使用了一个循环遍历所有硬币面额。在每次循环中,计算当前金额money 可以使用的当前面额硬币数量,并更新剩余金额money。

循环结束后,coins_used 数组存储了每种面额硬币的使用数量,以达到组合最少硬币数量的目的。

选择最优:由于每次都选择当前最大面额的硬币,贪心算法能够在保证每次选择最优的情况下,快速得到全局最优解,即使用最少数量的硬币来组合金额。

根据代码实现方式和贪心算法的特性,这段C++代码确实属于贪心算法。