杰啦 java初學記錄

  1   2
  3 import java.util.Scanner;
  4 
  5 /**對于給定的金額，給定的紙幣數量，求一共有幾種組合方式
  6  * eg:1,5,10,20,50,100
  7  *    6 5 4 3 2 1
  8  *    思路:通過迭代實現求解，難點在于怎么解決每次打印問題
  9  * @author 杰拉
 10  *
 11  */
 12 public class Finder02 {
 13     public static int cou =0;
 14     public static StringBuilder stB = new StringBuilder();
 15     public static void main(String[] args) {
 16         int[] money = {1,5,10,20,50,100};
 17         int[] count = new int[6];
 18         Scanner sc = new Scanner(System.in);
 19         int Amount = Integer.parseInt( sc.nextLine());    
 20         String[] str = sc.nextLine().split(" ");
 21         sc.close();
 22         for(int i=0;i<6;i++)
 23         {
 24             count[i] = Integer.parseInt(str[i]);
 25         }
 26         find(Amount, money,"");
 27         System.out.println(cou);
 28         res(stB, count);
 29     }
　　　　　　//遞歸求解所有的排列組合方式
 30     public static void find(int Amount,int[] now,String str)
 31     {
　　　　　　　　//存放當前剩余錢數
 32         int tem = Amount;
 33         for(int i=0;i<now.length;i++)
 34         {            
 35             if(i==0)
 36             {
 37                 for(int p=0;p<Amount;p++)
 38                 {
 39                     //System.out.print("1 ");
 40                     stB.append("1,");
 41                 }
 42                 Amount = 0;
 43                 if(Amount==0)
 44                 {
 45                     cou++;
 46                     stB.append("\n");
 47                     //System.out.println();
 48                 }
 49             }
 50             else
 51             {    
 52                 Amount = tem;
 53                 for(int j=0;j<(int)Amount/now[i];j++)
 54                 {
 55                     str = str + now[i] + ",";
 56                     //System.out.print(str);
 57                     stB.append(str);
 58                     find(Amount-(j+1)*now[i],IntToInt(i-1),str);
　　　　　　　　　　　　
 59                     if(j==((int)Amount/now[i]-1))
 60                     {
 61                         int x = str.length()-(j+1)*((now[i]+"").length()+1);
 62                         str = str.substring(0,x);
 63                     }
 64                 }    
 65             }    
 66         }    
 67     }
 68     //實現數組的子數組
 69     public static int[] IntToInt(int x)
 70     {
 71         int[] money = {1,5,10,20,50,100};
 72         int[] now = new int[x+1];
 73         for (int i = 0; i < now.length; i++) {
 74             now[i] = money[i];
 75         }
 76         return now;
 77     }
　　　　　//輸出符合要求的組合　　
 78     public static void res(StringBuilder sb,int[] count)
 79     {
 80         int[] money = {1,5,10,20,50,100};
 81         String[] str = sb.toString().split("\n");
 82         
 83         for (int i = 0; i < str.length; i++) {
 84             String[] str1 = str[i].split(",");
 85             int[] mount = new int[6];
 86             boolean flag = true;
 87             for (int j = 0; j < str1.length; j++) {
 88                 int tem = Integer.parseInt(str1[j]);
 89                 for (int k = 0; k < mount.length; k++) {
 90                     if(tem==money[k])
 91                     {
 92                         mount[k]+=1;
 93                     }
 94                 }
 95             }
 96             for (int j = 0; j < mount.length; j++) {
 97                 if(mount[j]>count[j])
 98                 {
 99                     flag = false;
100                 }
101             }
102             if(flag)
103             {
104                 System.out.println(str[i].toString());
105             }
106             
107         }
108     }
109 }