組み合わせ爆発のはなし - 大人になってからの再学習
YouTube 上に公開された 「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」 という動画が話題になっている。 http://youtube.com/watch?v=Q4gTV4r0zRs 下の図のようなNxNの格子を用意して、左上のスタート地点から、右下のゴール地点にたどり着くルートの数を数えてみよう、というもの。 この例は3x3の格子。 さて、何通りあるか？ ルートは最短ルートである必要はなくて、下から上に向かっても構わない。ただし、ルートは自分自身に交わってはいけない。 3x3の格子の例では、答えは184通りある。 意外とたくさんあることに驚かされる。 では、4x4の場合は？ 動画の中では「おねえさん」が手で数えているけど、答えは8,512通り。 5x5の場合は、もはや手で数えるわけにはいかなくなる。動画の中のコンピュータを使って求めた答えは1,262,81
パイこね変換を分数演算で"正しく"変換する - yattのブログ
『渋滞学』を最後まで読みきらずにいたのを思い出して読んでみた。 『渋滞学』によるとパイこね変換というアルゴリズムがあり、”コンピュータは原理的にこの計算はできない”らしい。 0 <= x <= 1 while True: if x < 0.5: x = 2x else: x = 2 - 2x print xこの計算は浮動小数点の誤差をどんどん大きくさせるのでだんだん誤差がひどくなりまともな結果にならなくなるらしい。 Pythonのインタプリタで確認した。 x = 0.1 >>> for _ in xrange(100): ... if x < 0.5: x = 2*x ... else: x = 2 - 2*x ... print x ... 0.2 0.4 0.8 0.4 0.8 0.4 0.8 0.4 0.8 0.4 0.8 0.4 0.8 0.4 0.8 0.4 0.79999999
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
