黄金比率とフィボナッチ数列 part2 | 数学アラカルト [実践] | 逆ポーランド電卓の実践ウェブ rpn hacks!

逆ポーランド電卓の実践ウェブ rpn hacks!

逆ポーランド電卓rpnの実践ウェブ   
rpn hacks! アールピーエヌ・ハックスサイトマップ

rpn | 実戦 | 数学アラカルト | 数学に関する話題をrpnで探求!数字と遊んでみよう。

HOME > 実践 > 数学アラカルト > 黄金比率とフィボナッチ数列 part2 hatena yahoo buzzurl livedoor del.icio.us nifty newsing twitter facebook rss ソーシャルブックマーク

黄金比率とフィボナッチ数列 part2

前のページに戻るLinkIcon

フィボナッチと黄金比率

 さて、このフィボナッチ数列は、応用コーナーウサギとフィボナッチで取り上げましたが、フィボナッチ数列の数字と数字の比率を計算すると面白いことが分かります。まずはフィボナッチ数列を生成してみましょう。

  >rpn @a @b + #c @c @b #a @c #b -b 0 #a 1 #b @b -r 10 | rpn 1 -c fold
  1 1 2 3 5 8 13 21 34 55 89


このフィボナッチ数列の隣り合う数字を除算してみます。

  1÷1=1
  2÷1=2
  3÷2=1.5
  5÷3=1.66667
  8÷5=1.6
  13÷8=1.625
    :


何だかある数字に近づいているようです。面倒なのでrpnで計算させてみましょう。

  >rpn @b @a / @a @b + #c @b #a @c #b -b 1 #a 1 #b -r 10
  1
  2
  1.5
  1.66667
  1.6
  1.625
  1.61538
  1.61905
  1.61765
  1.61818


やはり、どこかで見た数字じゃありませんか?そうです。黄金比率にそっくりですね。それでは、計算した結果がどのように収束していくのかグラフで確かめて見ましょう。

  >rpn @b @a / @a @b + #c @b #a @c #b -b 1 #a 1 #b -r 10 >tmp
  >rpn 1 -c rownum <tmp | xyp -x,10 -y1.5,1.7 -s1,.1 -m | npd
  ^y 1.7
  |
  |              *
  |
  |
  |                      *
  |・・・・・・・・・・・・・・・・・・・・・・・・・・*・・・*・・・*・・・* 黄金比率(τ) 
  - 1.6              *
  |
  |
  |
  |
  |
  |                                      x
  |                                     10
  +1.5---|---*---|---|---|---|---|---|--->


急速に黄金比率に近づいているのが分かります。最終的にどのような値になるのか、20項目まで繰り返し計算してみましょう。

  >rpn @b @a / @a @b + #c @b #a @c #b -b 1 #a 1 #b -r 20
  1
  2
  1.5
  1.66667
  1.6
  1.625
  1.61538
  1.61905
  1.61765
  1.61818
  1.61798
  1.61806
  1.61803
  1.61804
  1.61803
  1.61803
  1.61803
  1.61803
  1.61803
  1.61803


大体15項目くらいで、黄金比率の1.61803に収束しているようです。フィボナッチと黄金比率は一見関係がなさそうに思えますが、互いに関連しあっていたのですね。

黄金比率は美しいという感覚を与えてくれるだけではありません。植物が葉を出す方向も黄金比率に従っています。植物にとっては光合成は死活問題ですから、葉の出す方向は大切です。円周を1対1.618に分割した部分から葉を出すのが最も葉が重ならずに日光を多く受けることができるのだそうです。そして、植物が生長して幹を伸ばし葉を広げていきます。上からその植物を見ると、葉の位置は螺旋構造になっているというから驚きです。

黄金比率を使った探索

 最後に現実的な話です。黄金比率は様々な業種で応用されているようで、面白いものに水道管の水漏れ調査があるそうです。A地点からB地点まで延びている水道管のどこかに水漏れがあるとします。その場所を探し当てるにはどのようにして探すのが一番効率的かを考えます。

  ===============☆=============================
  A         どこかで水漏れ                     B


AからBまで順に調べていくのは最も効率が悪く、たまたま水漏れ箇所がAに近ければいいですが、逆にBに近いと一番遅く発見することになります。通常、このような場合にはバイナリーサーチ(2分探索法)が使われます。

AとBの真ん中をCと決めて、均等分割した左右のどちらに水漏れがあるかを探知します。左にあることが分かれば、次はAとCとの真ん中をDと決めて再度、左右をチェックします。これを水漏れ箇所が見つかるまで繰り返します。AからBまで100箇所調べるポイントがあるとすれば、最悪でも7回で水漏れ箇所が発見できます。

この手の探索では2分法が一番ベストなはずですが、AとBの分割地点を真ん中ではなく黄金比率に準じた区分けにすればより早く発見できるという話があります。

本来、黄金分割による探索法は単峰性のある関数の極大・極小値を探し出す方法なのですが、このようなケースにも効果はあるのでしょうか。シミュレーションしてみましょう。まずは均等分割による2分探索法です。

探索法の違いをシミュレーション

 シミュレーション方法ですが、まず1から100までの数列を用意します。次に無作為に1から100までの数字を選んでから、2分探索で数字を何回で見つけられたかを記録します。100回シミュレーションして平均発見回数を計算することにします。最悪値は7回ですから、7回以下になるはずです。

ここで、binaryというrpnプログラムを用意します。binaryプログラムは与えられた昇順の数列から特定の数値を2分探索します。出力は以下のように探知した位置と探索回数になります。

  >rpn 100 -c seq' | rpn 1 100 100 ? -c binary
  3 7


