Return to Video

22-24 Faster Fibonacci Solution

  • 0:00 - 0:03
    反復してフィボナッチを定義する方法があります
  • 0:04 - 0:08
    計算しながら記録をつけて
    冗長的な計算は避けることにします
  • 0:08 - 0:10
    2つの変数があります
  • 0:10 - 0:14
    私はやや奇妙な方法で処理するつもりです
    その理由はすぐに明らかになります
  • 0:14 - 0:19
    nがゼロの時及びnが1の時も
    例外なく正しい答えを出せるようにしたいと思います
  • 0:19 - 0:23
    前の2つの記録をつける代わりに
  • 0:23 - 0:26
    現在の数字1つと
    そのあとの想像上の数字1つの記録をつけます
  • 0:26 - 0:31
    最初の2つのフィボナッチ数列は
    ゼロと1であることは分かっています
  • 0:31 - 0:34
    currentはゼロ
  • 0:34 - 0:37
    afterは1とします
  • 0:37 - 0:42
    その数字は私たちが今処理していて
    ループしている数字の次の数字です
  • 0:42 - 0:44
    ゼロからnの範囲の中でiから開始します
  • 0:44 - 0:48
    私たちはfibonacci(n)を求めています
  • 0:48 - 0:51
    つまりゼロから開始します
    currentの値はfibonacci(0)のための値であり
  • 0:51 - 0:55
    afterはfibonacci(1)のための値です
  • 0:55 - 0:57
    ループを行いながら
  • 0:57 - 1:02
    これらの値を更新していきます
    私たちは再帰的ルールに従うことで更新します
  • 1:02 - 1:06
    これはcurrentの新しい値は
    afterの最新の値であることを意味します
  • 1:06 - 1:09
    afterの新しい値はcurrent及びafterの2つの合計です
  • 1:09 - 1:12
    多重代入により行います
  • 1:12 - 1:16
    これによりテンポラリ変数を使う必要がなくなります
  • 1:16 - 1:20
    currentとafterの新しい数値を指定できます
  • 1:20 - 1:23
    currentの新しい数値はafterの最新の値であり
  • 1:23 - 1:29
    afterの新しい値はcurrentの値足すafterの値です
  • 1:29 - 1:32
    これにより多重代入が便利になります
  • 1:32 - 1:34
    もし多重代入を使用しないならば
    テンポラリ変数を使い
  • 1:34 - 1:36
    代入を利用しながらこれらの内の1つの記録をつけます
  • 1:36 - 1:40
    しかし多重代入によりまず両方の値を入手し
  • 1:40 - 1:43
    その後左辺の2つの変数に指定します
  • 1:43 - 1:44
    それだけです
  • 1:45 - 1:48
    ループのあとcurrentの値を返します
  • 1:48 - 1:54
    その値はfibonacci(n)を求める場合の現在の
    フィボナッチ数です
  • 1:54 - 1:55
    ではやってみましょう
  • 1:55 - 2:00
    fibonacci(0)を見ることができ
    その結果はゼロとなります
  • 2:00 - 2:03
    これが得られた値です
  • 2:03 - 2:04
    currentの値であるので幅がゼロからゼロの場合
  • 2:04 - 2:06
    ループすることは絶対ありません
  • 2:06 - 2:08
    値を得ることができました
  • 2:10 - 2:17
    fibonacci(1)を確認しましょう
    実行すると値1を得ます
  • 2:17 - 2:21
    これは私たちが想定しているものです
    そしてそれを得たのはループを一度行い
  • 2:21 - 2:25
    afterの値を指定したからです
    値は1から開始してcurrentに至り
  • 2:25 - 2:31
    それはcurrentの値としてreturnするものです
    続けてfibonacci(2)を試します
  • 2:31 - 2:36
    それもまた予測どおり1です
  • 2:36 - 2:40
    fibonacci(3)は1足す1
    つまり2であり同様に続きます
  • 2:43 - 2:46
    うまくいっているようですね
  • 2:46 - 2:49
    これまで簡単なものを試してきました
    次はfibonacci(33)を試してみましょう
  • 2:49 - 2:52
    前の小テストではfibonacci(36)を
    計算する推測を行いましたが
  • 2:52 - 2:56
    以前の再帰的定義を使用し
  • 2:56 - 3:01
    fibonacci(33)の呼び出しが必要でした
  • 3:01 - 3:02
    なぜコードを実行するために長くかかったのでしょう?
  • 3:02 - 3:07
    fibonacci(33)の値は何でしょうか?
  • 3:07 - 3:10
    それは350万回の呼び出しです
  • 3:10 - 3:13
    何十億の指示を1秒で処理する装置があったとしても
  • 3:13 - 3:16
    350万回の再帰呼び出しを処理することは
    実に大変なことです
  • 3:16 - 3:19
    呼び出しの度にたった1つではなく
    数千の命令を受けるのです
  • 3:19 - 3:22
    このため開始に時間がかかり
  • 3:22 - 3:25
    結果を見ることができませんでした
  • 3:25 - 3:30
    fibonacci(2)への
    fibonacci(33)の呼び出しだけでなく
  • 3:30 - 3:32
    fibonacci(36)を得るために
  • 3:32 - 3:35
    他にも行うべきことが多くあります
  • 3:35 - 3:40
    しかし今インターネット定義で高速のフィボナッチが
    存在し冗長的な作業を行わずに
  • 3:40 - 3:45
    fibonacci(36)の計算が行えるのです
    そのため私たちはこの値を求めることができます
  • 3:45 - 3:50
    フィボナッチモデルを使用して
    3年後には1,500万羽のウサギがいると示されます
  • 3:50 - 3:55
    60ヵ月の引数を渡し
    5年後にはどれほどの数になっているのか
  • 3:55 - 4:01
    計算してみましょう
  • 4:01 - 4:03
    この計算では非常に大きな数から始めます
  • 4:03 - 4:05
    これに関係して
  • 4:05 - 4:09
    ウサギの質量が地球の質量を超えて産まれるまでに
  • 4:09 - 4:13
    どれほど長い時間かかるのか見てみましょう
  • 4:13 - 4:23
    地球の質量は5.9722×10の24乗
  • 4:23 - 4:27
    単位はキログラムです
  • 4:27 - 4:30
    累乗を使うと
  • 4:30 - 4:36
    10の24乗となります 累乗表記すれば
  • 4:36 - 4:40
    5.9×10の24乗キログラムとなります
  • 4:40 - 4:44
    これは2の10乗で結果は1024です
  • 4:45 - 4:49
    2×2×2…と2を10回かけます
  • 4:49 - 4:52
    ここでは10を24回かけています
  • 4:52 - 4:55
    地球の質量を計算するよい方法です
  • 4:55 - 4:59
    ではウサギの質量が地球の質量を超えるまで
  • 4:59 - 5:01
    何ヵ月かかるのかループを行います
  • 5:01 - 5:03
    フィボナッチ数列からループを開始し
  • 5:04 - 5:08
    その数が地球の質量を超えるまで続けます
  • 5:08 - 5:12
    またウサギの質量を決める必要があります
  • 5:12 - 5:15
    ウサギは約2キログラムとします
  • 5:15 - 5:20
    ウサギの体重としては適切だと思われます
  • 5:20 - 5:23
    この推定はもちろん
  • 5:23 - 5:25
    昨今のよく肥えたウサギに基づきますが
  • 5:25 - 5:29
    フィボナッチモデルが示すほど
    早く繁殖することはありません
  • 5:29 - 5:32
    ではループを書き
  • 5:32 - 5:36
    いつウサギの質量が地球の質量を超えるのかを
    見てみましょう
  • 5:36 - 5:45
    n=1から開始しfibonacci(n)が
    地球の質量を超えるまで続けます
  • 5:45 - 5:52
    ではfibonacci(n)×ウサギの質量の
    計算を行います
  • 5:52 - 5:54
    fibonacci(n)は月末のウサギの数を表わし
  • 5:54 - 5:56
    それにウサギの体重を乗じます
  • 5:56 - 5:58
    その値が地球の質量より少ない限り
  • 5:58 - 6:01
    地球は人類にとって安全であり
  • 6:01 - 6:05
    少なくとも人類にスペースは残されています
  • 6:05 - 6:09
    またループを行う度にnを増加させます
  • 6:10 - 6:13
    ループの終りにはnの値を出力し
  • 6:13 - 6:16
    得た値を確認します
  • 6:16 - 6:18
    fibonacci(n)の値も出力し
  • 6:18 - 6:22
    それがどれほど大きいか見てみます
  • 6:22 - 6:29
    fibonacci(n)×ウサギの質量が
    地球の質量よりも小さい限りループを続けます
  • 6:29 - 6:31
    ループが終了すれば
  • 6:31 - 6:34
    地球の質量を超えたことを意味します
    その結果を見てみましょう
  • 6:34 - 6:39
    それでは実行して結果を得てみます
  • 6:39 - 6:40
    nの値は119です
  • 6:40 - 6:45
    ウサギの質量が地球の質量を超えるまで
    わずか119ヵ月であり10年未満です
  • 6:45 - 6:49
    これはその時点でのウサギの数です
  • 6:49 - 6:51
    すさまじい数です
  • 6:51 - 6:54
    ウサギに恐怖心を抱きませんか?
  • 6:54 - 6:58
    安心してください
    フィボナッチモデルは実際には不正確です
  • 6:58 - 6:59
    これはウサギの繁殖についての数学的概念です
  • 6:59 - 7:02
    実際にはウサギはある時点で死にます
  • 7:02 - 7:05
    またウサギの数が多すぎるとエサが不足します
  • 7:05 - 7:07
    ですからフィボナッチ数列のように増えることはなく
  • 7:07 - 7:11
    ウサギが地球を征服することはありません
  • 7:11 - 7:14
    もしフィボナッチのモデルが正しければ
    恐れるべきです
  • 7:14 - 7:18
    ウサギが地球を支配するまでわずか10年であり
  • 7:18 - 7:20
    地球そのものよりも重くなるのです
  • 7:20 - 7:25
    しかしうれしいことにこのモデルは
    ウサギの繁殖について正確なものではありません
  • 7:25 - 7:27
    ウサギは永久に生きるわけではなく
  • 7:27 - 7:28
    数が多くなればエサ不足になります
  • 7:28 - 7:31
    そこでウサギの繁殖も生存も止まります
タイトル:
22-24 Faster Fibonacci Solution
概説:

22-24 Faster Fibonacci Solution

more » « less
Video Language:
English
Team:
Udacity
プロジェクト:
CS101 - Intro to Computer Science
Duration:
07:32

Japanese subtitles

改訂