c语言 ytuoj 找零钱 贪心算法
时间: 2024-05-31 15:06:07 浏览: 19
C语言中使用贪心算法求解找零钱问题,具体流程如下:
1. 定义一个数组存储不同面值的硬币,假设硬币面值分别为1元、2元、5元、10元、20元、50元、100元。
2. 输入需要找零的金额。
3. 从大到小遍历硬币面值数组,每次尽可能多地使用当前面值的硬币,直到找零金额为0。
4. 输出所用硬币的数量。
示例代码如下:
```c
#include <stdio.h>
int main()
{
int coins[] = {100, 50, 20, 10, 5, 2, 1}; // 硬币面值
int numCoins = sizeof(coins) / sizeof(coins); // 硬币种类数量
int amount, i, count;
printf("请输入需要找零的金额:");
scanf("%d", &amount);
for(i = 0; i < numCoins; i++)
{
count = amount / coins[i];
amount -= count * coins[i];
if(count > 0)
printf("%d元硬币%d个\n", coins[i], count);
if(amount == 0)
break;
}
return 0;
}
```
相关问题
找零钱贪心算法C语言代码
以下是C语言实现找零钱问题的贪心算法代码:
```c
#include <stdio.h>
void findMin(int coins[], int n, int amount)
{
int coinCount[n];
for (int i = 0; i < n; i++) {
coinCount[i] = 0;
}
forint i = n - 1; i >= 0; i--) {
while (amount >= coins[i]) {
amount -= coins[i];
coinCount[i]++;
}
}
printf("Coins needed:\n");
for (int i = n - 1; i >= 0; i--) {
if (coinCount[i] != 0) {
printf("%d coin(s) of %d\n", coinCount[i], coins[i]);
}
}
}
int main()
{
int coins[] = { 10,5, 2 };
int n = sizeof(coins) / sizeof(coins[0]);
int amount = 27;
findMin(coins, n, amount);
return 0;
}
```
c语言 贪心算法 找零钱
以下是使用贪心算法找零钱的C语言代码示例:
```c
#include <stdio.h>
void findChange(int money, int a, int b, int c) {
int sum, i = 0, m = 0, n = 0;
while (1) {
sum = a * n + b * m + c * i; // 总钱数求解
if (sum == money) { // 满足条件结束循环
printf("a:%d, b:%d, c:%d\n", n, m, i); // 打印输出i,m,n的数值
break;
}
if (sum > money) { // 总钱数超过money,需要回退
if (m > 0) { // 尝试减少b的个数
m--;
n = (money - c * i - b * m) / a;
} else if (i > 0) { // 尝试减少c的个数
i--;
m = (money - c * i) / b;
n = (money - c * i - b * m) / a;
} else { // 无法回退,退出循环
break;
}
} else { // 总钱数小于money,增加a的个数
n++;
}
}
}
int main() {
int money = 15, a = 5, b = 2, c = 1;
findChange(money, a, b, c);
return 0;
}
```
该算法的思路是从大面值开始,尽可能多地使用大面值,直到总钱数超过money,然后回退到上一个状态,尝试减少大面值的个数,增加小面值的个数,直到找到最优解或者无法回退为止。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)