我在面试中的一道算法题(1元换零)
给你一元钱,将它换成零钱例如:1元可以由两个五毛的组成、10个一毛的组成，100个一分的组成等...
用算法列出所有的可能
我的解法如下:1元=100分 有六种零钱 五角，两角，一角，五分，两分，1 分 统一下单位都用分吧
当时我的解题思想是这样的.我把100做为一个结点,那么这个节点有六条支路分别是(-i*50),(-i*20),(-i*10),(-i*5),(-i*2),(-i*1).通过这六条支路又可以到达一个新的结点,这个新的结点它也有上面的六条支路再到达下一个结点,如果最后的结点为0说明就找到了一个解.通过上面的分析我们就可以很容易得到一个六叉树.对一树这种数据结构,可以使用递归数法,虽然这种算法效率低,但是代码少而且更易理解.代码如下(C#版):
class Program
{
static int[]a=new int[]{50,20,10,5,2,1};
static int total = 0;
static void GetResult(string[] result, int Rank, int Remain)
{
for (int i = 0; Remain - i * a[Rank] >= 0; i++)
{
result[Rank] = i.ToString() + "*" + a[Rank].ToString();
if (Remain - i * a[Rank] == 0)
{
for (int j = 0; j <= Rank; j++)
{
Console.Write("{0} ", result[j]);
}
Console.WriteLine();
total++;
}
if ((Rank +1<6) && (Remain - i * a[Rank]>0))
{
GetResult(result, Rank + 1, Remain - i * a[Rank]);
}
}
}
static void Main(string[] args)
{
string[] Result = new string[100];
GetResult(Result, 0, 100);
Console.WriteLine(total);
}
}
