程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> hdu 2067 小兔的棋盤(卡特蘭數)

hdu 2067 小兔的棋盤(卡特蘭數)

編輯:關於C語言

 

小兔的棋盤

 

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2323    Accepted Submission(s): 1360

Problem Description

小兔的叔叔從外面旅游回來給她帶來了一個禮物,小兔高興地跑回自己的房間,拆開一看是一個棋盤,小兔有所失望。不過沒過幾天發現了棋盤的好玩之處。從起點(0,0)走到終點(n,n)的最短路徑數是C(2n,n),現在小兔又想如果不穿越對角線(但可接觸對角線上的格點),這樣的路徑數有多少?小兔想了很長時間都沒想出來,現在想請你幫助小兔解決這個問題,對於你來說應該不難吧!

 

Input

每次輸入一個數n(1<=n<=35),當n等於-1時結束輸入。

 

Output

對於每個輸入數據輸出路徑數,具體格式看Sample。

 

Sample Input

1

3

12

-1

 

Sample Output

1 1 2

2 3 10

3 12 416024

         最基礎的卡特蘭數(不是大數),直接公式,網上找到其他求法,都寫上去了,到時我會對卡特蘭數進行一些總結的,先看這個最簡單的。

 

代碼:

Java代碼 

#include <iostream> 

#include <stdio.h> 

#include <memory.h> 

#include <cmath> 

using namespace std; 

 

long long h[45]; 

long long f[45][45]; 

 

void catalan2()     //卡特蘭數:第二種求法 

    int i, j; 

    for(i = 1; i <= 36; i++) 

    { 

        f[0][i] = 1; 

    } 

    for(i = 1; i < 36; i++) 

    { 

        for(j = i; j <= 36; j++) 

        { 

            if(i == j) 

            { 

                f[i][j] = f[i-1][j]; 

            } 

            else 

            { 

                f[i][j] = f[i-1][j] + f[i][j-1]; 

            } 

        } 

    } 

 

void catalan()      //卡特蘭數:第一種求法 

    int i, j; 

    h[0] = 1; 

    for(i = 1; i < 36; i++) 

    { 

        h[i] = 0; 

        for(j = 0; j <= i; j++) 

        { 

            h[i] += h[j] * h[i-j-1]; 

        } 

    } 

 

int main() 

    int n, zz = 1; 

    catalan(); 

    catalan2(); 

    while(scanf("%d", &n) != EOF) 

    { 

        if(n == -1) break; 

        //h[n]、f[n][n]都是卡特蘭數 

        //printf("%d %d %I64d\n", zz++, n, h[n]*2); 

        printf("%d %d %I64d\n", zz++, n, f[n][n]*2); 

    } 

 

    return 0; 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved