2014年4月4日金曜日

フィボナッチ数列を動的計画法で高速化する頭の体操をしてみた


入社試験の季節。プログラムの実技試験で撃沈したのは今は昔。
とってもボロボロだったけどなんでか採用してもらえたのを思い出します。
入社してから苦労してますが、なんとかやっていけています。

てか、新卒採用でプログラム試験やる会社ってなかなかないだろうなぁ。。
いまはgithub採用なんてあるらしいね。選別しやすいんだろうなぁ。

とりあえず、入社時はオブジェクト指向なにそれおいしいの?っていう人でもプログラムに興味ある人なら普通に生きていればそれなりにプログラマとしてやっていけます。

個人的に思う会社に入るメリットは、先人たちが実装した秘伝のタレを覗けることです。
スーパープログラマの実装をトラッキングして、真似して、自分のものにすることが若手エンジニアに求められていることな気がする。

なんか初々しい気持ちになったので、
今日は入社試験に出ると面白いかもな問題を自分で設定してサクッと解いてみる。

======================================================================
問題:
「フィボナッチ数列を、なるべく早く、安定して動作するプログラムを実装せよ」
======================================================================


アルゴリズム的な話:
 プログラムの経験のある人だったら再帰で数行書いて終わりやんって人ばっかりかも。
 数学屋さんなら一般項を導出してO(1)なプログラム書いちゃうかも。

高速化の話:
 動的計画法打ち込めるかどうか程度しか差異がでないのでただの暗記問題になってしまうかも

安定して:
 再帰呼び出しのスタックオーバーフローとか気にしてくれると嬉しいかも
 (まぁFibonacciくらいじゃスタックオーバーフローしないけど)


0 件のコメント:

コメントを投稿