Problem 15</h2>
19 April 2002</div>
Starting in the top left corner of a 2
2 grid, there are 6 routes (without backtracking) to the bottom right corner.</p>
</div>
How many routes are there through a 2020 grid?</p>
</p>
1. 初看起来似乎没什么感觉，但总结下，只是每个路径都必须有40条线，且有20条竖线和20条横线。</p>
组合数学告诉我们 answer：C(40,20)
</p>
2. 递归调用，若每个节点，用坐标表示的话，routes(m,n)表示(0,0)到（m,n)的路线数，注意到routes(m,n)包括了经过， (m-1,n-1), (m,n-2),(m-2,n)的三种路径，而他们却不会重合。这就直接找出了 routes(m,n)的递推关系式，所以：</p>
[code]
</p>
#include
long long int routes(int m,int n)
{
if(m==1)
return n+1;
else if(n==1)
return m+1;
else if(m==0||n==0)
return 1;
else
return 2*routes(m-1,n-1)+routes(m,n-2)+routes(m-2,n);
}
int main()
{
long long int count=0;
count=routes(20,20);
printf("%lldn",count);
return 0;
}</p>
[/code]</p>
用了 1.597274065017700195312500000000s才跑出结果，不过很方便理解。</p>
3.还好，有projecteuler优秀前辈的算法，现在列上几个好的C/C++ code：</p>
</p>
</p>
Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.</p>
</div>
How many routes are there through a 2020 grid?</p>
</p>
1. 初看起来似乎没什么感觉，但总结下，只是每个路径都必须有40条线，且有20条竖线和20条横线。</p>
组合数学告诉我们 answer：C(40,20)
</p>
2. 递归调用，若每个节点，用坐标表示的话，routes(m,n)表示(0,0)到（m,n)的路线数，注意到routes(m,n)包括了经过， (m-1,n-1), (m,n-2),(m-2,n)的三种路径，而他们却不会重合。这就直接找出了 routes(m,n)的递推关系式，所以：</p>
[code]
</p>
#include [/code]</p>
用了 1.597274065017700195312500000000s才跑出结果，不过很方便理解。</p>
3.还好，有projecteuler优秀前辈的算法，现在列上几个好的C/C++ code：</p>
long long int routes(int m,int n)
{
if(m==1)
return n+1;
else if(n==1)
return m+1;
else if(m==0||n==0)
return 1;
else
return 2*routes(m-1,n-1)+routes(m,n-2)+routes(m-2,n);
}
int main()
{
long long int count=0;
count=routes(20,20);
printf("%lldn",count);
return 0;
}</p>
</p>
</p>
</td>
0</a></div></td></tr>
</td>