题目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 的网格，这样的路有多少条？

翅膀团

#include <stdio.h>

int a(int x,int y)
{
    if(x==1)
    {
    return y;
    }
    if(y==1)
    {
    return 1;
    }
    return (a(x-1,y) + a(x,y-1));
}

int main(void)
{
    int i,l,f;
    printf("请输入所需的网格(如：2x2):");
    scanf("%dx%d",&i,&l);
    f = a(i,l);
    printf("共有%d条。\n",2*f);
}

如果有错误希望指出

huomqh

这题不会，先放着。

DAY

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

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

        public static BigInteger C(BigInteger N,BigInteger M){
                BigInteger n=N;
                BigInteger m=M;
                BigInteger tM=BigInteger.ONE;
                BigInteger tN=BigInteger.ONE;
                while(n!=BigInteger.ZERO){
                        tM=tM.multiply(m);
                        tN=tN.multiply(n);
                        m=m.subtract(BigInteger.ONE);
                        n=n.subtract(BigInteger.ONE);
                }
                return tM.divide(tN);
        }
        public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                BigInteger n=sc.nextBigInteger();
                BigInteger m=sc.nextBigInteger();
                System.out.println(C(n,m));
        }
}

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

飘飞的白杨

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

答案：137846528820

迷雾少年

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

QingXin

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

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

渡风

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

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

fc1735

这题不用编程

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

鱼油小白

c
#include <stdio.h>

#define size 21
int main()
{
    long a[size][size];
    int i,j;

    for(i = 0; i<size; i++)
                for(j = 0; j<size; j++)
                        a[i][j] = 0;

    for(i = 0; i<size; i++)
    {
        a[0][i] = 1;
        a[i][0] = 1;
    }
    for(i = 1; i<size; i++)
    {
        for(j = 1; j<size; j++)
        {
                        a[i][j] = a[i-1][j] + a[i][j-1];
        }
    }
    printf("%ld",a[size-1][size-1]);

    return 0;
}

FlySelf

import time
import math

def lattice_paths(number):
    '求从number*number的网格的左上角通往右下角有多少条路'
    return int(math.factorial(2 * number) / (math.factorial(number)) ** 2)


start = time.clock()
print(lattice_paths(20))
end = time.clock()
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

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

L =[]
for i in range(21):
    L.append([])
L[0].append(0)
for y in range(1,21):
    L[0].append(1)
for x in range(1,21):
    for y in range(21):
        L[x].append(0)
for x in range(1,21):
    L[x][0] = 1

for x in range(1,21):
    for y in range(1,21):
        L[x][y] = L[x-1][y] + L[x][y-1]
print(L[20][20])

zengtaozt

BngThea

def routes(n):
    s = [1]
    while n:
        for i in range(len(s)-1,0,-1):
            s[i] = s[i] + s[i-1]            
        s.append(1)
        n -= 1
    
    return sum(each**2 for each in s)

print(routes(20))

由我们主宰

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

#include<stdio.h>
#include<time.h>
#define ORDER 7
int n;
int next(int (*p1)[ORDER],int x,int y)
{
        int tag=0;
        int grid2[ORDER][ORDER];
        int i,j;
        for(i=0;i<ORDER;i++)
        {
                for(j=0;j<ORDER;j++)
                {
                        grid2[i][j]=p1[i][j];
                }
        }
        while(tag<2)
        {
                if(0==tag)
                {
                        tag++;
                        if(x>=ORDER-1)
                        {
                                nextright(grid2,x,y);
                                return 0;
                        }
                        nextunder(grid2,x,y);
                }
                else if(1==tag)
                {
                        tag++;
                        if(y>=ORDER-1)
                        {
                                return 0;
                        }
                        nextright(grid2,x,y);
                        return 0;
                }
        }

}

int nextright(int (*p2)[ORDER],int x,int y)
{
        int grid3[ORDER][ORDER];
        int i,j;
        for(i=0;i<ORDER;i++)
        {
                for(j=0;j<ORDER;j++)
                {
                        grid3[i][j]=p2[i][j];
                }
        }
        if(1==grid3[ORDER-1][ORDER-1])
        {
                n++;
                printf("这是第%d种\n",n);
                for(i=0;i<ORDER;i++)
                {
                        for(j=0;j<ORDER;j++)
                        {
                                printf("%d ",*(*(grid3+i)+j));                        
                        }
                        printf("\n");
                }
                return 0;
        }
        grid3[x][y+1]=1;
        next(grid3,x,y+1);
        return 0;
}
int nextunder(int (*p3)[ORDER],int x,int y)
{
        int grid4[ORDER][ORDER];
        int i,j;
        for(i=0;i<ORDER;i++)
        {
                for(j=0;j<ORDER;j++)
                {
                        grid4[i][j]=p3[i][j];
                }
        }
        if(1==grid4[ORDER-1][ORDER-1])
        {
                n++;
                printf("这是第%d种\n",n);
                for(i=0;i<ORDER;i++)
                {
                        for(j=0;j<ORDER;j++)
                        {
                                printf("%d ",*(*(grid4+i)+j));                        
                        }
                        printf("\n");
                }
                return 0;
        }
        grid4[x+1][y]=1;
        next(grid4,x+1,y);
        return 0;
}



void main()
{
        int grid[ORDER][ORDER];
        int i,j;
        clock_t start,end;
        start=clock();
        for(i=0;i<ORDER;i++)
        {
                for(j=0;j<ORDER;j++)
                {
                        grid[i][j]=0;
                }
        }
        grid[0][0]=1;
        next(grid,0,0);
        end=clock();
        printf("一共用时%f秒\n",(double)(end-start)/CLK_TCK);
}

zzzgod

#include <iostream>

unsigned long long C(int down,int up)
{
        unsigned long long dest1=1,dest2=1,dest=1;
        for(int i=1;i<=up;i++)
        {
                dest1=down-i+1;
                dest2=i;
                dest*=dest1;
                dest/=dest2;
        }
        return dest;
} 

int main()
{
        int len;
        std::cout<<"请输入长度："<<std::endl;
        std::cin>>len;
        std::cout<<"总共有"<<C(2*len,len)<<"条路径。"; 
}

塔利班

from math import *
a=factorial(40)//factorial(20)**2
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

#include <stdio.h>
#include <time.h>

#define LENGTH 20 //正方形边长

int MaxDiv(int, int);
int MaxDiv(int m, int n)
{
        int max, min, temp;
        max = m > n ? m : n;
        min = m < n ? m : n;
        while (max % min)
        {
                temp = max % min;
                max = min;
                min = temp;
        }
        return min;
}


main()
{
        int i, j, div;
        long long int m = 1, n = 1, times;

        for (i = LENGTH, j = LENGTH + LENGTH; i > 0; i--, j--)//20 * 20的正方形要走C(20 + 20, 20)次
        {                                                     //C是排列组合里面的公式可以去百度一下
                m *= j;                                           //由于数字太大,采用两个数都除以最大公约数
                n *= i;                                           //的方式进行计算。
                div = MaxDiv(m, n);
                m /= div;
                n /= div;
        }

        printf("20 * 20的正方形要走%lld次", m / n);
}

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