You are given $n steps to climb

Write a script to find out the distinct ways to climb to the top. You are allowed to climb either 1 or 2 steps at a time.

`Input: $n = 3 Output: 3 Option 1: 1 step + 1 step + 1 step Option 2: 1 step + 2 steps Option 3: 2 steps + 1 step Input: $n = 4 Output: 5 Option 1: 1 step + 1 step + 1 step + 1 step Option 2: 1 step + 1 step + 2 steps Option 3: 2 steps + 1 step + 1 step Option 4: 1 step + 2 steps + 1 step Option 5: 2 steps + 2 steps`

If we can climb stairs one or two steps at a time, then the number of ways to climb a stair with \(N\) steps is the number of ways to climb a stair with \(N - 1\) steps (if we first climb one step), plus the number of ways to climb of stair with \(N - 2\) steps (if we first climb two steps).

Since there is just one way to climb a stair case with 0 or with 1 step, we have the following formula to climb a stair case with \(N\) steps:

\[ S (N) = \begin{cases} 1 & \text{if } N = 0 \\ 1 & \text{if } N = 1 \\ S (N - 1) + S (N - 2) & \text{if } N > 1 \end{cases} \]

But this means that \(S (N)\) is \(F (N + 1)\), where \(F\) is the Fibonacci Sequence. And we have a closed formula for this:

\[ F (N) = \frac{\varphi^N - \psi^N}{\sqrt{5}} \]

where

\[ \varphi = \frac{1 + \sqrt{5}}{2} \text{ and } \psi = \frac{1}{\varphi} \]

Since \(\psi < 1\), the component \(\psi^N\) goes to \(0\). Hence

\[ F (N) \approx \frac{\varphi^N}{\sqrt{5}} \]

In fact,

\[ F (N) = \left[ \frac{\varphi^N}{\sqrt{5}} \right] \]

where \([\text{expr}]\) rounds the expression to the nearest integer.

So, if we have a stair case with \(N\) steps, the answer we are looking for is:

\[ S (N) = \left[ \frac{\varphi^{N + 1}}{\sqrt{5}} \right] \]

For most languages, we use the formula above. In Bash and Befunge-93, we can only do integer arithmetic, so we use the recursive definition.

In the solutions below, the number of steps the stair case is in a variable
`n`

(or `$n`

):

```
my $SQRT5 = sqrt (5);
my $PHI = (1 + $SQRT5) / 2;
say int (1 / 2 + $PHI ** ($n + 1) / $SQRT5)
```

Find the full program on GitHub.

```
SQRT5 = sqrt (5)
PHI = (1 + SQRT5) / 2
print int (0.5 + PHI ^ (n + 1) / SQRT5)
```

Find the full program on GitHub.

```
# define SQRT5 (sqrt (5))
# define PHI ((1 + SQRT5) / 2)
printf ("%lld\n", (long long) floor (0.5 + pow (PHI, n + 1) / SQRT5));
```

Find the full program on GitHub.

```
import "fmt"
import "math"
var SQRT5 float64 = math . Sqrt (5)
var PHI float64 = (1 + SQRT5) / 2
r = math . Round (math . Pow (PHI, (n + 1)) / SQRT5)
r = math . Round (math . Pow (PHI, (n + 1)) / SQRT5)
```

Find the full program on GitHub.

```
final double SQRT5 = Math . sqrt (5);
final double PHI = (1 + SQRT5) / 2;
System . out . printf ("%d\n",
(int) Math . round (Math . pow (PHI, n + 1) / SQRT5));
```

Find the full program on GitHub.

```
local SQRT5 = math . sqrt (5)
local PHI = (1 + SQRT5) / 2
print (math . floor (0.5 + PHI ^ (n + 1) / SQRT5))
```

Find the full program on GitHub.

```
let SQRT5 = Math . sqrt (5)
let PHI = (1 + SQRT5) / 2
Math . round (Math . pow (PHI, n + 1) / SQRT5)
```

Find the full program on GitHub.

```
const
sqrt5 = sqrt (5);
phi = (1 + sqrt5) / 2;
writeln (round (power (phi, n + 1) / sqrt5));
```

Find the full program on GitHub.

```
SQRT5 = sqrt (5)
PHI = (1 + SQRT5) / 2
print (round (pow (PHI, n + 1) / SQRT5))
```

Find the full program on GitHub.

```
sqrt5 <- sqrt (5)
phi <- (1 + sqrt5) / 2
cat (round (phi ^ (n + 1) / sqrt5), "\n", sep = "")
```

Find the full program on GitHub.

```
SQRT5 = Math . sqrt 5
PHI = (1 + SQRT5) / 2
puts ((PHI ** (n + 1) / SQRT5) . round)
```

Find the full program on GitHub.

```
(define sqrt5 (sqrt 5))
(define phi (/ (+ 1 sqrt5) 2))
(format #t "~d\n" (inexact->exact (round (/ (expt phi (+ n 1)) sqrt5))))
```

Find the full program on GitHub.

Here we use a starndard recursive definition of the Fibonacci numbers. We're using a cache to speed things up:

```
declare -A cache
cache[0]=1
cache[1]=1
function fib () {
local n=$1
if [[ -z ${cache[$n]} ]]
then fib $((n - 1))
cache[$n]=$result
fib $((n - 2))
cache[$n]=$((cache[$n] + result))
fi
result=${cache[$n]}
}
```

Calling `fib`

and printing the results:

```
fib $n
echo $result
```

Find the full program on GitHub.

```
> & :1+!#@_ 111p112p > :!#v_ 12g:11g+12p11p :1- v
^ <
^ ,+55 .g11 <
```

The program above is an iterative formula to calculate the Fibonacci
numbers. We use the cells `(1, 1)`

and `(1, 2)`

to store the two
previous numbers in the sequence. These numbers are initialized to 1,
using the following fragment:

```
111p112p
```

On the stack we keep track how often we still need to iterate. If the
number on the stack is `0`

, we break out of the loop:

```
> :!#v_ v
^ <
<
```

Inside the loop, we set the second to last number to the last number, and the last number to the sum of the last and second to last number. And then we substract 1 from the number on the stack:

```
12g:11g+12p11p :1-
```

When we break out of the loop, we print the result:

```
,+55 .g11
```

This line is run left to right, and it fetches the number from
the cell `(1, 1)`

, which is printed (`.`

), followed by a newline
(`55+,`

).

Find the full program on GitHub.