杭電1284 兌換錢币問題

解題報告：

     大緻題意：現在有面值為3、2、1的錢币

                 問：給你一個金額N ，問有多少組合方法

 下面給出代碼向大家講解：

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int sum = 0;
            for (int i = 0; i <= n / 3; i++) {
                int k = (n - i * 3) / 2;
                sum += k + 1;
            }
            System.out.println(sum);
        }
    }
}
           

首先我們假設N=20 ，我現在隻拿0個3分的那就還剩下20-0分，我在将剩下的20分全都分成2分這裡就會有1種分法

（裡面有隐藏了小的分法，因為2可以分成兩個1）

也就是說現在沒有一個3分的錢币 

全部都是二算一種分法（2,2,2,2,2,2,2,2,2,2） 

将其中一個二成兩1又是一種分發（2,2,2,2,2,2,2,2,2,1,1） 

在将一個二有變成兩個1又是一種分法

總結這裡就有10種分法

在加上最後一種就是20可以全都分成1。

然後在假設有一個3分的硬币，兩三分的硬币一次類推即可求出最後的總數。

程式解讀：

      for (int i = 0; i <= n / 3; i++) {

           表示從0個3分硬币開始到n/3個

    int k = (n - i * 3) / 2;

           表示先取出已有的3分硬币，求出分成2+1的組合種數

     sum += k + 1;

          表示加上最後一種全為一的情況