货币币值有100、50、20、10、5、2、1元共七种,某单位给给职工发工资(精确到元),为了使职工领取的货币张数最少,通过键盘输入职工工资,使用贪心算法求出最少的货币张数。 源程序及运行结果:用c语言
时间: 2023-12-28 18:14:23 浏览: 52
#include <stdio.h>
int main()
{
int salary, money[7] = {100, 50, 20, 10, 5, 2, 1}, count[7] = {0};
// money数组存储货币币值,count数组存储每种货币的张数
printf("请输入职工工资:");
scanf("%d", &salary);
for(int i = 0; i < 7; i++)
{
count[i] = salary / money[i]; // 计算每种货币的张数
salary %= money[i]; // 计算剩余的工资
}
printf("最少的货币张数为:\n");
for(int i = 0; i < 7; i++)
{
printf("%d元:%d张\n", money[i], count[i]); // 输出每种货币的张数
}
return 0;
}
// 运行结果:
// 请输入职工工资:3456
// 最少的货币张数为:
// 100元:34张
// 50元:1张
// 20元:0张
// 10元:0张
// 5元:1张
// 2元:0张
// 1元:1张
相关问题
货币币值有100、50、20、10、5、2、1元共七种,某单位给给职工发工资(精确到元),为了使职工领取的货币张数最少,通过键盘输入职工工资,使用贪心算法求出最少的货币张数。
算法思路:
贪心算法的思路是每次选择当前情况下最优的解,再基于当前情况寻找下一个最优解,直到达到最终目标。在本题中,我们采用贪心算法的思路,每次选择最大面额的货币,直到工资为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张。
某单位给职工发工资(精确到元),为了保证不临时兑换零钱,且取款的张数最少,取工资前要统计出所有职工的工资所需各种币值(100、50、20、10、5、1元共6种)的张数。的算法思想
这是一道贪心算法的经典问题。贪心算法的思想是每一步都选择最优的策略,期望最终得到全局最优解。
对于这个问题,我们可以按照从大到小的顺序依次考虑每种币值,每次取尽可能多的该币值的纸币,直到无法取为止。这样就可以保证取款的张数最少,且不需要临时兑换零钱。
下面是具体的算法实现:
1. 定义一个列表 `money_list`,记录每种币值的张数,初始值为0。
2. 对于每个职工的工资金额:
1. 从大到小遍历每种币值,依次尝试取尽可能多的该币值的纸币。
2. 如果该币值的纸币张数已经达到了需要的数量,则继续尝试下一种币值。
3. 如果该币值的纸币张数还不够,且该币值的面值小于等于剩余工资金额,则尽可能多地取该币值的纸币,并将该币值的张数加入 `money_list` 中。
4. 如果该币值的面值大于剩余工资金额,则继续尝试下一种币值。
3. 最终统计 `money_list` 中每种币值的张数,就是所有职工的工资所需各种币值的张数。
这个算法的时间复杂度是 O(n),其中 n 是职工的数量。