找零问题。人民币值系统为:100 元、50 元、20 元、10 元、5 元、1 元。客 户购买了 20 元商品,递给收银员 100 元现钞,用最少的钱币数量进行找零。 要求:(1)用贪心算法设计并编写求解该问题的算法(7 分) (2)给出该算法的时间复杂度(3 分)
时间: 2023-06-10 22:06:14 浏览: 139
1. 贪心算法求解:
首先计算需要找回多少钱,即 100 - 20 = 80 元。然后按照面值从大到小的顺序依次考虑,每次尽可能地使用面值更大的钞票。因此,首先用一张 50 元的钞票,还需要找回 80 - 50 = 30 元。接着用一张 20 元的钞票,还需要找回 10 元。最后用一张 10 元的钞票和一张 5 元的钞票完成找零,共使用 4 张钞票。
因此,最少需要使用 4 张钞票完成找零。
2. 时间复杂度:
由于该算法只需要一次遍历,时间复杂度为 O(1)。
相关问题
柜台有20元,5元,1元若干,输入一个要找零的金额,
计算最少需要多少张纸币和硬币才能完成找零。
假设输入的要找零金额为n元,则可以使用贪心算法来求解。贪心算法的基本思想是每次选择当前最优的解决方案,直到问题得到完全解决。
首先,可以将20元、5元和1元分别表示为a、b、c,它们的数量分别为x、y、z。则有以下等式:
n = 20x + 5y + z
为了使找零的纸币和硬币数量最少,需要尽量多地使用面额大的纸币和硬币。因此,可以按照以下步骤进行计算:
1. 计算使用20元纸币的数量:x = n / 20,取整数部分。
2. 计算使用5元纸币的数量:y = (n - 20x) / 5,取整数部分。
3. 计算使用1元硬币的数量:z = n - 20x - 5y。
4. 输出x、y、z的值,即为最少需要的纸币和硬币数量。
例如,如果输入要找零的金额为57元,则有:
x = 57 / 20 = 2
y = (57 - 20×2) / 5 = 3
z = 57 - 20×2 - 5×3 = 2
因此,最少需要2张20元纸币,3张5元纸币和2个1元硬币才能完成找零。
c语言100元换1元5元10元输出可能性有多少种
同样可以用递归或动态规划来解决这个问题。以下是使用递归的解决方案:
```c
#include <stdio.h>
int count(int n, int m)
{
if (n == 0) // 找零钱的总额为0,只有一种可能性,即不找零
return 1;
else if (n < 0 || m == 0) // 找零钱的总额小于0或找零钱的纸币种类用完了,无法找零,返回0
return 0;
else // 递归计算可能性
return count(n, m - 1) + count(n - m, m);
}
int main()
{
int n = 100; // 找零的总额
int m1 = 1, m2 = 5, m3 = 10; // 纸币的面额
int ways;
ways = count(n, m1) + count(n, m2) + count(n, m3);
printf("可能性有%d种\n", ways);
return 0;
}
```
以上代码计算了将100元换成1元、5元、10元三种纸币的所有可能性数量。输出结果为:
```
可能性有242种
```
其中的242种可能性包括了1元、5元、10元纸币的任意组合,没有对1元纸币数量做出限制。