MiYu原创, 转帖请注明 : 转载自 

题目地址:

         

题目描述:

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

题目分析:

假设小兔的棋盘是 8 × 8 的 ( 当然你也可以假设是其他 )。如下图:

箭头方向表示从该格子下一步能去的格子。因为不能穿越对角线，所有对角线上的格子只有进去的箭头，没有出来的箭头。

观察上图你就可以发现，其实这是一张关于对角线对称的图。所有我们只要求一个方向的值，然后乘以2即可。

我们就拿下三角来考虑。不难发现，所有在0列上的格子，路径数都是 

1 (只能从上面过来)。

而其他格子则都是由上、左两个方向过来，即:

f(i, j) = f(i - 1, j) + f(i, j - 1);

另外

f(i, i) = f(i, j - 1)  或者 f(i, i) = f( i-1, j ) ;

代码如下:

MiYu原创, 转帖请注明 : 转载自 

#include

<

iostream

>

using

 

namespace

 std;

typedef 

long

 

long

 int64;

int64 f[

37

][

37

];

int

 main()

{

    

int

 ca

=

0

;

    

int

 N;

    

while

 ( cin 

>>

 N , N 

+

 

1

 )

    {

        

++

 ca;

        

for

 ( 

int

 i 

=

 

1

;i 

<=

 N; 

++

 i )

        {

              f[

0

][i] 

=

 

1

;

        }

        

for

 ( 

int

 i 

=

 

1

; i 

<

 N; 

++

 i )

        {

              

for

 ( 

int

 j 

=

 i; j 

<=

 N; 

++

 j )

              {

                    

if

 ( i 

==

 j )

                    {

                         f[i][j] 

=

 f[i

-

1

][j];

                    }

                    

else

                    {

                         f[i][j] 

=

 f[i

-

1

][j] 

+

 f[i][j

-

1

];

                    }

              }

        }

        printf(

"

%d %d %I64d\n

"

, ca, N, 

2

 

*

 f[N

-

1

][N] );

    }

    

return

 

0

;

}

另外看别人的解题报告说这个是卡特兰数 ( 详细请查看    ), 其实现在还不理解, 分析如下:

Catalan数。。

令h(

1

)＝

1

,h(

0

)

=

1

，catalan数满足递归式：

　　h(n)

=

 h(

0

)

*

h(n

-

1

)

+

h(

1

)

*

h(n

-

2

) 

+

  

+

 h(n

-

1

)h(

0

) (其中n

>=

2

)

　　另类递归式：

　　h(n)

=

((

4

*

n

-

2

)

/

(n

+

1

))

*

h(n

-

1

);

　　该递推关系的解为：

　　h(n)

=

C(2n,n)

/

(n

+

1

) (n

=

1

,

2

,

3

,…)

附卡特兰代码:

#include

<

stdio.h

>

int

 main()

{

    __int64 a[

37

][

37

]

=

{

0

};

    

int

 i,j,n,t

=

0

;

    a[

0

][

0

]

=

0

;

    a[

0

][

1

]

=

1

;

    a[

1

][

1

]

=

2

;

    

for

(i

=

2

;i

<

37

;i

++

)

    {

        a[i][

0

]

=

1

;

        

for

(j

=

1

;j

<

i

-

1

;j

++

)

            a[i][j]

=

a[i][j

-

1

]

+

a[i

-

1

][j];

        a[i][i

-

1

]

=

a[i][i

-

2

]

+

a[i

-

1

][i

-

1

]

/

2

;

        a[i][i]

=

2

*

a[i][i

-

2

]

+

a[i

-

1

][i

-

1

];

 

    }

    

while

(scanf(

"

%d

"

,

&

n)

&&

n

!=-

1

)

    {

        printf(

"

%d %d %I64d\n

"

,

++

t,n,a[n][n]);

    }

    

return

 

0

;

}