题目15：从20*20的网格的左上角通往右下角有多少条路？

欧拉计划

Lattice paths

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.



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

题目：

从一个 2×2 网格的左上角开始，有 6 条（不允许往回走）通往右下角的路。



对于 20×20 的网格，这样的路有多少条？

翅膀团

1. #include <stdio.h>
   
2. 
   
3. int a(int x,int y)
   
4. {
   
5.     if(x==1)
   
6.     {
   
7.     return y;
   
8.     }
   
9.     if(y==1)
   
10.     {
    
11.     return 1;
    
12.     }
    
13.     return (a(x-1,y) + a(x,y-1));
    
14. }
    
15. 
    
16. int main(void)
    
17. {
    
18.     int i,l,f;
    
19.     printf("请输入所需的网格(如：2x2):");
    
20.     scanf("%dx%d",&i,&l);
    
21.     f = a(i,l);
    
22.     printf("共有%d条。\n",2*f);
    
23. }

复制代码

如果有错误希望指出

huomqh

这题不会，先放着。

DAY

这道题最重要的就是分析一下，，无论怎样走都要横着走n步，竖着走n步，因此可以用组合公式求C（n，2n）（这里的n为nXn方格）
答案:137846528820

1. 
   
2. 
   
3. import java.math.BigInteger;
   
4. import java.util.Scanner;
   
5. 
   
6. public class Main {
   
7. 
   
8.         public static BigInteger C(BigInteger N,BigInteger M){
   
9.                 BigInteger n=N;
   
10.                 BigInteger m=M;
    
11.                 BigInteger tM=BigInteger.ONE;
    
12.                 BigInteger tN=BigInteger.ONE;
    
13.                 while(n!=BigInteger.ZERO){
    
14.                         tM=tM.multiply(m);
    
15.                         tN=tN.multiply(n);
    
16.                         m=m.subtract(BigInteger.ONE);
    
17.                         n=n.subtract(BigInteger.ONE);
    
18.                 }
    
19.                 return tM.divide(tN);
    
20.         }
    
21.         public static void main(String[] args) {
    
22.                 Scanner sc = new Scanner(System.in);
    
23.                 BigInteger n=sc.nextBigInteger();
    
24.                 BigInteger m=sc.nextBigInteger();
    
25.                 System.out.println(C(n,m));
    
26.         }
    
27. }
    

复制代码

特别说明:这道题涉及到大数乘法。。。

飘飞的白杨

1. #杨辉三角
   
2. l = [1]
   
3. a = 20
   
4. while a:
   
5.     for i in range(len(l)-1,0,-1):
   
6.         l[i] = l[i] + l[i-1]
   
7.     l.append(1)
   
8.     a -= 1
   
9. print(sum(i**2 for i in l))
   

复制代码

答案：137846528820

迷雾少年

这个就是有公式规律的吧。。

QingXin

40步中取出20步横着走，剩下的20步全都竖着走，C40（上标）20（下标） = 40！/(20! * 20!)。

1. import math
   
2. math.factorial(40)/(math.factorial(20))**2

复制代码

渡风

此代码使用matlab编程
Problem15所用时间为0.00069592秒
Problem15的答案为137846528820

1. %题目15：从20*20的网格的左上角通往右下角有多少条路？
   
2. %总共横走20步，竖走20步，取20步怎么横走，竖就确定了，所以是C(40,20)
   
3. function Output=Problem15(Input)
   
4. tic
   
5. if nargin==0
   
6.     Input=20;
   
7. end
   
8. format long
   
9. Output=factorial(Input*2)/factorial(Input)^2;
   
10. toc
    
11. disp('此代码使用matlab编程')
    
12. disp(['Problem15所用时间为',num2str(toc),'秒'])
    
13. disp(['Problem15的答案为',num2str(Output)])
    
14. end
    

复制代码

fc1735

这题不用编程

37*31*29*23*13*11*7*5*3^2*2^2

鱼油小白

1. c
   
2. #include <stdio.h>
   
3. 
   
4. #define size 21
   
5. int main()
   
6. {
   
7.     long a[size][size];
   
8.     int i,j;
   
9. 
   
10.     for(i = 0; i<size; i++)
    
11.                 for(j = 0; j<size; j++)
    
12.                         a[i][j] = 0;
    
13. 
    
14.     for(i = 0; i<size; i++)
    
15.     {
    
16.         a[0][i] = 1;
    
17.         a[i][0] = 1;
    
18.     }
    
19.     for(i = 1; i<size; i++)
    
20.     {
    
21.         for(j = 1; j<size; j++)
    
22.         {
    
23.                         a[i][j] = a[i-1][j] + a[i][j-1];
    
24.         }
    
25.     }
    
26.     printf("%ld",a[size-1][size-1]);
    
27. 
    
28.     return 0;
    
29. }
    

