小竞赛一。锻炼锻炼（清柳，看看能否置顶）

Question

给定任意数量的现金，给定了0.5元、0.25元、0.10元、0.05元、0.01元的硬币，请写出一个程序（实现的函数行了），计算出换零钱方式的种数。

Answer 1

刚看到消息，置顶数量是有限的，所以如果本贴大家参与热情高的话需要其他几个放几天再把这个放上去。欢迎大家提出类似题目，最好要切合实际应用而且不要把作业贴上来:)
关于问题本身，在”问题求解与程序设计“的课程中见过同样的题目，教材上就有实现方式，另外讲greedy method时此类题目有了除此之外还能解决如何是找的硬币数最少的算法。
这也是台湾景文技术学院89年大专电脑程序竞赛的题目。

Answer 2

这题目虽然是几十年前的问题，我在MIT的书上看到的。虽然难度不大，但觉得对于递归问题和效率的考虑上却是有很好思考价值，对其他人的提高有一定帮助

Answer 3

将总数为a的现金换成n种硬币的不同方式的数目=
    将现金数a换成除了第一种（任意某种就行）之外的所有其他硬币的不同方式的数目+
        ......

Answer 4

to0: sqfeiyu(流星雨)
题目是求种数！

Answer 5

                 0.01 0.05 0.1 0.25 0.5
0.01                  1,1 1,5 1,10 1,25 1,50
0.05                   0 1,1 1,2 1,5 1,10
0.1                   0 0 1,1 0 1,5
0.25                   0 0 0 1,1 1,2
0.5                   0        0 0 0 1
0.01&0.05
0.01&0.05&0.1
0.01&0.05&0.1&0.25
0.01&0.1
0.01&0.25
0.01&0.1&0.25
0.1&0.05&0.25
0.05&0.1
0.05&0.25
…
把提供的钱币进行内部组合,看能由多少个内部组合构成.
然后再用模方法做,到时就计算这其中的组合有多少.
如0.76=0.5+0.25+0.01
但0.25可分为=0.1+0.1+0.05或25个0.01或....
逐一分解为不可分为止.
可取得不同的数字组合,组合数不相同则组数就++.不知这样做会如何,个人的一个想法,没有去上机验证.还望大家也想想,不一定要
递归,程序清晰点小脑袋也会好受些,:<大家多批多提啊

Answer 6

呵呵，大家光说不做，楼主怒了
那我就先献丑using System;
class MainClass
{
    static int GetChange(int money, int maxChange)
    {
        if (money < 1 || maxChange < 1)
        {
            return 0;
        }
        if (money < 5 || maxChange < 5)
        {
            return 1;
        }
        if (money < maxChange)
        {
            if (money >= 25)
                return GetChange(money, 25);
            if (money >= 10)
                return GetChange(money, 10);
            if (money > 5)
                return GetChange(money, 5);
            else
                return 1;
        }
        if (money == maxChange)
        {
            if (maxChange == 50)
            {
                return 1 + GetChange(money, 25);
            }
            if (maxChange == 25)
            {
                return 1 + GetChange(money, 10);
            }
            if (maxChange == 10)
            {
                return 1 + GetChange(money, 5);
            }
            if (maxChange == 5)
            {
                return 2;
            }
        }
        if (maxChange == 50)
        {
            return GetChange(money, 25) + GetChange(money - 50, 50);
        }
        if (maxChange == 25)
        {
            return GetChange(money, 10) + GetChange(money - 25, 25);
        }
        if (maxChange == 10)
        {
            return GetChange(money, 5) + GetChange(money - 10, 10);
        }
        if (maxChange == 5)
        {
            return 1+GetChange(money - 5, 5);
        }
        else
        {
            return 1;
        }
    }
    static void Main()
    {
        int money = 0; //以分为单位，比如money=50，表示5角钱。
        for (money = 1; money < 51; money++)
        {
            Console.WriteLine(money + "分,找钱方式个数为: " + GetChange(money, 50));
        }
        Console.ReadLine();
    }
}

Answer 7

to: Kevin_jun() 
你的想法跟Ivony() 差不多的。
还是先把它做下来吧！
然后大家在讨论改良

Answer 8

先把硬币面值和目标现金数全部转成以分为单位，然后就是简单的动态规划:using System;class Class1
{
    const int maxCents = 1000000;
    int[] coins = {50, 25, 10, 5, 1};
    int[] a = new int[maxCents];    public int getChange(int cents)
    {
          if(cents >= maxCents) 
              throw new ArgumentException("The number of money is too large.");
          a[0] = 1;
          for(int i=1; i<=cents; i++)
          {
               a[i] = 0;
               for(int j=0; j<coins.Length; j++)
                   if(i-coins[j]>=0) a[i] += a[i-coins[j]];
          }
          return a[cents];
    }
    
}