この記事では、「梯子問題」と呼ばれる非常に興味深い問題を理解します。
まず、この問題で何を達成したいかを理解しましょう。
ラダー問題を理解する
この問題では，2つの入力が与えられる．1つは段数で，もう1つは人が一度に歩ける最大段数である．
例えば，最大歩数＝3であるとする．人はある時間に1歩、2歩、3歩のいずれかを歩くことができる。
一度に1歩、2歩、3歩のいずれかを踏み、梯子の頂上に到達する方法をすべて数える必要がある。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def count_no_ways(n,k):
if(n<0):
return 0
# already on top
if(n==0):
return 1
if(n<3):
return n
ans = 0
for i in range(1,k+1):
ans+=count_no_ways(n-i,k)
return ans
n = int(input())
k = int(input())
print(count_no_ways(n,k))
|
梯子問題の解決策
さて、この問題は、通常のループ処理やif-else文を使って解くことができる。
しかし、より良い方法は、再帰的アプローチに従うことです。
もし、Recursionがどのように機能するのか知らないのであれば、以下のチュートリアルを読むことをお勧めします。
Recursionについてもっと読む。
この問題を解くために、最小の問題、すなわち、n = 1からn = nまでの問題を探すことになります。
その場合を下図に示す。
では、梯子問題のコード実装を見てみましょう。
Pythonによる梯子問題のコード実装
ここでは、k回の最大ステップの方法を計算します。
そのため、(n-1),(n-2),(n-3)と順に(n-k)まで計算することになる。
そして最後に、得られた値をすべて合計して、最終的な答えを返すことになります。
以下はその実装コードです。
結果は以下の通りです。
17
17
65536
梯子問題で使われた再帰の概念が理解でき、自分で同じように実装できるようになれば幸いです。
読んでくれてありがとうございます。
この記事もチェック：Pythonで再帰を使った0-1ナップザック問題の実装を解説する