1つの小さいカエル、1回に2つの階段を跳ぶことができて、1回に1つの階段を跳ぶことができて、もし彼が101本の階段を跳ぶならば、全部でいくつかの跳び方の方案がありますか?
2533 ワード
1つの小さいカエル、1回に2つの階段を跳ぶことができて、1回に1つの階段を跳ぶことができて、もし彼が101本の階段を跳ぶならば、全部でいくつかの跳び方の方案がありますか?
问题の说明は简単で、この问题を见た时、私はまず例を挙げて分析して、例えばn=1の时にいくつかの方案があって、n=2の时にいくつかの方案があります....
私达はまず1波を分析して、n=1の时、この时小さいカエルはただ1种の跳び方があって、それから阶段1を跳び上がって、それから终わります.もちろんこれは私达が総括をまとめることを助けることができなくて、それから私达は引き続き分析してn=2の时、この时、小さいカエルは阶段1を跳び上がることができて、阶段2を跳び上がって终わることができて、それから阶段1は、阶段2を跳び上がって终わることができて、私达は発见して、想像するだけではこの時、私たちは図形を借りて私たちを助ける必要があります.
下図は私が自分でペンで描いた図形で、このような时にやはりペンで紙の上で絵を書いて私达を助けることを提案します
魂画手!!!
例を挙げると、得られた結果からなる数、特にフィボナス数列のように、n=3から、各項目は前の2項の和に等しく、私たちの結論を検証するために、私たちはn=5を導く時、全部でいくつかの状況があり、明らかに私たちの結論が正しいことが分かった.これはフィボナスの数列を求める問題です.では、いいですね.この時、フィボナスの数列は何ですか.食べられますか.では、別の角度からこのテーマを分析します.
もし、カエルが今4番目の階段を飛び上がったとしたら、その階段を上がったのはどれですか.この質問に答えるには、カエルが一度に1つの階段を跳ぶか、2つの階段を跳ぶしかないという問題の紹介を見なければなりません.では、この答えは簡単です.もし彼が今4にいたら、その上の階段は3か2に違いありません.そして私たちは考えていますもし彼が今3番目の階段にいたら、その上の階段は2か1に違いない.
では、あなたは疑問に思うかもしれませんが、この彼の階段を知って何の役に立つのでしょうか.私はみんなに栗をあげて、みんなは知っています.1+1はいくらですか.もし私があなたに聞いているならば、1+1+1の結果は明らかで、私がみんなに教えなければならないのはこの等式の結果がどれだけなのかではありません.私はみんなに計算の過程を教えたいと思っています.私たちは1+1を計算した後、1+1を計算したら、私たちは1+1の結果を加えるだけでいいです.逆に、もしあなたが1+1+1を計算したいなら、私たちは1+1の結果を計算するだけでいいのではないでしょうか.
私たちのこのアルゴリズムに比べて、もしあなたがカエルが4番目の階段を飛び上がることを計算したいならば、私たちはカエルが3番目の種類を飛び上がることと2番目の階段を飛び上がる種類を計算するだけでまとめることができる数学の公式はf(n)=f(n-1)+f(n-2)です.
私たちはこのルートコードを実現して、とても簡単で、私たちはまず再帰でします.
function jump(n) {
if (n === 1 || n=== 2) {
return n
}
return jump(n - 1) + jump(n - 2)
}
コードは簡単ですが、n=101を計算したいという大きな問題があります.全然計算できません.ブラウザの実行時間が長すぎます.もちろん、待っていれば、ブラウザは計算できます.実はこのコードには大きな弊害があり、彼はずっと繰り返して計算して、仮に私たちはすでにf(4)を計算したとして、しかし私たちがf(5)を計算する時、この関数はまた新しいからf(4)を計算して、この構想によって私たちは最適化することができて、私たちは1つの配列を通じてf(n)を記録して、このように繰り返して計算しません.
function jump(n, memory = []) {
if (n === 1 || n=== 2) {
memory[n] = n
}
if (memory[n] !== undefined) {
return memory[n]
} else {
memory[n] = jump(n - 1, memory) + jump(n - 2, memory)
}
return memory[n]
}
改善されたコードは、「秒」で計算できますが、私たちの追求はここに止まらないので、コードを最適化してみましょう.このコードは再帰的に作られていますが、実際には再帰的に性能を消費しています.私たちは直接循環的にfunction jump(n){
let arr = [1, 2]
for (let i = 2; i< n; i++) {
arr [i] = arr[i - 1] + arr[i - 2]
}
return arr[n - 1]
}
最終的にループコードと最適化された再帰アルゴリズムによって実行された時間を比較し,n=1000のときの結果を計算した.
結果は明らかである.
最后にみんなに一言を分かち合います:大物は一日で练习したのではありません!!!がんばって、塩漬けの魚はいつも寝返りを打つ日があって、寝返りを打っても塩漬けの魚で、それは寝返りを打つ塩漬けの魚です!!!