复制代码

FlySelf

1. 
   
2. import time
   
3. import math
   
4. 
   
5. def lattice_paths(number):
   
6.     '求从number*number的网格的左上角通往右下角有多少条路'
   
7.     return int(math.factorial(2 * number) / (math.factorial(number)) ** 2)
   
8. 
   
9. 
   
10. start = time.clock()
    
11. print(lattice_paths(20))
    
12. end = time.clock()
    
13. print('程序执行了%fs。' %(end - start))
    

复制代码

执行结果：
137846528820
程序执行了0.000232s。

JonTargaryen

QingXin 发表于 2016-9-16 00:11
40步中取出20步横着走，剩下的20步全都竖着走，C40（上标）20（下标） = 40！/(20! * 20!)。

正解！

py阿碗

除了排列组合的数学算法
另一种解题思路是百度的：
0  1  1   1    1
1  2  3   4    5
1  3  6  10  15
1  4 10 20 35
1  5 15 35 70

每个数代表走到此处的走法，是它上方和左边的两个数之和。

1. L =[]
   
2. for i in range(21):
   
3.     L.append([])
   
4. L[0].append(0)
   
5. for y in range(1,21):
   
6.     L[0].append(1)
   
7. for x in range(1,21):
   
8.     for y in range(21):
   
9.         L[x].append(0)
   
10. for x in range(1,21):
    
11.     L[x][0] = 1
    
12. 
    
13. for x in range(1,21):
    
14.     for y in range(1,21):
    
15.         L[x][y] = L[x-1][y] + L[x][y-1]
    
16. print(L[20][20])

复制代码

zengtaozt

BngThea

1. 
   
2. def routes(n):
   
3.     s = [1]
   
4.     while n:
   
5.         for i in range(len(s)-1,0,-1):
   
6.             s[i] = s[i] + s[i-1]            
   
7.         s.append(1)
   
8.         n -= 1
   
9.    
   
10.     return sum(each**2 for each in s)
    
11. 
    
12. print(routes(20))
    
13. 
    

复制代码

由我们主宰

我下面的代码可以解决每一条路径怎么走，所以效率比较低，不适合用了求总数。但我觉得，能够求出每种具体路径，也是一种锻炼，分享给大家吧。至少我自己通过编写这个，递归的能力提升了不少。

1. #include<stdio.h>
   
2. #include<time.h>
   
3. #define ORDER 7
   
4. int n;
   
5. int next(int (*p1)[ORDER],int x,int y)
   
6. {
   
7.         int tag=0;
   
8.         int grid2[ORDER][ORDER];
   
9.         int i,j;
   
10.         for(i=0;i<ORDER;i++)
    
11.         {
    
12.                 for(j=0;j<ORDER;j++)
    
13.                 {
    
14.                         grid2[i][j]=p1[i][j];
    
15.                 }
    
16.         }
    
17.         while(tag<2)
    
18.         {
    
19.                 if(0==tag)
    
20.                 {
    
21.                         tag++;
    
22.                         if(x>=ORDER-1)
    
23.                         {
    
24.                                 nextright(grid2,x,y);
    
25.                                 return 0;
    
26.                         }
    
27.                         nextunder(grid2,x,y);
    
28.                 }
    
29.                 else if(1==tag)
    
30.                 {
    
31.                         tag++;
    
32.                         if(y>=ORDER-1)
    
33.                         {
    
34.                                 return 0;
    
35.                         }
    
36.                         nextright(grid2,x,y);
    
37.                         return 0;
    
38.                 }
    
39.         }
    
40. 
    
41. }
    
42. 
    
43. int nextright(int (*p2)[ORDER],int x,int y)
    
44. {
    
45.         int grid3[ORDER][ORDER];
    
46.         int i,j;
    
47.         for(i=0;i<ORDER;i++)
    
48.         {
    
49.                 for(j=0;j<ORDER;j++)
    
50.                 {
    
51.                         grid3[i][j]=p2[i][j];
    
52.                 }
    
53.         }
    
54.         if(1==grid3[ORDER-1][ORDER-1])
    
55.         {
    
56.                 n++;
    
57.                 printf("这是第%d种\n",n);
    
58.                 for(i=0;i<ORDER;i++)
    
59.                 {
    
60.                         for(j=0;j<ORDER;j++)
    
61.                         {
    
62.                                 printf("%d ",*(*(grid3+i)+j));                       
    
63.                         }
    
64.                         printf("\n");
    
65.                 }
    
66.                 return 0;
    
67.         }
    
68.         grid3[x][y+1]=1;
    
69.         next(grid3,x,y+1);
    
70.         return 0;
    
71. }
    
