计算不同的方式使（金钱）从$ 167.37变化？ [英] Compute the different ways to make (money) change from $167.37?

问题描述

这是一个采访问题：

给出一个金额，比如$ 167.37，找到所有可能的方法来生成这个金额的变化任何人可以想到空间和时间有效的算法和支持代码，请分享。

p>

这是我写的代码（工作）。我试图找到这个的运行时间，任何帮助是赞赏

  import java.util.HashMap; 
 import java.util.Iterator; 
导入java.util.LinkedList; 
 import java.util.Map; 
 
 
 public class change_generation {
 
 / ** 
 * @param args 
 * / 
 
 public static void generatechange（float amount，LinkedList& Float>面值，HashMap< Float，Integer> useddenominations）
 {
 if（amount< 0）
 return; 
 if（amount == 0）
 {
迭代器< Float> it = useddenominations.keySet（）。iterator（）; 
 while（it.hasNext（））
 {
 Float val = it.next（）; 
 System.out.println（val +::+ useddenominations.get（val））; 
} 
 
 System.out.println（**************************** ********）; 
 return; 
} 
 
（浮点数：面额）
 {
 
 if（amount-denom< 0）
 continue; 
 
 if（useddenominations.get（denom）== null）
 useddenominations.put（denom，0）; 
 
 useddenominations.put（denom，useddenominations.get（denom）+1）; 
 generatechange（amount-denom，denominations，useddenominations）; 
 useddenominations.put（denom，useddenominations.get（denom）-1）; 
} 
 
} 
 
 public static void main（String [] args）{
 // TODO自动生成的方法存根
 float数量= 2.0f; 
 float nikle = 0.5f; 
 float dollar = 1.0f; 
 float ddollar = 2.0f; 
 
 LinkedList< Float> denominations = new LinkedList< Float>（）; 
 
 
 denominations.add（ddollar）; 
 denominations.add（dollar）; 
 denominations.add（nikle）; 
 
 HashMap< Float，Integer> useddenominations = new HashMap< Float，Integer>（）; 
 generatechange（amount，denominations，useddenominations）; 
} 
 
} 
  

解决方案

  import java.util.HashMap; 
 import java.util.Iterator; 
 import java.util.LinkedList; 
 import java.util.Map; 
 
 public class change_generation {
 
 static int jj = 1; 
 
 public static void generatechange（float amount，LinkedList< Float> denominations，
 HashMap< Float，Integer> useddenominations）{
 if（amount< 0）
 return ; 
 if（amount == 0）{
 Iterator< Float> it = useddenominations.keySet（）。iterator（）; 
 while（it.hasNext（））{
 Float val = it.next（）; 
 System.out.println（val +::+ useddenominations.get（val））; 
} 
 System.out.println（******************************** ****）; 
 
 return; 
} 
 
（Float denom：denominations）{
 if（amount-denom< 0）
 continue; 
 if（useddenominations.get（denom）== null）
 useddenominations.put（denom，0）; 
 
 useddenominations.put（denom，useddenominations.get（denom）+1）; 
 generatechange（amount-denom，denominations，useddenominations）; 
 useddenominations.put（denom，useddenominations.get（denom）-1）; 
} 
} 
 
 public static void main（String [] args）{
 float amount = 2.0f; 
 float nikle = 0.25f; 
 float dollar = 1.0f; 
 float ddollar = 2.0f; 
 
 LinkedList< Float> denominations = new LinkedList< Float>（）; 
 
 denominations.add（ddollar）; 
 denominations.add（dollar）; 
 denominations.add（nikle）; 
 
 HashMap< Float，Integer> useddenominations = new HashMap< Float，Integer>（）; 
 generatechange（amount，denominations，useddenomination）; 
} 
} 
  

This was an interview question:

Given an amount, say $167.37 find all the possible ways of generating the change for this amount using the denominations available in the currency?

Anyone who could think of a space and time efficient algorithm and supporting code, please share.

Here is the code that i wrote (working) . I am trying to find the running time of this, any help is appreciated

    import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;


public class change_generation {

    /**
     * @param args
     */

    public static void generatechange(float amount,LinkedList<Float> denominations,HashMap<Float,Integer> useddenominations)
    {
        if(amount<0)
            return;
        if(amount==0)
        {
            Iterator<Float> it = useddenominations.keySet().iterator();
            while(it.hasNext())
            {
                Float val = it.next();
                System.out.println(val +" :: "+useddenominations.get(val));
            }

            System.out.println("**************************************");
            return;
        }

        for(Float denom : denominations)
        {

            if(amount-denom < 0)
                continue;

            if(useddenominations.get(denom)== null)
                useddenominations.put(denom, 0);

            useddenominations.put(denom, useddenominations.get(denom)+1);
            generatechange(amount-denom, denominations, useddenominations);
            useddenominations.put(denom, useddenominations.get(denom)-1);
        }

    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        float amount = 2.0f;
        float nikle=0.5f;
        float dollar=1.0f;
        float ddollar=2.0f;

        LinkedList<Float> denominations = new LinkedList<Float>();


        denominations.add(ddollar);
        denominations.add(dollar);
        denominations.add(nikle);

        HashMap<Float,Integer> useddenominations = new HashMap<Float,Integer>();
        generatechange(amount, denominations, useddenominations);
    }

}

解决方案

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;

public class change_generation {

  static int jj=1;

  public static void generatechange(float amount,LinkedList<Float> denominations, 
                                  HashMap<Float,Integer> useddenominations) {
    if(amount<0)
        return;
    if(amount==0) {
        Iterator<Float> it = useddenominations.keySet().iterator();
        while(it.hasNext()) {
            Float val = it.next();
            System.out.println(val +" :: "+useddenominations.get(val));
        }
        System.out.println("**************************************");

        return;
    }

    for(Float denom : denominations) {
        if(amount-denom < 0)
            continue;
        if(useddenominations.get(denom)== null)
            useddenominations.put(denom, 0);

        useddenominations.put(denom, useddenominations.get(denom)+1);
        generatechange(amount-denom, denominations, useddenominations);
        useddenominations.put(denom, useddenominations.get(denom)-1);
    }
  }

  public static void main(String[] args) {
    float amount = 2.0f;
    float nikle=0.25f;
    float dollar=1.0f;
    float ddollar=2.0f;

    LinkedList<Float> denominations = new LinkedList<Float>();

    denominations.add(ddollar);
    denominations.add(dollar);
    denominations.add(nikle);

    HashMap<Float,Integer> useddenominations = new HashMap<Float,Integer>();
    generatechange(amount, denominations, useddenominations);
  }
}

这篇关于计算不同的方式使（金钱）从$ 167.37变化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！