已知钱数x不足10元,要用1元、五角、1角,1分的硬币表示,用最少的硬币数量,设计算法,求出硬币的个数.

问题分析：根据常识,我们到店里买东西找钱时,老板总是先给我们最大面值的,要是不够再找面值小一点的,直到找满为止.如果老板都给你找分数的或者几角的,那你肯定不干,另外,他也可能没有那么多零碎的钱给你找.其实这就是一个典型的贪心选择问题.问题的算法设计与实现：先举个例子,假如老板要找给我99分钱,他有上面的面值分别为25,10,5,1的硬币数,为了找给我最少的硬币数,那么他是不是该这样找呢,先看看该找多少个25分的,诶99／25＝3,好像是3个,要是4个的话,我们还得再给老板一个1分的,我不干,那么老板只能给我3个25分的拉,由于还少给我24,所以还得给我2个10分的和4个1分.具体实现
view plaincopy to clipboardprint?
//找零钱算法
//输入：数组m,依次存放从大到小排列的面值数,n为需要找的钱数,单位全部为分
//输出：数组num,对照数组m中的面值存放不同面值的硬币的个数,就找钱方案
public static int[] zhaoqian(int m[],int n)
{
int k=m.length;
int[] num=new int[k];
for(int i=0;i