blob: 9eb1ffb432118a2413e6e811bf5476570d3ec6ea (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#!/usr/bin/perl -s
use v5.16;
use warnings;
use Math::Prime::Util 'lucasu';
die <<EOS unless @ARGV;
usage: $0 N
N
Count the different ways to climb a stair of N steps taking either
one ore two steps at a time.
EOS
# Are Abigail and Abigail the same person? See perlsecret.
<<m=~m>>
Let S(n) be the number of different ways to climb a stair of n steps
taking either one ore two steps at a time.
Let n > 2. The last move is either one step with S(n-1) ways to reach
the second last step or two steps with S(n-2) ways to reach the step
before it.
Thus S(n) = S(n-1) + S(n-2). Furthermore, the trivial cases S(1) = 1
and S(2) = 2 lead to S(n) = Fₙ₊₁, the (n+1)th Fibonacci number.
The Fibonacci sequence Fₙ is the particular Lucas sequence Uₙ(1, -1) as
provided by Math::Prime::Util.
See e.g. http://oeis.org/wiki/Lucas_sequences.
m
;
say lucasu 1, -1, 1 + shift;
|
