Geek Answers Handbook

How many ways can you draw a 3xn rectangle with a 2x1 domino?

Every day I struggle with algorithmic questions and try to ask here what I cannot answer. Sorry if I cause a headache. Anyway,

Here is a problem from the Waterloo University ACM Programming Contest.

How many ways can you draw a 3xn rectangle with a 2x1 domino?

Nirvana: smells like a recursive spirit

+5
source share
3 answers

You can solve this problem with dynamic programming. Check this one out for a possible solution.

+4
source

Just an explicit solution to the equations given implicitly in the problem:

enter image description here

Or

f[n]=((1 + (-1)^n)*((2 - Sqrt[3])^(n/2)*(-1 + Sqrt[3]) + 
     (1 + Sqrt[3])* (2 + Sqrt[3])^(n/2)))/(4*Sqrt[3])

if someone cares.

10 ( n ) {n, f [n]}:

{6, 41.},   
{12, 2131.},   
{18, 110771.},   
{24, 5.75796*10^6},   
{30, 2.99303*10^8},   
{36, 1.5558*10^10}, 
{42, 8.08717*10^11},  
{48, 4.20377*10^13}, 
{54, 2.18515*10^15}, 
{60, 1.13586*10^17}
+9

, , , , n - . , ,

( )

, belisarius

+2

More articles:


All Articles