ビギナーバイナリーオプション

フィボナッチ数列は再帰関数の題材として適切なのか

フィボナッチ数列は再帰関数の題材として適切なのか

情報処理Ⅱ 2007年12月3日(月) その2.

Presentation on theme: "情報処理Ⅱ 2007年12月3日(月) フィボナッチ数列は再帰関数の題材として適切なのか その2."— Presentation transcript:

1 情報処理Ⅱ 2007年12月3日(月) その2

2 本日学ぶこと 再帰(recursion) ⇒自己言及なくして情報技術を語るなかれ ライブラリ関数 ⇒先人の知恵を拝借
ライブラリ関数 ⇒先人の知恵を拝借 フィボナッチ数列は再帰関数の題材として適切なのか フィボナッチ数列は再帰関数の題材として適切なのか 共通するキーワード:関数の活用

3 前回の補足:関数の抽出 関数を抽出することで一般に 関数抽出の要点 コード量(プログラムのサイズ,ステップ数)は増える.
しかし,それぞれの関数のコード量は減り,関数ごとに役割が明確になるため,読みやすい. 関数抽出の要点 ①関数名,②戻り値の型,③仮引数 の順に決める. 変数の有効範囲に注意する. 仮引数と実引数が同じ名前でも,別オブジェクト. 変数の除去や複製が必要なこともある. 保守性向上

4 再帰呼び出しとは 関数の内部で自分自身を呼び出すことを,再帰呼び出し(フィボナッチ数列は再帰関数の題材として適切なのか フィボナッチ数列は再帰関数の題材として適切なのか リカーシブコール,recursive call)という. 用途 注意点
再帰的(帰納的,循環的)な定義 バックトラック(backtrack) 分割統治法(divide-and-conquer) フィボナッチ数列は再帰関数の題材として適切なのか 注意点 無限ループにならないようにする. 再帰を使わないほうがよいこともある. 「データ構造とプログラ ミング技法」他で リp.121, pp

