Project Euler——Problem 15 - Daybreakcx's Blog - Keep Programming! With Algorithm! With Fun!
Project Euler——Problem 14
Project Euler——Problem 16

Project Euler——Problem 15

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

原题与答案:

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位整数。程序源代码如下所示:

  1. #include<stdio.h>
  2. int i;
  3. long long ans;
  4. int main()
  5. {
  6.         ans=1;
  7.         for (i=1;i<=20;i++)
  8.         {
  9.                 ans=ans*(20+i);
  10.                 ans/=i;
  11.         }
  12.         printf("%lld\n",ans);
  13.         return 0;
  14. }

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter