小练习：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
from functools import reduce
def c(n, k):
    if k==0 or k == n:
        return 1
    else:
        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)))
    
def numRoad(n):
    result = 0
    for k in range(1, n+1):
        result = result + c(n-1, k-1) * c(n+1, k)
    return result

# 方法2
def numroad(n):
    nnew = [0]
    for k in range(1, n+1):
        nlast = nnew
        nnew[0] = 1
        for i in range(1, k):
            nnew[i] = nnew[i-1] + nlast[i]
        nnew.append(2*nnew[k-1])
    return nnew[-1]

if __name__ == '__main__':
    n = 20
    print('Method1:' + str(n) + '*' + str(n) + '网格路径共有' + str(numRoad(n)) + '条')
    print('Method2:' + str(n) + '*' + str(n) + '网格路径共有' + str(numroad(n)) + '条')

holdme

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

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

答案是：

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

DingRan

严重支持

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

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

填坑~

import time

d = {}#储存单步运算的结果，避免重复计算

#迭代函数
def f(x,y):
    if (x,y) in d:
        return d[(x,y)]
    
    if x==0 and y!=0:
        d[(x,y)] = f(x,y-1)
        return f(x,y-1)

    if x!=0 and y==0:
        d[(x,y)] = f(x-1,y)
        return f(x-1,y)

    if x==0 and y==0:
        d[(x,y)] = 1
        return 1

    if x!=0 and y!=0:
        d[(x,y)] = f(x-1,y)+f(x,y-1)
        return f(x-1,y)+f(x,y-1)

m = 20

a = time.clock()
print('结果：%s' %f(m,m))
b = time.clock()

print('用时：%.3fs'%(b-a))

运行结果：

>>> 
结果：137846528820
用时：0.010s
>>> 

小火木

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

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

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

from time import time

n=int(input('Input a number:'))

start=time()

def jiecheng(m):
    num=1
    while m>1:
        num*=m
        m-=1
    return num

result=jiecheng(n*2)/jiecheng(n)/jiecheng(n)
print('result is :' + str(result))
print("Use time is :" + str(time()-start))

结果如图：

小剑剑

又是数学题。。

def fun(n=20,m=20):
    accu1=1
    if n>m:
        n,m=m,n
    i=n+m
    count=0
    while count<n:
        accu1*=i
        i-=1
        count+=1
    i=2
    accu2=1
    while i<=n:
        accu2*=i
        i+=1
    return accu1//accu2

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

老忘

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

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

#-*- coding: UTF-8 -*-
int_num=20    #设置网格数为20
dict_result={}    #定义一个空字典，存放坐标点为key及(0,0)点到该坐标的路径数

for x in range(0,int_num+1):    #从(0,0)坐标开始循环处理，计算从(0,0)到(x,y)的路径数
    for y in range(0,int_num+1):
        if x==0 or y==0:    #如果是（0,y)或(x,0)坐标的点，则将(0,0)到该坐标的路径数赋值为1(因为不允许往走），并存入字典
            dict_result[x,y]=1
        else:    #否则,将(0,0)到(x,y)坐标对应的路径数则赋值为(x,y)其相临两个坐标（x或y少1）的路径数之和，并存入字典
            dict_result[x,y]=dict_result[x,y-1]+dict_result[x-1,y]

print(dict_result[int_num,int_num])

cold2wind

# encoding = "utf - 8"
__author__ = 'MG'
def TrackSum(n):
    fenZi = 1
    fenMu = 1
    for i in range(n + 1,n + n + 1):
        fenZi *= i
        fenMu *= (i - n)

    return fenZi // fenMu

if __name__ == "__main__":
    print(TrackSum(20))

kmh

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

shichaoufo

n = int(input("请输入N×N网格数:"))
a = 1
b = 1

for i in range(2*n,2*n-n,-1):
    a = a * i
for i in range(n,1,-1):
    b = b * i

c = a / b

print("有%s条最短路径" % str(c))
    

lingtingliushen

from time import clock
ts=clock()
a=[[0 for i in range(20)] for i in range(20)]
for i in range(20):
    for j in range(20):
        if i==0:
            a[i][j]=j+2
        else:
            a[i][j]=1
            for m in range(j+1):
                a[i][j]+=a[i-1][m]
print('从20*20的网格的左上角通往右下角有%d条路' % a[19][19])
print(clock()-ts)

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

WylLy

#coding:utf-8
dt = {'00':0}
le = input('输入格数：')
for i in range(1,int(le)+1):
    dt[(0,i)]=1
    dt[(i,0)]=1
for i in range(0,int(le)):
    for j in range(0,int(le)):
        dt[(i+1,j+1)]=dt[(i,j+1)]+dt[(i+1,j)]

print(dt[(int(le),int(le))])

挥舞乾坤

def path(row, column):
    lst = [[1 for x in range(column+1)] for x in range(row+1)]
    for r in range(1,row+1):
        for c in range(1,column+1):
            lst[r][c] = lst[r-1][c] + lst[r][c-1]
    return lst.pop().pop()

print(path(20,20))

leozyre

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