货币币值有100、50、20、10、5、2、1元共七种,某单位给给职工发工资(精确到元),为了使职工领取的货币张数最少,通过键盘输入职工工资,使用贪心算法求出最少的货币张数。
时间: 2023-10-20 07:06:15 浏览: 81
算法思路:
贪心算法的思路是每次选择当前情况下最优的解,再基于当前情况寻找下一个最优解,直到达到最终目标。在本题中,我们采用贪心算法的思路,每次选择最大面额的货币,直到工资为0为止。
算法步骤:
1. 读入职工工资w。
2. 定义货币面额数组a={100,50,20,10,5,2,1}。
3. 定义变量count,表示所需货币张数。
4. 从大到小遍历货币面额数组a,每次取出一个面额c。
5. 如果c小于等于工资w,说明可以用c元面额的货币来支付一部分工资。此时,计算使用c元面额的货币的张数n,n=w/c,将n加入count中,将工资w更新为w-w/c*c。
6. 如果c大于工资w,说明不能使用c元面额的货币,跳过该面额。
7. 判断工资w是否为0,若为0,输出count中的货币张数,程序结束。
Python代码实现如下:
```python
w = int(input("请输入职工工资:"))
a = [100, 50, 20, 10, 5, 2, 1]
count = []
for c in a:
if c <= w:
n = w // c
count.append(n)
w -= n * c
else:
count.append(0)
if w == 0:
print(sum(count))
```
测试:
输入职工工资为1234元,输出结果为13张货币:
```
请输入职工工资:1234
13
```
其中100元1张,50元0张,20元1张,10元1张,5元0张,2元2张,1元8张,共计13张。