上の例では、7回の探索で左から3番目の位置に発見したことを示しています。このプログラムを使って以下のように100回コマンド入力することで、ファイルのcount.binに100回分の探索結果が格納されます。

  >rpn -c null >count.bin
  >rpn 100 -c seq' | rpn 1 100 100 ? -c binary >>count.bin
                               :
                             (中略)
                               :
  >rpn 100 -c seq' | rpn 1 100 100 ? -c binary >>count.bin


次に均等分割による2分法ではなく黄金比率で分割して数字を探索します。上記と同様にgoldenというrpnプログラムを用意します。プログラムの仕様はbinaryと同じで、異なるのは探索時の分割方法だけです。

それでは、同様に100回繰り返します。

  >rpn -c null >count.gol
  >rpn 100 -c seq' | rpn 1 100 100 ? -c golden >>count.gol
                               :
                             (中略)
                               :
  >rpn 100 -c seq' | rpn 1 100 100 ? -c golden >>count.gol


これでファイルのcount.golに探索結果が格納されました。それぞれを横結合して、基本統計量を計算してみましょう。

  >paste count.bin count.gol | rpn #g _ #b _ @b @g | rpn -c statinfo
  デ ー タ        100       100
  最 小 値        6         5
  最 大 値        7         8
  範    囲        1         3
  合 計 値(Σ)    678       682
  平 均 値(μ)    6.78      6.82
  分 散 値(σ2)   0.1716    0.4676
  標準偏差(σ)    0.414246  0.683813
  分 散 値(s2)   0.173333  0.472323
  標準偏差(s)    0.416333  0.687258
  歪度(a3≒0)    -1.35185  0.0573446
  尖度(a4≒3)    2.82751   2.47542
  変動係数(ν)    0.0614061 0.100771


均等分割の平均探索回数が6.78回に対し、黄金分割による方法が6.82回です。黄金分割のほうが探索に多くの回数が掛かっています。どうも話が違いますね。幹葉表示による分布形状で見てみましょう。

  >rpn x _ <count.bin | rpn 10 * -c stemleaf
   6 | 0000000000000000000000
   7 | 0000000000000000000000000000000000000000000000000000000000000
       00000000000000000

  >rpn x _ <count.gol | rpn 10 * -c stemleaf
   5 | 0
   6 | 0000000000000000000000000000000
   7 | 00000000000000000000000000000000000000000000000000000
   8 | 000000000000000


均等分割による探索はほとんどが7回に集まったピークの高い分布です。対して、黄金分割による探索のほうは6回から8回に渡ってバラつきが大きく、なだらかな分布になっています。どうも黄金分割は当たり外れのある探索という感じは否めません。

このシュミレーションでは均等分割による探索では78%が最悪の7回探索になっています。逆に22%が最悪回数にならなかった探索です。黄金分割の場合、68%が最悪の7回以上の探索です。逆に32%が最悪回数にはなりませんでした。

実践数学アラカルトに戻るLinkIcon

情報関連記事として、応用コーナーウサギとフィボナッチがあります。興味のある人は閲覧ください。

警告rpnプログラムを実行するには、rpn試用版かrpn標準版が必要です(バージョンの違いはこちら)。

情報pasteは講座サポートで公開されています。fold, seq'はユーティリティーパッケージに同梱されています。statinfo, stemleafはrpnマイスターパッケージに同梱されています。nullはカレンダー・システムパッケージに同梱されています。rownumはカンタン分析パッケージに同梱されています。xypとnpdはrpnの姉妹ソフトウェアです。詳しくはプロダクトを参照ください。

数学アラカルト

数字と遊んでみよう

※実践コーナーのTOP

紹介 rpnの利用シーンはこちら…

講座初めての人のrpn基礎もどうぞ
講座しっかり学べるrpn入門もどうぞ
講座すぐに使えるdos入門もどうぞ

実践他の分野への挑戦は実践TOP

応用rpnアプリケーションは応用TOP

part2

数字と遊んでみよう

※実践コーナーのTOP

講座初めての人のrpn基礎もどうぞ
講座しっかり学べるrpn入門もどうぞ
講座すぐに使えるdos入門もどうぞ

実践他の分野への挑戦は実践TOP

応用rpnアプリケーションは応用TOP

書籍紹介

記事に関連した書籍

本ウェブサイトで扱った話題に関連した書物で、スタッフが実際に読了したものを紹介。

書籍数学の書籍
数の世界は思ったよりもエキサイティング。

  • 書籍統計の書籍
  • ビジネスで統計が使えるととっても有利。

書籍投資の書籍
失敗しない投資には広範囲で実践的な知識が必要。

警告バックスラッシュはエンマークに読み替えてください( IEのみ)。
バックスラッシュとエンマーク

警告文字で作られた図表や式が崩れることがあります。ブラウザによっては固定幅フォントをMSゴシックにするときれいに表示されます。それでも崩れる場合は図表や式をメモ帳にコピー後、閲覧下さい。

警告rpn試用版と標準版(2kリビジョン)はダブルクォートで囲ってください。

rpn 1 2 + ⇒ rpn "1 2 +"
rpn 1 -c foo ⇒ rpn "1" -c "foo"

ダブルクォートは省略できることが多いのですが、慣れない間は囲んだほうが無難です。なお、本ウェブサイトの記事ではrpn標準版(98リビジョン)を使用しているため囲っていません。詳しくは技術サポートの「rpn TIPS参照ください。

注意rpnの障害情報はこちら

警告rpn試用版の場合、複雑なプログラムや処理時間のかかるプログラムの一部には動作しないものがあるかもしれません。あくまで無料提供であることを勘案・了承ください。rpn標準版は、すべてのプログラムが動作します。