72. int nextunder(int (*p3)[ORDER],int x,int y)
    
73. {
    
74.         int grid4[ORDER][ORDER];
    
75.         int i,j;
    
76.         for(i=0;i<ORDER;i++)
    
77.         {
    
78.                 for(j=0;j<ORDER;j++)
    
79.                 {
    
80.                         grid4[i][j]=p3[i][j];
    
81.                 }
    
82.         }
    
83.         if(1==grid4[ORDER-1][ORDER-1])
    
84.         {
    
85.                 n++;
    
86.                 printf("这是第%d种\n",n);
    
87.                 for(i=0;i<ORDER;i++)
    
88.                 {
    
89.                         for(j=0;j<ORDER;j++)
    
90.                         {
    
91.                                 printf("%d ",*(*(grid4+i)+j));                       
    
92.                         }
    
93.                         printf("\n");
    
94.                 }
    
95.                 return 0;
    
96.         }
    
97.         grid4[x+1][y]=1;
    
98.         next(grid4,x+1,y);
    
99.         return 0;
    
100. }
     
101. 
     
102. 
     
103. 
     
104. void main()
     
105. {
     
106.         int grid[ORDER][ORDER];
     
107.         int i,j;
     
108.         clock_t start,end;
     
109.         start=clock();
     
110.         for(i=0;i<ORDER;i++)
     
111.         {
     
112.                 for(j=0;j<ORDER;j++)
     
113.                 {
     
114.                         grid[i][j]=0;
     
115.                 }
     
116.         }
     
117.         grid[0][0]=1;
     
118.         next(grid,0,0);
     
119.         end=clock();
     
120.         printf("一共用时%f秒\n",(double)(end-start)/CLK_TCK);
     
121. }

复制代码

zzzgod

1. #include <iostream>
   
2. 
   
3. unsigned long long C(int down,int up)
   
4. {
   
5.         unsigned long long dest1=1,dest2=1,dest=1;
   
6.         for(int i=1;i<=up;i++)
   
7.         {
   
8.                 dest1=down-i+1;
   
9.                 dest2=i;
   
10.                 dest*=dest1;
    
11.                 dest/=dest2;
    
12.         }
    
13.         return dest;
    
14. }
    
15. 
    
16. int main()
    
17. {
    
18.         int len;
    
19.         std::cout<<"请输入长度："<<std::endl;
    
20.         std::cin>>len;
    
21.         std::cout<<"总共有"<<C(2*len,len)<<"条路径。";
    
22. }

复制代码

塔利班

1. from math import *
   
2. a=factorial(40)//factorial(20)**2
   
3. print(a)

复制代码

从一共要走的40步里选出哪20步给横着走

gonorth

import math as m

def routine(n):
    return int (m.factorial(n*2)/(m.factorial(n) **2))

print (routine(20))
其实是排列组合问题，40个选择选20个。

a1351468657

1. #include <stdio.h>
   
2. #include <time.h>
   
3. 
   
4. #define LENGTH 20 //正方形边长
   
5. 
   
6. int MaxDiv(int, int);
   
7. int MaxDiv(int m, int n)
   
8. {
   
9.         int max, min, temp;
   
10.         max = m > n ? m : n;
    
11.         min = m < n ? m : n;
    
12.         while (max % min)
    
13.         {
    
14.                 temp = max % min;
    
15.                 max = min;
    
16.                 min = temp;
    
17.         }
    
18.         return min;
    
19. }
    
20. 
    
21. 
    
22. main()
    
23. {
    
24.         int i, j, div;
    
25.         long long int m = 1, n = 1, times;
    
26. 
    
27.         for (i = LENGTH, j = LENGTH + LENGTH; i > 0; i--, j--)//20 * 20的正方形要走C(20 + 20, 20)次
    
28.         {                                                     //C是排列组合里面的公式可以去百度一下
    
29.                 m *= j;                                           //由于数字太大,采用两个数都除以最大公约数
    
30.                 n *= i;                                           //的方式进行计算。
    
31.                 div = MaxDiv(m, n);
    
32.                 m /= div;
    
33.                 n /= div;
    
34.         }
    
35. 
    
36.         printf("20 * 20的正方形要走%lld次", m / n);
    
37. }

复制代码

若有错误或者能继续改善的地方，望大佬指导！