假设1元、2元、5元、10元、20元、50元、 100元 的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱 来支付K元,至少要用多少张纸币?
时间: 2024-01-18 17:05:03 浏览: 27
这是一个很经典的贪心算法问题。我们可以从面额最大的纸币开始,尽可能多地使用该面额的纸币,直到不能再使用为止,然后再用面额次大的纸币,直到支付完K元为止。
具体做法如下:
1. 用c6张100元的纸币,支付K元中的整百部分,剩余金额记为K1。
2. 用c5张50元的纸币,支付K1元中的整50部分,剩余金额记为K2。
3. 用c4张20元的纸币,支付K2元中的整20部分,剩余金额记为K3。
4. 用c3张10元的纸币,支付K3元中的整10部分,剩余金额记为K4。
5. 用c2张5元的纸币,支付K4元中的整5部分,剩余金额记为K5。
6. 用c1张2元的纸币,支付K5元中的整2部分,剩余金额记为K6。
7. 用c0张1元的纸币,支付K6元中的整1部分。
最终,支付K元所需的最少纸币数就是c6 + c5 + c4 + c3 + c2 + c1 + c0。
相关问题
用100元人民币兑换10元5元和1元的纸币共50张实验步骤
以下是用100元人民币兑换10元、5元和1元纸币共50张的实验步骤:
1. 使用while循环进行兑换:
```python
total_money = 100
count = 0
i = 0
j = 0
k = 0
while total_money >= 10 and count < 50:
if i < 10:
i += 1
total_money -= 10
count += 1
elif j < 5:
j += 1
total_money -= 5
count += 1
elif k < 35:
k += 1
total_money -= 1
count += 1
print("10元纸币数量:", i)
print("5元纸币数量:", j)
print("1元纸币数量:", k)
```
2. 使用for循环进行兑换:
```python
total_money = 100
count = 0
i = 0
j = 0
k = 0
for i in range(10):
for j in range(5):
for k in range(35):
if total_money >= 10 and count < 50:
total_money -= 10
count += 1
elif total_money >= 5 and count < 50:
total_money -= 5
count += 1
elif total_money >= 1 and count < 50:
total_money -= 1
count += 1
print("10元纸币数量:", i)
print("5元纸币数量:", j)
print("1元纸币数量:", k)
```
3. 使用do-while循环进行兑换(Python中没有原生的do-while循环,可以使用while循环实现):
```python
total_money = 100
count = 0
i = 0
j = 0
k = 0
while True:
if total_money >= 10 and count < 50:
total_money -= 10
count += 1
i += 1
elif total_money >= 5 and count < 50:
total_money -= 5
count += 1
j += 1
elif total_money >= 1 and count < 50:
total_money -= 1
count += 1
k += 1
else:
break
print("10元纸币数量:", i)
print("5元纸币数量:", j)
print("1元纸币数量:", k)
```
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元纸币数量做出限制。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)