人民币换算算法的问题,Nokia面试题
现在假设有这种情况,我有100块钱,想换成不同面额的零钞,如下1:50 1-10张
2:20 1-5张
3:10 1-10张
要求
优先换50,比如输出结果应该是2张,因为允许换1到10张,所以20和10元就不用考虑
但是现在的问题是,假如面额的有130块钱的面值,那就是2张50,1张20,1张10元的
面额有不同的,要换算结果刚刚好,否则就输出0
谁有更好的算法,我觉得穷举法应该不是最好的
大家来讨论下 --------------------编程问答--------------------
--------------------编程问答-------------------- 學習 --------------------编程问答-------------------- 条件不充分 --------------------编程问答-------------------- 条件够吗? --------------------编程问答-------------------- 贪心算法即可 --------------------编程问答-------------------- 路过。。。。 --------------------编程问答-------------------- 学习. --------------------编程问答-------------------- 嗯.从高位算起.总数减去最高的50.如果大于0则50的数量加1,继续减50,如果还大于0.继续加小于0则跳到20那里去减... --------------------编程问答-------------------- 顶一下 --------------------编程问答-------------------- MK --------------------编程问答-------------------- if 输入==40
Dim Amount As Integer
Dim RMB50_Counter, RMB20_Counter, RMB10_Counter As Integer
Dim CurrentRMB As Integer
Amount = -1
Response.Write("总额: " & Amount & " RMB<br>")
RMB50_Counter = 0
RMB20_Counter = 0
RMB10_Counter = 0
CurrentRMB = 50
Do While Amount > 0
If Amount >= CurrentRMB Then
Amount = Amount - CurrentRMB
Select Case CurrentRMB
Case 50
RMB50_Counter = RMB50_Counter + 1
Case 20
RMB20_Counter = RMB20_Counter + 1
Case 10
RMB10_Counter = RMB10_Counter + 1
End Select
Else
Select Case CurrentRMB
Case 50
CurrentRMB = 20
Case 20
CurrentRMB = 10
Case Else
Exit Do
End Select
End If
Loop
Response.Write("50 RMB x" & RMB50_Counter & "<br>")
Response.Write("20 RMB x" & RMB20_Counter & "<br>")
Response.Write("10 RMB x" & RMB10_Counter & "<br>")
Response.Write("余款: " & Amount & " RMB<br>")
。。。。。。
--------------------编程问答-------------------- 关注 --------------------编程问答-------------------- 确实是贪心算法可以解决的,学习了! --------------------编程问答-------------------- 本人蠢笨,不知所云!就是无聊 --------------------编程问答-------------------- 学习学习 --------------------编程问答-------------------- 我是菜鸟,路过围观。。。。 --------------------编程问答-------------------- 除了穷举法,好像也没啥好方法,看 有没有对穷举法再优化下 --------------------编程问答-------------------- 学习! --------------------编程问答-------------------- 除50取余 为0就是商 不为零余数除20取余 。。还不为零就除10取余 钱的数目就是各自的商、 --------------------编程问答-------------------- 用总额与面额求幂,再整除! --------------------编程问答-------------------- --------------------编程问答--------------------
没错 --------------------编程问答-------------------- int a = 180;
int b = a % 50;
int RMB50_Count = a/50;
b = b%20;
int RMB20_Count = b/20;
b = b%10;
int RMB10_Count = b/10;
--------------------编程问答-------------------- 如果想学算法,类似你们说的贪心算法从哪儿可以学呢,数据结构里貌似没有…… --------------------编程问答-------------------- 一个迭代+职责链即可
伪代码
while(n<10)
{
if(n>=50&&50张数-->0)
{
n-=50;
}
if(n>=20&&20张数-->0)
{
n-=20
}
//剩下的不写了
} --------------------编程问答--------------------
up --------------------编程问答-------------------- Console.WriteLine("请输入要换的人民币:");
int RMB = Convert.ToInt32(Console.ReadLine());
int count50 = RMB / 50;
int left = RMB % 50;
int count20=0;
int count10=0;
int left1=0;
int left2=0;
if (left >= 20)
{
count20 = left / 20;
left1 = left % 20;
if (left1 >=10)
{
count10 = left1 / 10;
left2 = left1 % 10;
}
}
else
{
count10 = left / 10;
left2 = left % 10;
}
Console.WriteLine("{0}张50的,{1}张20的,{2}张10的",count50,count20,count10);
Console.ReadLine(); --------------------编程问答-------------------- 有趣的问题,解法多多 --------------------编程问答-------------------- 你是要算出什么?算出所有组成情况还是就是贪心算法需要的那个结果?
补充:.NET技术 , ASP.NET