あなたは階段を登ります。 各ステップで、1ステップまたは2ステップのいずれかを登ることができます。合計で、階段にはnステップがあります。 階段の終わりに到達する方法はいくつありますか？
このタスクはそれほど難しくありませんが、ソリューションの最小の複雑さに関していくつかの興味深い点があり、「知っておくと面白いこと」を示します。
明らかに、いずれにせよ、決定は、各ステップで2つのアクションを選択できるという観察から始まります。1つのステップを取るか2つのステップを取るかです。 前者の場合、階段は1ステップ、2番目の階段-2ずつ減少します。 階段を回避するための可能な方法の総数は、1つのステップから開始する場合はこれを行う方法の数の合計であり、2つから開始する場合は方法の数の合計です。 その結果、ソリューションは繰り返し式になります。
F（n）= F（n-1）+ F（n-2）
このアルゴリズムの「正面」アルゴリズムの再帰的または反復的な実装は、比率自体よりも少し長く見えます（オーバーフローの問題は括弧の外に残します）。
int f(int n) { if (n == 0 || n == 1) return 1; return f(n-1) + f(n-2); }
それ自体、このソリューションは正しいですが、その有効性は低く、アルゴリズムは指数関数的です。 動的プログラミング- メモ化の標準的な手法を使用することにより、複雑さを軽減できます。 直感的な説明：階段の各具体的なステップから、最後に到達する方法の数はこのステップに到達した方法に依存しないため、次の計算ステップで答えを覚えて使用するのが理にかなっています。 私はコードを提供しません-主なことは、反復とともに線形解が得られることです。 ただし、これだけではありません。
注意深い読者は、上記の比率がnを1ずつ補正したフィボナッチ数の式にすぎないことに気付くでしょう（初期条件が異なるため補正が表示されます-Fib（0）= 0、Fib（1）= 1、Fib（2）= 1 、私たちの場合、階段F（0）= 1、F（1）= 1、F（2）= 2）。 フィボナッチ数については、次の関係が成り立つことが知られています。
したがって、このべき乗の後、結果のマトリックスには、最初の行の最初の列に関心のある「n + 1」フィボナッチ数が含まれます（マトリックス要素は、通常1からインデックス付けされます）。
この事実自体はすでに興味深いものですが、急速累乗法のアルゴリズムとの組み合わせでは特に興味深いものです。 問題に適用すると、これは、O（ln N）乗算の答えが得られることを意味します。 Pythonでのこのソリューションのコード（もう一度、今のところオーバーフローの問題を忘れます-必要に応じてPythonは自動的に大きな整数の使用に切り替わります）は次のようになります。
#!/usr/bin/env python # You are climbing a stair case. Each time you can either make 1 step or 2 # steps. The staircase has n steps. In how many distinct ways can you climb the # staircase? def mul(a, b): return ((a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]), (a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1])) def pow(a, N): """Fast matrix exponentiation""" assert N >= 1 if N == 1: return a x = pow(a, N / 2) ret = mul(x, x) if N % 2: ret = mul(ret, a) return ret def num_stair_ways(N): x = pow(((1, 1), (1, 0)), N) return x[0][0] for i in range(1, 1001): print i, num_stair_ways(i)
実際には、それだけです。 私と同じように、読者が問題453973694165307953197296969696910619233826の条件に従ってさまざまな方法で200段の階段を歩くことができることを喜ばしく思います。
更新：コメントを読んだ結果、私は急いでコメントを2つ作成しました。
- 最近、非常によく似たトピックに関する記事がすでにありました。 この記事には、多くの賢明なコメントがあります。 公開時に類似の記事を自動検索できると便利です。
- O（ln N）操作の指数関数的に増加するシーケンスのN番目の項を計算するためのアルゴリズムに関するすべての議論は、線形に増加する数のビット深度を考慮する必要があります。 つまり、乗算の数はO（ln N）として増加する可能性がありますが、個々の乗算の複雑さはNから線形に増加します。したがって、合計の複雑さは、あるモジュールで最終値を見つけるだけで十分な場合にのみ対数のままになります。