5 階乗を求める関数 階乗 プログラムコード 0! = 1, 1! = 1 n! = n×(n-1)! (n≧2)
int factorial(int x) < if (x 関数factorialの中で 関数factorialを 呼び出している…再帰! factorial.c

6 なぜ再帰呼び出しが可能なのか? 同一の変数名x に対して複数の このようなデータ 構造を,「スタック」 オブジェクトが という.
生成される. このようなデータ 構造を,「スタック」 という. factorial x = 1 factorial x = 2 factorialの再帰呼び出しを終えたときの戻り先 factorialの呼び出し(関数処理)を終えたときの戻り先 factorial関数処理時に 生成されるオブジェクト main x = 3 Cの規格として「スタック」が必須ということではない. しかし,関数呼び出しの構造(mainから関数Aを呼び出し,関数Aの中で関数Bを呼び出し,関数Bの処理を終えたら, 制御は,mainではなく,「関数Aの中で関数Bを呼び出したところ」に戻らなければならない(そして,関数Aの処理を 終えたら,制御は,mainの中で関数Aを呼び出したところに戻る))を実行時に保持するには,スタックが最も合理的 ということである. main関数処理時に 生成されるオブジェクト num = 3 入p.285

7 カウントダウン,カウントアップ countdown(5); ⇒ 5 4 3 2 1 0 countup(フィボナッチ数列は再帰関数の題材として適切なのか 5); ⇒ 0 1 2 3 4 5
カウントアップ,カウントダウンともに,再帰呼び出しなしの プログラムのほうが,効率はよい. フィボナッチ数列は再帰関数の題材として適切なのか なぜ再帰呼び出しは効率が悪いか? …関数呼び出しのコスト(オーバーヘッド)があるから. 業務としてのプログラミングで,再帰呼び出しを使用してはならないと(コーディング規約で)定めていることも 再帰呼び出しはしてはいけないと書いている例: 『組み込みソフトウェア開発向けコーディング作法ガイド』p.49 『ずっと受けたかったソフトウェアエンジニアリングの授業2』pp countdown.c, countup.c

8 再帰的な定義の例(1) 階乗 フィボナッチ数列 最大公約数 再帰呼び出しを用いれば,シンプルに書ける.
0! = フィボナッチ数列は再帰関数の題材として適切なのか 1, 1! = 1 n! = n×(n-1)! (n≧2) フィボナッチ数列 a1 = 1, a2 = 1 an = フィボナッチ数列は再帰関数の題材として適切なのか フィボナッチ数列は再帰関数の題材として適切なのか an-1 + an-2 (n≧3) 最大公約数 gcd(n,0) = 0 フィボナッチ数列は再帰関数の題材として適切なのか gcd(n,m) = gcd(m,n%m) (m>0) 再帰呼び出しを用いれば,シンプルに書ける. フィボナッチ数列は再帰関数の題材として適切なのか しかしこれらも,whileループのほうが効率がよい. 最大公約数の式について,n=0や,n

9 再帰的な定義の例(2) 木構造 再帰呼び出しは必要? トーナメント表の決勝戦から順に見て, 優勝チームの戦績を知る
100万個の記録から,欲しいものを 瞬時に獲得する ホームディレクトリ以下のすべての ファイル名を出力する 再帰呼び出しは必要? するのが自然な場合と,してはいけない 場合がある 呼び出し方よりもデータ構造のほうが重要 「100万個~瞬時に獲得する」と木構造の結びつきは自明でないが,2年後期の「データベース」で学んでほしい. 「ホームディレクトリ以下のすべてのファイル名を出力する」には,いちいちプログラムを作らなくても, 「find ~」を実行するだけでいい.

10 再帰的な定義の例(3) 文法 計算機でどう処理する? BNF記法
::= | | '_' | | '_' 句構造文法による式の定義 計算機でどう処理する? 字句解析・構文解析を行う. 再帰下降構文解析は,文法と対応した 解析器(パーサ)を生成するが,効率は 必ずしも良くない. a=b++-+c; ↓ 字句解析 構文解析 OK a=b++++c; NG 再帰下降構文解析 構文解析などに関する基本書籍:中田育男: コンパイラ, 産業図書, 1981. 「b(符号) (符号) (符号) (符号)c」の式で文法的に正しいものはどれか検証している文献:Lepton: フィボナッチ数列は再帰関数の題材として適切なのか Lepton先生のCの強化書, 翔泳社, pp , 2007. リpp

11 次に学ぶこと ライブラリ関数の活用 フィボナッチ数列は再帰関数の題材として適切なのか フィボナッチ数列は再帰関数の題材として適切なのか (参考)関数の分類 先人の知恵を活用する.
勉強・授業のためでなければ, ライブラリ関数と同じ名前や機能の関数は自作しない. (参考)関数の分類 自作関数: 自分で定義する.⇒ 11月26日のテーマ ライブラリ関数: 出来合いのもの.printfなど.⇒ フィボナッチ数列は再帰関数の題材として適切なのか ここでのテーマ 入p.111

12 ライブラリ 関数・定数・独自型などをまとめて,他のプログラムから利用できるよう部品化したものを「ライブラリ」という. ライブラリ関数の分類
標準ライブラリ関数(標準関数,ANSI準拠の関数) 情報処理Ⅱで使用するのは,この範囲だけ POSIX準拠の関数 情報ネットワーク演習で使用する その他(サードパーティライブラリ) OpenGL(ビジュアル情報演習で使用する) など ANSI: American National Standard Institute POSIX: Portable Operating System Interface for UNIX リp.346 フィボナッチ数列は再帰関数の題材として適切なのか フィボナッチ数列は再帰関数の題材として適切なのか フィボナッチ数列は再帰関数の題材として適切なのか

13 ライブラリ関数とヘッダファイル 既に定義されている関数や定数を利用するには,あらかじめ,適切なファイル名(ヘッダファイル)を記載しておく.
printf なら #include CHAR_BIT なら #include ライブラリ関数と,記載すべきヘッダファイル名は,オンラインマニュアルで知ることができる. man 3 printf jman 3 printf JM Project ( ヘッダファイルはコンパイル環境が保有しているが,その所在は,環境による. Vine Linuxでおすすめ リp.369の最後に「詳細は,27.10節を参照して下さい.」とあるが,27.10節は存在しない. 入p.114 リp.369, pp , p.473, p.421

14 ヘッダファイルとインクルード ヘッダファイルには,定数,構造体や特殊な型,関数プロトタイプなどが宣言されている.
#include とすると,/usr/include/stdlib.h を取り込む(インクルードする). 慣例として,ファイル名は「.h」で終わらせる. ヘッダファイルの中で,他のヘッダファイルをインクルードすることもよく行われる. ヘッダファイルを自作することもある.そのファイルをインクルードするときは,#include "headerfile.フィボナッチ数列は再帰関数の題材として適切なのか h" のように書く. 「.c」や「.h」などを,Windowsユーザは「拡張子」と呼んでいるが, Unix文化では「サフィックス(suffix)」と呼ばれている. リp

15 有用なライブラリ関数(1) #include を必要とするもの
int printf(const char *format, . ); int scanf(const char *format, . ); int putchar(int c); フィボナッチ数列は再帰関数の題材として適切なのか … 1文字出力 int getchar(void); … 1文字入力 int sprintf(char *str, const char *format, . ); … printfと同様に文字列を構成し,結果をstr(の指し示す配列領域)に格納する 可変引数 と呼ばれる 可変引数 フィボナッチ数列は再帰関数の題材として適切なのか と呼ばれる リp.455, p.139

16 有用なライブラリ関数(2) #include を必要とするもの
int atoi(char *s); … 文字列から整数値への変換 void exit(int status); … プログラムの終了 int rand(void); … 乱数生成 #include を必要とするもの size_t strlen(char *s); … 文字列の長さ int strcmp(char *s1, char *s2); … 文字列比較 char *strstr(char *s1, char *s2); … 文字列検索 char *strcat(char *dest, char *src); … 文字列連結 #include を必要とするものについて, strcatのdestを除き,char *型の仮引数には,constがつく. リp.493, p.511

17 有用なライブラリ関数(3) #include を必要とするもの
int isdigit(int c); … 文字が数字であるか判定 isalphaは英字判定,isalnumは英数字判定 int tolower(int c); … 大文字を小文字に変換 大文字以外の文字はそのまま 逆はtoupper #include を必要とするもの double exp(double x); … eのx乗 double floor(double x); … x以下で最小の整数 最大はceil,四捨五入(丸め)はround コンパイル時,「cc -lm program.c」のようにリンカオプション(フィボナッチ数列は再帰関数の題材として適切なのか linker option)が必要 リp.411, p.432

18 関数名の表記 printf関数,関数printf printf()関数,関数printf() printf(3) この授業で採用している.
関数名であることを明確にする表記法.よく見かける. printf(3) 「printfというライブラリ関数があって,詳細は, man 3 printfを実行すれば得られる」の意味. 「(1)」ならコマンド,「(2)」はシステムコール man printfを実行すると,ライブラリ関数ではなく,コマンドとしてのprintfの使い方が出てくる. 「printfの実引数に3と書く」ではない.

19 まとめ 再帰呼び出しを用いて関数を定義すると,プログラムがすっきり書けることがある. 一般に,再帰を用いないほうが効率的である.
再帰的に定義された問題に適用すると,効果的. 一般に,再帰を用いないほうが効率的である. 関数内のauto変数は,関数呼び出しごとに生成される. ライブラリ関数の活用により,先人の知恵を活用しながら,信頼性の高いソフトウェアが作れる. 関数名,処理内容,ヘッダファイル,引数,戻り値を把握する. 教科書だけでなく,オンラインマニュアルやインターネットの情報も参考に.

Processingで学ぶ 実践的プログラミング専門課程

今回はその最終回として 「再帰」 を学習します。高校で数学を学習した人ならば, 数学的帰納法の名前は聞いたことがあるでしょう。数学的帰納法は再帰の一例です。マトリョーシカのように式が構成されます。私は, 数学的帰納法や再帰の概念が自分のものになるまでは, フィボナッチ数列は再帰関数の題材として適切なのか それらがまるで魔法のようで手をつけるのが恐ろしいような気がしたものでした。読者の皆さんがそんなふうに恐れて身を引いておられるならば, もったいないことです。是非, 今回の学習で便利さに気付き, 適切に活用しましょう。

再帰 (Recursion) とは, 再帰的な構造を持つアルゴリズムのことです。再帰的な構造とは, 自分自身の定義の中に, 自分自身を含む構造です。再帰の代表的な例として階乗やユークリッドの互除法の再帰的定義がよく用いられます。それぞれについて学習していきます。

階乗と数学的帰納法

整数 n の階乗は記号 ! を用いて n! と書きます。実際の計算は次のように行われます。

階乗のsketch。 Factorial. pde

右辺に ! が出てきましたね。 「 ⁠. 」 なんていう省略記号を用いずに, はっきり式を定義している再帰的定義のほうが美しいと思いませんか?

さて, 数学的帰納法を用いた証明問題で, 同じような構造の式を見たことがあるはずです。数学的帰納法とは次のような方法でした。

  1. 式 f(1) が成り立つことを示す。 f(1) を初期条件という。
  2. 任意の自然数 k に対して, f(k) ならば f(k + 1) が成り立つことを示す。
  3. 2.が成り立つならば, 任意の自然数 n について f(n) が成り立つといえる。これで数学的帰納法による証明おわり。

『教養としてのコンピュータ・ サイエンス』 ( ⁠渡辺治 著) に 「再帰の極意」 として紹介されていること (P. 59) が, この数学的帰納法についても同様に言えます。つまり, ひとつ後の式 f(k+1) が正しく実行されるために, 今の式 f(k) は正しく実行されると信じ込む, 疑わないことが大切です。こう言及すると, 何か詐欺でも働いているようですが, 再帰ならば最終的な条件, 数学的帰納法ならば初期条件をしっかり定義したのだから大丈夫なのです。どんどん進んで条件に打ち当たれば, その条件に定めた処理を実行するだけです。

[作業] 10の階乗を行うsketchを作成しましょう。(1)フィボナッチ数列は再帰関数の題材として適切なのか 繰り返し構文を使ったメソッド, (2)再帰するメソッド, この2通りのコードをひとつのsketchの中に書いてみましょう。

ユークリッドの互除法

ユークリッドの互除法も, 再帰を用いる代表的な例です。2つの正の整数 m と n についての最大公約数を求めるアルゴリズムです。 『 フィボナッチ数列は再帰関数の題材として適切なのか フィボナッチ数列は再帰関数の題材として適切なのか フィボナッチ数列は再帰関数の題材として適切なのか ⁠改訂C言語によるはじめてのアルゴリズム入門』 ( ⁠河西朝雄 著, P. 37) には次のように書かれています。

  1. 正の整数 m , n について。
  2. m と n が等しくない間、次の操作3.を繰り返す。
  3. m > n ならば m = m-n 、そうでないならば n = n-m
  4. m (または n ) が最大公約数である。
  1. 入力を m, n(m >= n) フィボナッチ数列は再帰関数の題材として適切なのか とする。
  2. n = 0 なら、 m を出力してアルゴリズムを終了する。
  3. m を n フィボナッチ数列は再帰関数の題材として適切なのか で割った余りを新たに n とし、更に元の n を新たに m とし2.に戻る。

sketch GCD_ General. pde 。再帰を用いずにユークリッドの互除法で最大公約数を求める。

  1. 2つの正の整数 m, n の最大公約数を求める。ただし, m < n の場合は m と n の値を交換してから関数を適用する。こののち関数を gcd(m,n) を呼ぶ。
  2. m と n が等しければ, m が最大公約数である。手順はこれで終了。
  3. m と n が等しくなければ, 新しい m の値を m-n とし, 手順1.に戻る。

[作業] GCD_ General. pde には, ある欠陥があります。アルゴリズムに条件として述べられている 「m,nが正の整数であること」 をチェックしていないのです。マウスポインタがディスプレイウインドウの 「ふち」 にちょうど重なると, ぴたっとsketchが動作を止めます。これは入力に0があったために無限ループに陥るからです。この欠陥を修正しましょう。

再帰を活用するメリットとデメリット

再帰を活用するメリットは, 「 ⁠ ( ⁠場合によっては) 問題をシンプルに記述できること」 です。しかし, 再帰は電子計算機で実行するアルゴリズムとしてはやっかいな問題, デメリットを抱えています。

そのデメリットを話す前に, 計算量の2つの種類について言及しておきます。計算量は 「時間計算量」 と 「空間計算量」 という2つに区別できます。時間計算量は, これまで何度か取り扱って来た計算量の考え方で, そのアルゴリズムの実行にどれだけ手数がかかるかを表す量です。これに対して空間計算量は, そのアルゴリズムの実行にどれだけの記憶容量が必要かを表す量です。

再帰のアルゴリズムは, 自分自身を1回呼ぶ度に, 自分自身を実行するために必要なメモリを用意します。再帰の回数が多くなれば, 必要なメモリ容量も多くなります。つまり, 再帰のアルゴリズムのデメリットとは空間計算量が大きくなることです。再帰のアルゴリズムは潤沢にメモリがあることを前提とした手段なのです。

かつて, コンピュータがごくわずかなメモリしか持っていなかった時代のプログラミング言語が, 再帰を言語の仕組みとして用意しなかった理由の一つは, 再帰が簡単にメモリを食いつぶす方法だったからでしょう。現在, パーソナルコンピュータのメモリは数ギガバイトを持つようになったため, この問題が大きく扱われることはあまりありません。ただ, 再帰を使ったプログラムによってはメモリを圧迫しますので, 利用にあたっては慎重になりましょう。

そのため, 再帰アルゴリズムを使用するべき場合とは, コードを劇的にシンプルにできる場合に限ると考えておくべきです。 「 フィボナッチ数列は再帰関数の題材として適切なのか ⁠劇的にシンプルにできる場合」 に気付き, 再帰を適用できるためには, あらかじめ再帰を使えるようになっている必要があります。ですから学習が必要なのです。

さらに学ぶために

実は, 前回までで学習したソートやサーチにおいて, 再帰が上手く活用されているアルゴリズムがあります。これらによってより実用的な再帰処理を学習できるのですが, 今回のテキスト分量としては大きくなりすぎると判断したので割愛します。再帰についてより深く学習したい方は, キーワード 「クイックソート」 「 ⁠バイナリサーチツリー」 について調べてみましょう。

演習1 (難易度:easy)

フィボナッチ数について調査し, n 番目のフィボナッチ数を求めるsketchを書きましょう。再帰を用いない getFibonacciGeneral と再帰を用いる getFibonacciRecursive の2つのメソッドを書きましょう。sketchファイル名を GetFibonacci. pde としてください。

演習2 (難易度:middle)

マウスカーソルの座標値 x , y の最大公約数を求めるために, ユークリッドの互除法を再帰的に使ったsketchを書きましょう。 GCD_ General. pde を適宜変更してください。sketchの名前は GCD_ Recursive. pde としてください。

  • 再帰とその代表的なアルゴリズムを学習しました。
  • 再帰のメリットとデメリットを紹介しました。

学習の確認

それぞれの項目で, Aを選択できなければ, 本文や演習にもう一度取り組みましょう。

  1. 再帰の仕組みが理解できましたか?
    1. 理解できた。気持ちよく納得した。
    2. 理解できた。しかし, 今ひとつスッキリしない。
    3. 理解できない。
    1. 理解できた。気持ちよく納得した。
    2. 理解できた。しかし, 今ひとつスッキリしない。
    3. 理解できない。
    • 『改訂C言語によるはじめてのアルゴリズム入門』 ( ⁠河西朝雄 著, 技術評論社⁠ ) ⁠
      • アルゴリズムの入門書。入門者に取っては十分に辞書的な内容です。丁寧に解説された良書。
        フィボナッチ数列は再帰関数の題材として適切なのか
      • 大学1年生の教養科目としてのコンピュータ・ サイエンスの教科書。薄くて内容が精選されています。平易な文章と最低限の数式で構成されており, コンピュータ・ サイエンスがどんな学問分野なのか知りたい方にはおすすめします。P. 57から数頁ですが再帰についてマージソートを例に分かりやすく解説しています。

      [作業] 解答例のsketchには負の数が入力された場合のチェックはありません。このメソッドをより一般的に使えるものにするためにはチェックの必要があります。時間があれば取り組んでみてください。

      フィボナッチ数列は再帰関数の題材として適切なのか

      2021/09/19 23:58 編集

      日本人が英会話を勉強するときに、二つの考え方があります。 (1) 日本語での会話を瞬時に英語に翻訳して話そうとする。 (2) 英語で考えて英語で話そうとする。 (1)でまともに英会話するのは現実問題として無理です。 おはようございます = Good morning こんにちは = Good afternoon こんばんは = Good evening では、11時にあいさつするときは? とか考えていては会話になりませんね。 Good morning : May you have a good morning と理解していれば、そしてmorningはsunriseからnoonまでだと理解していれば、瞬時に反応できますし応用も利きます。 これと同じように、CでプログラミングするときはCで考え、PythonでプログラミングするときはPythonで考え、再帰でプログラミングするときは再帰で考えるのが楽ですし実用的です。 私は良く再帰のコードを書きますが、その理由は再帰で考える方が楽で、短い時間でコードが書けるからです。しかし、再帰コードは実行性能が悪い(遅い)ことが多いので、性能を気にするときは、最初からループで書きます。 ループで書いたコードを元に再帰コードを作るというのは意味がありませんし効率が悪いと思います。

      > maisumakun 確認ありがとうございます。他の方も同じような疑問が浮かぶかと思いましたので、質問の背景を詳細に下記に記載しておきます。 上記のようなコードを再帰実装する上での処理ステップを言語化して人にわかりやすく説明できるようになるため、もしくはより汎用的な説明を見つけるために、わざわざfor-loopから再帰で書こうとしています。 まずは、for-loopを実装して、それから再帰に書き換えてみましょう、という説明の仕方が一番クリアで実装前の実装後を比較しながら対応付けをしつつ理解しやすいと思ったからです。 フィボナッチ数列は再帰関数の題材として適切なのか フィボナッチ数列は再帰関数の題材として適切なのか フィボナッチ数列は再帰関数の題材として適切なのか 最初から再帰を実装しろ、という教え方は、誰にでも通じる説明の仕方ではない一方で、for-loopはわりと手続的に理解ができ、処理ステップが理解しやすので、手続的に理解してから命題的に課題を解く、っていう考え方のほうがいいかなと思っています。 仮に最初から再帰的に解けと言われた瞬間に手続的に踏む処理ステップがblack boxになり、ある数式を途中式をかかず説明せずにこれで動くんです、自明である、的な説明で終始しがちになります。その思考癖だとデバックはもとい、これはこうだから動く、なんとく私のローカル環境では動くから正しい、のような思考癖になります。 で、その説明をする上で、上記のようなループがいれくんだ複雑なコードになった瞬間、手続的→命題的に、for-loop→recursionのステップでの理解がしづらくなってきた気がしましたので、どう説明及び言語化したらいいだろうか、というのが質問の背景になります。

      IT・技術研修ならCTC教育サービス

      教育サービス

      Java 5で追加された並行処理のためのjava.util.concurrentパッケージに細かい粒度で並列性を増したFork/Joinフレームワークが Java 7から登場しました。大量の計算を小さく分けてマルチスレッド処理をしようという戦略で、これを分割統治法(Divide and Conquer Algorithm)と呼びます。
      いかつい名前ですが、問題を小さく分割して最終的に解決しようとする方法はとても自然です。
      加えてフレームワーク内部ではWork Stealingという方策で最小限のコストで適切にタスクを分配できる実装が為されています。これによりマルチコアCPUを効率的に稼動させる事が出来るのです。

      フィボナッチ数列は単に再帰的に足し算するだけの単純な計算のため今回は恩恵を享受できない上にオーバーヘッドのコストが上回ります。
      筆者の非力なマシンでは、数値を増やすと目に見えて遅くなりました。
      むしろシンプルな線形アルゴリズムを使えば高速に実行できるでしょう。
      しかしながら、再帰すべき計算処理が複雑で且つ、多数のコアを有する場合に「コア数を意識することなく記述が可能」で、しかもコア数が増える程に飛躍的に処理速度が向上することでしょう(並列度は指定可能)。つまりメニーコア時代の潤沢な計算資源を有効活用する光明かもしれません。

      現在から少しだけ未来の話になりますが、Java 8リリースではFork/JoinフレームワークにParallelArray(並列処理のためのコレクション)が登場して内部イテレータで容易に並列化できる記述が検討されています。
      同じくJava 8に持ち越しされたProject Lambdaでラムダ式(クロージャー)が登場し、並列化での冗長な記述を排除し簡潔に表現出来ると期待されます。

      アルゴリズムの題材として初等数学のフィボナッチ数を取りあげました。
      フィボナッチは神秘的な数列で植物の花弁や葉の数、または巻き貝と一致するのが散見されます。フィボナッチは自然界とリンクしています。
      また幾何学的にもフィボナッチ数列の各項を一辺とする正方形を描き、その一辺の中点から対面する角への斜線を半径とした円弧を辺の延長線上まで描き、それを繰り返していくと黄金螺旋(フィボナッチ・スパイラル)なる綺麗な図形が紡ぎ出されます(Sybase社のロゴに使われていました)。
      隣り合う正方形一辺の比率は1:1.618(近似値)で黄金比率に収束します。
      最も美しいとされる比率です。やはり花弁と同じ比率を美しいと感じ取る人間こそがまさに自然の一部なのだと強く感じます。

      CTC教育サービス 関連コース

      [IT研修]注目キーワード Python UiPath(RPA) 最新技術動向 Microsoft Azure Docker Kubernetes

      IT・技術研修ならCTC教育サービス

      教育サービス

      Java 5で追加された並行処理のためのjava.util.concurrentパッケージに細かい粒度で並列性を増したFork/Joinフレームワークが Java 7から登場しました。大量の計算を小さく分けてマルチスレッド処理をしようという戦略で、これを分割統治法(Divide and Conquer フィボナッチ数列は再帰関数の題材として適切なのか フィボナッチ数列は再帰関数の題材として適切なのか Algorithm)と呼びます。
      いかつい名前ですが、問題を小さく分割して最終的に解決しようとする方法はとても自然です。
      加えてフレームワーク内部ではWork Stealingという方策で最小限のコストで適切にタスクを分配できる実装が為されています。これによりマルチコアCPUを効率的に稼動させる事が出来るのです。

      フィボナッチ数列は単に再帰的に足し算するだけの単純な計算のため今回は恩恵を享受できない上にオーバーヘッドのコストが上回ります。
      筆者の非力なマシンでは、数値を増やすと目に見えて遅くなりました。
      むしろシンプルな線形アルゴリズムを使えば高速に実行できるでしょう。
      しかしながら、再帰すべき計算処理が複雑で且つ、多数のコアを有する場合に「コア数を意識することなく記述が可能」で、しかもコア数が増える程に飛躍的に処理速度が向上することでしょう(並列度は指定可能)。つまりメニーコア時代の潤沢な計算資源を有効活用する光明かもしれません。

      現在から少しだけ未来の話になりますが、Java 8リリースではFork/JoinフレームワークにParallelArray(並列処理のためのコレクション)が登場して内部イテレータで容易に並列化できる記述が検討されています。
      同じくJava 8に持ち越しされたProject Lambdaでラムダ式(クロージャー)が登場し、並列化での冗長な記述を排除し簡潔に表現出来ると期待されます。

      アルゴリズムの題材として初等数学のフィボナッチ数を取りあげました。
      フィボナッチは神秘的な数列で植物の花弁や葉の数、または巻き貝と一致するのが散見されます。フィボナッチは自然界とリンクしています。
      また幾何学的にもフィボナッチ数列の各項を一辺とする正方形を描き、その一辺の中点から対面する角への斜線を半径とした円弧を辺の延長線上まで描き、それを繰り返していくと黄金螺旋(フィボナッチ・スパイラル)なる綺麗な図形が紡ぎ出されます(Sybase社のロゴに使われていました)。
      隣り合う正方形一辺の比率は1:1.618(近似値)で黄金比率に収束します。
      最も美しいとされる比率です。やはり花弁と同じ比率を美しいと感じ取る人間こそがまさに自然の一部なのだと強く感じます。

      CTC教育サービス 関連コース

      [IT研修]注目キーワード Python UiPath(RPA) 最新技術動向 Microsoft Azure Docker Kubernetes

      関連記事

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

目次
閉じる