小练习：20160516 从20*20的网格的左上角通往右下角有多少条路？

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题，并且你每做对一题，就可以下载到参考答案的pdf文件，看看你的实现方法与参考答案有什么不同，以利于迅速提高自己的水平。

                               
登录/注册后可看大图

好了言归正传，我们开始做小练习。




题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
题目比较简单，注重程序效率和创意。
答题在一周内完成，即5.23 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。


题目：

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

                               
登录/注册后可看大图

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

本题重要的是找出规律，大家可以先在纸上画画。

奖励：
对所有完成程序并得出正确答案的将给予加分奖励，优秀的将额外加分。
在完成一批题目后，将根据每期的完成情况总评评出最佳，会有神秘大奖。

caobynk

1. 
   
2. # 方法1
   
3. from functools import reduce
   
4. def c(n, k):
   
5.     if k==0 or k == n:
   
6.         return 1
   
7.     else:
   
8.         return reduce(lambda x,y: x*y, list(range(k+1, n+1)))/reduce(lambda x,y: x*y, list(range(1, n-k+1)))
   
9.    
   
10. def numRoad(n):
    
11.     result = 0
    
12.     for k in range(1, n+1):
    
13.         result = result + c(n-1, k-1) * c(n+1, k)
    
14.     return result
    
15. 
    
16. # 方法2
    
17. def numroad(n):
    
18.     nnew = [0]
    
19.     for k in range(1, n+1):
    
20.         nlast = nnew
    
21.         nnew[0] = 1
    
22.         for i in range(1, k):
    
23.             nnew[i] = nnew[i-1] + nlast[i]
    
24.         nnew.append(2*nnew[k-1])
    
25.     return nnew[-1]
    
26. 
    
27. if __name__ == '__main__':
    
28.     n = 20
    
29.     print('Method1:' + str(n) + '*' + str(n) + '网格路径共有' + str(numRoad(n)) + '条')
    
30.     print('Method2:' + str(n) + '*' + str(n) + '网格路径共有' + str(numroad(n)) + '条')
    
31. 
    
32. 
    

复制代码

holdme

用组合数学求解很方便：
横竖总共要走40步，其中横20步，竖20步，其实就是C40取20
这样的话，一行就能解决计算部分了

1. import math
   
2. import time
   
3. start = time.clock()
   
4. print('从20*20的网格的左上角通往右下角有%s条路'%str(int(math.factorial(20)/math.factorial(10)/math.factorial(10))))
   
5. print('用时%s秒'%str(time.clock()-start))

复制代码

答案是：

1. 从20*20的网格的左上角通往右下角有137846528820条路
   
2. 用时3.0443930882029235e-05秒

复制代码

DingRan

严重支持

首先，
用排列组合即可解决：
即：20个“向右”和20个“向下”共有几种排法？
C(40,20)=40!/20!/20!=137846528820

但毕竟是一道编程题～先占坑～

填坑~

1. import time
   
2. 
   
3. d = {}#储存单步运算的结果，避免重复计算
   
4. 
   
5. #迭代函数
   
6. def f(x,y):
   
7.     if (x,y) in d:
   
8.         return d[(x,y)]
   
9.    
   
10.     if x==0 and y!=0:
    
11.         d[(x,y)] = f(x,y-1)
    
12.         return f(x,y-1)
    
13. 
    
14.     if x!=0 and y==0:
    
15.         d[(x,y)] = f(x-1,y)
    
16.         return f(x-1,y)
    
17. 
    
18.     if x==0 and y==0:
    
19.         d[(x,y)] = 1
    
20.         return 1
    
21. 
    
22.     if x!=0 and y!=0:
    
23.         d[(x,y)] = f(x-1,y)+f(x,y-1)
    
24.         return f(x-1,y)+f(x,y-1)
    
25. 
    
26. m = 20
    
27. 
    
28. a = time.clock()
    
29. print('结果：%s' %f(m,m))
    
30. b = time.clock()
    
31. 
    
32. print('用时：%.3fs'%(b-a))

复制代码

运行结果：

1. >>>
   
2. 结果：137846528820
   
3. 用时：0.010s
   
4. >>>

复制代码

小火木

1. def fun1(m,n):
   
2.     lis3=[1 for x in range(1,n+1)]
   
3.     for i in range(m):
   
4.         lis4=[]
   
5.         for j in range(n):
   
6.             lis4.append(sum(lis3[:j+1])+1)
   
7.         lis3=lis4[:]
   
8.     print('对于%dx%d的网格，这样的路有%d条' %(m,n,lis3.pop()))
   
9. 
   
10. fun1(20,20)

复制代码

bacon6581

其实这道题就是排列组合的问题。
20x20的格子，从左上角走至右下角
不管哪种走法，横着要走20格，竖着要走20格。一共要走40格
-------------------------
那么我们就在要走的40格里，排列出横着走20格的所有组合（横的20格确定了，剩下的20格就是竖的）
根据排列组合公式：

计算如下：

---------------------------
补充下：公式写成这样更好理解点
C40取20 * C20取20（在40格里取20格，放横着的；剩下的20格里取20格放竖着的）
因为C20取20等于1
又化简成上图的公式了
---------------------------

可能不好理解，解释下：

横着走用‘-’，竖着走用‘|’
那么上图的六种组合：
--||          -|-|             -||-
|--|          |-|-             ||--

