怎么用Java實現(xiàn)貨幣組合

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

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

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

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

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

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

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

y<= v1andv5andv10/5-2x   設(shè)  m = v1andv5andv10/5；

y<=m;   x=0 ;

y<=m-2 ;   x=1 ;

y<=m-4； x=2 ;

其實質(zhì)上就是一個等差數(shù)列求和

4:   每趟循環(huán)的組合數(shù)為 z1 * z2 , 然后求和即為最終的結(jié)果。

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  非負整數(shù)解的個數(shù)  =>   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  非負整數(shù)解的個數(shù)
                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;

    }
}

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

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