Project Euler——Problem 15

daybreakcx posted @ 2009年7月18日 23:43 in Prject Euler , 1398 阅读

原题与答案：

Problem 15

19 April 2002

Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20×20 grid?

Answer:137846528820

分析与解答：

这个题目也十分经典了，问的是从一个20×20的格子的左上角走到右下角有多少种走法。一个经典的解法就是利用组合数学的知识，实际上不论你怎么走，最后都是走了20条横边和20条竖边，换句话说也就是20条横边和竖边的组合问题，横边和竖边自己内部都是自排序的，因此问题公式就可以很容易得出，假设是n×m的格子，那么解决的方案数就是 $C_{n+m}^n$ ，于是这个题目的结果可以直接笔算出来就是 $C_{40}^{20}=137846528820$ 。当然，写个程序也很快，注意结果是一个64位整数。程序源代码如下所示：

#include<stdio.h>
int i;
long long ans;
int main()
{
ans=1;
for (i=1;i<=20;i++)
{
ans=ans*(20+i);
ans/=i;
}
printf("%lld\n",ans);
return 0;
}