怎么用Java實現貨幣組合

本篇內容主要講解“怎么用Java實現貨幣組合”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“怎么用Java實現貨幣組合”吧!

給你六種面額 1、5、10、20、50、100 元的紙幣，假設每種幣值的數量都足夠多，編寫程序求組成N元（N為0~10000的非負整數）的不同組合的個數。 先分析

1： 假定100和50兩種幣的和為num， num = 0,50,100,150，... ,  50* (N/50)  

      組合數為 z1  (100x +50y = num 的非負整數解的個數)

2： 20有k張，  k=0，1，2，3，.... , (N-num) / 20

3:   那么1，5，10 這幾種幣的和為 v1andv5andv10 = N- num - 20 * k;   

組合數為z2  (10x+5y <= v1andv5andV10的非負整數解的個數) 

y<= v1andv5andv10/5-2x   設  m = v1andv5andv10/5；

y<=m;   x=0 ;

y<=m-2 ;   x=1 ;

y<=m-4； x=2 ;

其實質上就是一個等差數列求和

4:   每趟循環的組合數為 z1 * z2 , 然后求和即為最終的結果。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println(getTotal(scanner.nextInt()));
    }


    private static long getTotal(int money) {

        long total = 0L;

        for (int num = 0; num <= money; num += 50) {

            // 求解 100x + 50y = num  非負整數解的個數  =>   y = num/50 - 2x (x=0,1,2,3...,num/50/2) 
            int z1 = (num / 50) / 2 + 1;

            int v20 = (money - num) / 20;

            for (int k = 0; k <= v20; k++) {

                // 求解 10x + 5y <= v1andv5andV10  非負整數解的個數
                int v1andv5andV10 = money - num - 20 * k;

                int tmp = (v1andv5andV10 / 5);
                int kkkk = tmp / 2 + 1;
                int z2 = (tmp + 1) * kkkk - kkkk * (kkkk - 1);

                total = total + (long) (z1) * (long) z2;
            }

        }

        return total;

    }
}

不用質疑，這是個正確的答案，也是比較容易理解的答案。 內存消耗也應該是最優的，因為沒有使用數組，只是使用了幾個變量。運行速度也應該還可以， （money/50) * (money/20）/2  次循環運算，100萬內的輸入應該都是秒出結果。

到此，相信大家對“怎么用Java實現貨幣組合”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！