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
is considered checkmate. Note that a person cannot occupy a urinal next to an already occupied urinal.
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.
0 -> 1 (the null case counts as checkmate)
1 -> 1 (
2 -> 2 (
3 -> 2 (
4 -> 3 (
5 -> 4 (
6 -> 5 (
7 -> 7 (
8 -> 9 (
The smallest program in bytes wins.