每个图横着走两步，竖着走两步。共走4步
C4取2 = 4！/（2！（4-2）！）=4*3*2/2/2=6

------------------------------------------------
按要求写点代码吧

1. from time import time
   
2. 
   
3. n=int(input('Input a number:'))
   
4. 
   
5. start=time()
   
6. 
   
7. def jiecheng(m):
   
8.     num=1
   
9.     while m>1:
   
10.         num*=m
    
11.         m-=1
    
12.     return num
    
13. 
    
14. result=jiecheng(n*2)/jiecheng(n)/jiecheng(n)
    
15. print('result is :' + str(result))
    
16. print("Use time is :" + str(time()-start))
    

复制代码

结果如图：

小剑剑

又是数学题。。

1. def fun(n=20,m=20):
   
2.     accu1=1
   
3.     if n>m:
   
4.         n,m=m,n
   
5.     i=n+m
   
6.     count=0
   
7.     while count<n:
   
8.         accu1*=i
   
9.         i-=1
   
10.         count+=1
    
11.     i=2
    
12.     accu2=1
    
13.     while i<=n:
    
14.         accu2*=i
    
15.         i+=1
    
16.     return accu1//accu2
    

复制代码

这个答案就是我们高中时学的C40(下标)20(上标)

老忘

如果楼主不给个找规律的提示，可能我解不出来这道题，呵呵！说实话，找规律所花的时间比编代码的时间要多得多啊！

在解法中我假定方格的左上角坐标为(0,0)，则20个方格，最右下角的坐标为(20,20)

1. #-*- coding: UTF-8 -*-
   
2. int_num=20    #设置网格数为20
   
3. dict_result={}    #定义一个空字典，存放坐标点为key及(0,0)点到该坐标的路径数
   
4. 
   
5. for x in range(0,int_num+1):    #从(0,0)坐标开始循环处理，计算从(0,0)到(x,y)的路径数
   
6.     for y in range(0,int_num+1):
   
7.         if x==0 or y==0:    #如果是（0,y)或(x,0)坐标的点，则将(0,0)到该坐标的路径数赋值为1(因为不允许往走），并存入字典
   
8.             dict_result[x,y]=1
   
9.         else:    #否则,将(0,0)到(x,y)坐标对应的路径数则赋值为(x,y)其相临两个坐标（x或y少1）的路径数之和，并存入字典
   
10.             dict_result[x,y]=dict_result[x,y-1]+dict_result[x-1,y]
    
11. 
    
12. print(dict_result[int_num,int_num])

复制代码

cold2wind

1. # encoding = "utf - 8"
   
2. __author__ = 'MG'
   
3. def TrackSum(n):
   
4.     fenZi = 1
   
5.     fenMu = 1
   
6.     for i in range(n + 1,n + n + 1):
   
7.         fenZi *= i
   
8.         fenMu *= (i - n)
   
9. 
   
10.     return fenZi // fenMu
    
11. 
    
12. if __name__ == "__main__":
    
13.     print(TrackSum(20))

复制代码

kmh

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

复制代码

shichaoufo

1. n = int(input("请输入N×N网格数:"))
   
2. a = 1
   
3. b = 1
   
4. 
   
5. for i in range(2*n,2*n-n,-1):
   
6.     a = a * i
   
7. for i in range(n,1,-1):
   
8.     b = b * i
   
9. 
   
10. c = a / b
    
11. 
    
12. print("有%s条最短路径" % str(c))
    
13.    

复制代码

lingtingliushen

1. from time import clock
   
2. ts=clock()
   
3. a=[[0 for i in range(20)] for i in range(20)]
   
4. for i in range(20):
   
5.     for j in range(20):
   
6.         if i==0:
   
7.             a[i][j]=j+2
   
8.         else:
   
9.             a[i][j]=1
   
10.             for m in range(j+1):
    
11.                 a[i][j]+=a[i-1][m]
    
12. print('从20*20的网格的左上角通往右下角有%d条路' % a[19][19])
    
13. print(clock()-ts)

复制代码

1. 从20*20的网格的左上角通往右下角有137846528820条路
   
2. 0.002599226197788156
   

复制代码

WylLy

1. #coding:utf-8
   
2. dt = {'00':0}
   
3. le = input('输入格数：')
   
4. for i in range(1,int(le)+1):
   
5.     dt[(0,i)]=1
   
6.     dt[(i,0)]=1
   
7. for i in range(0,int(le)):
   
8.     for j in range(0,int(le)):
   
9.         dt[(i+1,j+1)]=dt[(i,j+1)]+dt[(i+1,j)]
   
10. 
    
11. print(dt[(int(le),int(le))])

复制代码

挥舞乾坤

1. def path(row, column):
   
2.     lst = [[1 for x in range(column+1)] for x in range(row+1)]
   
3.     for r in range(1,row+1):
   
4.         for c in range(1,column+1):
   
5.             lst[r][c] = lst[r-1][c] + lst[r][c-1]
   
6.     return lst.pop().pop()
   
7. 
   
8. print(path(20,20))

复制代码

leozyre

一开始是想把起点和终点设定为x,y都为20的点，然后每一次横向和纵向移动就分别减1，然后按照这个思路看了一下，发现。。其实路径数就是等于除了起点和终点以外点的个数。。也就是21*21-2。。。