题目15：从20*20的网格的左上角通往右下角有多少条路？
本帖最后由 欧拉计划 于 2015-4-21 16:33 编辑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 的网格，这样的路有多少条？
本帖最后由 翅膀团 于 2015-11-16 14:15 编辑
#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);
}
如果有错误希望指出 这题不会，先放着。 这道题最重要的就是分析一下，，无论怎样走都要横着走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));
}
}
特别说明:这道题涉及到大数乘法。。。
本帖最后由 飘飞的白杨 于 2016-9-25 13:03 编辑
#杨辉三角
l =
a = 20
while a:
for i in range(len(l)-1,0,-1):
l = l + l
l.append(1)
a -= 1
print(sum(i**2 for i in l))
答案：137846528820 这个就是有公式规律的吧。。 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
这题不用编程
37*31*29*23*13*11*7*5*3^2*2^2 c
#include <stdio.h>
#define size 21
int main()
{
long a;
int i,j;
for(i = 0; i<size; i++)
for(j = 0; j<size; j++)
a = 0;
for(i = 0; i<size; i++)
{
a = 1;
a = 1;
}
for(i = 1; i<size; i++)
{
for(j = 1; j<size; j++)
{
a = a + a;
}
}
printf("%ld",a);
return 0;
}
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。 QingXin 发表于 2016-9-16 00:11
40步中取出20步横着走，剩下的20步全都竖着走，C40（上标）20（下标） = 40！/(20! * 20!)。
正解！ 除了排列组合的数学算法
另一种解题思路是百度的：
011 1 1
123 4 5
1361015
14 10 20 35
15 15 35 70
每个数代表走到此处的走法，是它上方和左边的两个数之和。
L =[]
for i in range(21):
L.append([])
L.append(0)
for y in range(1,21):
L.append(1)
for x in range(1,21):
for y in range(21):
L.append(0)
for x in range(1,21):
L = 1
for x in range(1,21):
for y in range(1,21):
L = L + L
print(L) {:10_249:}
def routes(n):
s =
while n:
for i in range(len(s)-1,0,-1):
s = s + s
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),int x,int y)
{
int tag=0;
int grid2;
int i,j;
for(i=0;i<ORDER;i++)
{
for(j=0;j<ORDER;j++)
{
grid2=p1;
}
}
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),int x,int y)
{
int grid3;
int i,j;
for(i=0;i<ORDER;i++)
{
for(j=0;j<ORDER;j++)
{
grid3=p2;
}
}
if(1==grid3)
{
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=1;
next(grid3,x,y+1);
return 0;
}
int nextunder(int (*p3),int x,int y)
{
int grid4;
int i,j;
for(i=0;i<ORDER;i++)
{
for(j=0;j<ORDER;j++)
{
grid4=p3;
}
}
if(1==grid4)
{
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=1;
next(grid4,x+1,y);
return 0;
}
void main()
{
int grid;
int i,j;
clock_t start,end;
start=clock();
for(i=0;i<ORDER;i++)
{
for(j=0;j<ORDER;j++)
{
grid=0;
}
}
grid=1;
next(grid,0,0);
end=clock();
printf("一共用时%f秒\n",(double)(end-start)/CLK_TCK);
} #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步给横着走 import math as m
def routine(n):
return int (m.factorial(n*2)/(m.factorial(n) **2))
print (routine(20))
其实是排列组合问题，40个选择选20个。 #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);
}
若有错误或者能继续改善的地方，望大佬指导！
页:
[1]
2