1496.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1496 on 2005-03-23 at 19:15:36 */ 
#include <stdio.h>

int combinat(int, int);

int main()
{
    int n, i, j, m, k, t;
    
    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        scanf("%d", &m);
        t = (m+1)/2;
        k = 0;
        printf("Scenario #%d:\n", i);
        for(j = 0; j <= t; j++){
            k += combinat(m-j+1, j);
        }
        printf("%d\n\n", k);
    }
    
    return 0;
}            
        
int combinat(int m, int n)
{
    int i, j;
    int mat[45][45];
    
    if (n == 0 || m == n){
        return 1;
    }else{
        if(2 * n > m){
            n = m - n;
        }
        for(j = 0; j < n; j++){
            mat[0][j] = 1;
            for(i = 1; i <= m-n; i++){
                if(j == 0){
                    mat[i][j] = i+1;
                }else{
                    mat[i][j] = mat[i-1][j] + mat[i][j-1];
                }
            }        
        }              			
        return (mat[m-n][n-1]);
    }
}