My Precalc teacher has one of his favorite problems that he made up (or more likely stole inspired by xkcd) that involves a row of n
urinals. "Checkmate" is a situation in which every urinal is already occupied OR has an occupied urinal next to them. For instance, if a person is an X
, then
X-X--X
is considered checkmate. Note that a person cannot occupy a urinal next to an already occupied urinal.
Task
Your program will take a number through stdin
, command line args, or a function argument. Your program will then print out or return the number of ways that checkmate can occur in with the inputted number of urinals.
Examples
0 -> 1
(the null case counts as checkmate)
1 -> 1
(X
)
2 -> 2
(X-
or -X
)
3 -> 2
(X-X
or -X-
)
4 -> 3
(X-X-
, -X-X
, or X--X
)
5 -> 4
(X-X-X
, X--X-
, -X-X-
, or -X--X
)
6 -> 5
(X-X-X-
, X--X-X
, X-X--X
, -X--X-
or -X-X-X
)
7 -> 7
(X-X-X-X
, X--X-X-
, -X-X--X
, -X--X-X
, X-X--X-
, X--X--X
or -X-X-X-
)
8 -> 9
(-X--X--X
, -X--X-X-
, -X-X--X-
, -X-X-X-X
, X--X--X-
, X--X-X-X
, X-X--X-X
, X-X-X--X
, X-X-X-X-
)
...
Scoring
The smallest program in bytes wins.
''
. This is the same as with factorial and permutations, 0! = 1, because there is exactly 1 way to arrange 0 items. \$\endgroup\$