60 lines
1.1 KiB
Ruby
60 lines
1.1 KiB
Ruby
descr=%{
|
||
Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.
|
||
|
||
1) 00 01 02 12 22
|
||
2) 00 01 11 12 22
|
||
3) 00 01 11 21 22
|
||
4) 00 10 11 12 22
|
||
5) 00 10 11 21 22
|
||
6) 00 10 20 21 22
|
||
|
||
How many routes are there through a 20×20 grid?
|
||
}
|
||
|
||
reflexion=%#
|
||
coordinates at time t are (x_t,y_t)
|
||
We have:
|
||
0 <= x_t <= n
|
||
0 <= y_t <= n
|
||
x_{t+1} + y_{t+1} = x_t + y_t + 1
|
||
x_{t+1} >= x_t
|
||
y_{t+1} >= y_t
|
||
|
||
In order to have a computable recursive content, we need to extend
|
||
this reasonment to rectangles nxm.
|
||
|
||
nb(0,n)=1
|
||
nb(n,0)=1
|
||
nb( 1,1 ) = nb(0,1) + nb(1,0)
|
||
|
||
nb(n,m)=nb(m,n)
|
||
#
|
||
|
||
number=20
|
||
$mem=[]
|
||
(0..number).each do |i|
|
||
$mem <<= []
|
||
(0..number).each do |j|
|
||
$mem[i] <<= 0
|
||
end
|
||
end
|
||
|
||
def nb(n,m)
|
||
if (m>n)
|
||
tmp=n
|
||
n=m
|
||
m=tmp
|
||
end
|
||
if $mem[n][m] != 0
|
||
return $mem[n][m]
|
||
end
|
||
if n==0 or m==0
|
||
$mem[n][m]=1
|
||
return 1
|
||
end
|
||
$mem[n][m] = nb(n-1,m) + nb(n,m-1)
|
||
return $mem[n][m]
|
||
end
|
||
|
||
puts nb(number,number)
|
||
p $mem
|