UVa 369 - Combinations

( Tip: 點擊左上方的三橫槓選單按鈕，可以收起左側 Pdf 頁。)

Step 1. 題目概要

  • 輸入兩個整數 n,m
  • 輸出 排列組合中的 Cn取m
  • 當輸入為 0 0 時，程式終止

Step 2. 解題思路

  • 利用動態規劃(Dynamic Programming)的概念，從尾巴的部分開始去切。尾巴就是第n個，這個東西必定要決定取或不取，將第n物拿開，剩下的n-1個東西就會變成同性質的子問題
    • dp[n][m]=k (在n個物品中取出m個的方法有k種)
    • 若第n物選擇取，則剩餘的n-1物中，要剛好取m-1個
    • 若第n物選不取，則剩餘的n-1物中，要剛好取m個
    • dp[n][m] = dp[n-1][m-1] + dp[n-1][m]

Step 3. 範例輸入與輸出 - Sample Input and Output

1
2
3
4
100 6
20 5
18 6
0 0
1
2
3
100 things taken 6 at a time is 1192052400 exactly.
20 things taken 5 at a time is 15504 exactly.
18 things taken 6 at a time is 18564 exactly.

Extra Sample Input
Extra Sample Output

uDebug 快速連結
Diffnow (線上比對程式)
C++ Online Compiler
Python Online Compiler

Step 4. 參考程式碼 - Accepted Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    //dp遞迴建表
    long long int c[105][105]; //c[n][m]=k (在n個物品中取出m個的方法有k種)
    memset(c,0,sizeof(c)); //初始化為全0
    for(int i=1;i<=100;i++) {
        c[i][0]=1;
        for(int j=1;j<=i;j++) {
            if(i==j) c[i][j]=1;
            /*
            若取第 n 物，則餘下 n-1 個中，要剛好取 m-1 個，加上第 n 個剛好；
            若不取第 n 物，則餘下 n-1 個中，要剛好取 m 個才會剛好。
                        取第 n 個     不取第 n 個
            dp[n][m] = dp[n-1][m-1] + dp[n-1][m]
            */
            else c[i][j]=c[i-1][j-1]+c[i-1][j];
        }
    }
    //input
    int n,m;
    while((cin>>n>>m)&&!(n==0&m==0)) {
        //output (讀入n,m，查表輸出)
        cout<<n<<" things taken "<<m<<" at a time is "<<c[n][m]<<" exactly.\n";
    }
    return 0;
}