フィボナッチ数列の場合、Aは正則です。N+1番目のフィボナッチ数列を調べるばあい、末尾再帰 F :- F( A X)が N 回呼び出されますが、行列 A の N 乗 と ベクトル X の積と、Fの結果が一致します。 今回は素直にnumpyで行列のN乗を使ってますけれども、 スペ…

フィボナッチ数列の場合、Aは正則です。が、ちょっと脱線して、Aが正則でない場合を考えるに、X = A Xを繰り返すことで、XはAの固有値が最大になる固有ベクトル（の倍数）に近づいていきます。（べき乗法） 。。。って、放送大学 「数値の処理と数値解析（'1…

そう考えると、ならばとなります。というわけで、線形代数を使うと、（若干手間はわかかりますが） 再帰を行列のべき乗に代替したり、再帰関数が終了するかどうかを比較的容易に判定することが出来る、はずです

たとえば、フィボナッチ関数を考えます 例によって 変な擬似言語 F(0 x1 x2) :- 0 F(0 x1 x2) :- x2F(x,y) :- F(n-1,x2,x1+x2) で、ここで引数を n次のベクトルだと考えてみます X={n x1 x2 1} ベクトル F( [0 x1 x2 1]) :- 0 #ベクトルXの第1要素が0 F( [1 …

今回は再帰関数を、行列のべき乗に直してみます。その３とか書いてあるけど、記事が増えたので適当にナンバリングしてみただけです。（雑）

逆に、隣接行列だけ見ても さっぱり 終わるのか無限ループになるのかわからない例説明は 竹内関数 wikipedia参照これも隣接行列を書いてみます。 関数一個だけなので 逆にわかりにくい気もしますが。 Tak(X,Y,Z) :- X Tak(X,Y,Z) :- return Tak(Tak(X-1,Y,Z)…

なんちゃってPrologっぽく書いてあるけど、Prologでは動かない擬似コード。 ハノイの塔 (1 スタート ゴール 空き 手順) :- 手順=[ (スタート.ゴール) ]. ハノイの塔 (n スタート ゴール 空き 手順) :- ハノイの塔(n-1 スタート 空き ゴール 手順１) , ハノイ…

次のような末尾再帰の関数によってフィボナッチ数列を計算する場合を考えます 0番目のフィボナッチ数は0 再帰によってNが1になったらX2を返す Fib (0,X1,X2) :- 0. Fib (1,X1,X2) :- X2. Fib (N,X1,X2) :- Fib(N-1, X2,X1+X2).たとえば、７番目のフィボナッ…

概略）注）こういうのに興味が出てきたら、Haskell使ったほうがいいのかも、と思えてきたけど数学苦手なのでHaskellのドキュメント読んでもさっぱりわかりませんプログラムがちゃんと終了するかどうか、関数の隣接行列によって調べることを考えます 関数の中…

#エントリーポイント def hanoii(n): if isinstance(n,(int)) and n>0: return hanoii_main(1,2,3,n=n) else: raise Exception assert hanoii(1) == [(1,2)] assert hanoii(2) == [(1,3),(1,2),(3,2)] assert hanoii(3) == [ (1,2),(1,3),(2,3),(1,2),(3,1),…

ちっちゃい！ コメントのほうが多い！ # -*- coding: utf8 -*- "kwmatch.py PUBLIC DOMAIN" class KwMatch(object): #引数の型によって比較関数切り替え cmps={ type:lambda x,y:isinstance(x,y), slice:lambda x,y:y.start set:lambda x,y:x in y, } def __…

Py2 Py3 ともに動作確認済み ハノイの塔 すっきり！ # -*- coding: utf8 -*- from __future__ import print_function from kwmatch import KwMatchif __name__=="__main__": hanoii_main=KwMatch() @hanoii_main.case(n=1) #１枚のとき def _(start,goal,res…

pythonにて（Prolog風に？）引数が特定の値になったときに、呼び出す関数を切り替えるクラスを書いてみました。 値によるマッチングで、ハノイの塔などもすっきり 値は 範囲や集合に含まれるかもチェックできる 型チェックなどにも使える （前回書いたのより…

pythonにて、 JAVAとかC++風味に、関数の引数の型とか数によって、呼び出す関数の本体を切り替えるためのデコレータ書いてみました先に、サンプルを兼ねたテストコード（長くなったのでさわりだけ） Py2 Py3 ともに動作確認済み同じ addという名前の関数です…

[0,[1,2,3], [4,5]]のような入力から、 [0,1,4], [0,1,5] , [0,2,4] , [0,2,5] , [0,3,4] , [0,3,5]と、全ての組み合わせを生成するジェネレータがPythonで必要になったので書いてみた (本当はタプルで返したほうがよい)ちょっと書くのに時間がかかったので…

「プログラムが終わる」ことの証明 〜ハノイの塔 編〜 http://d.hatena.ne.jp/boxheadroom/20140902 …これ、20日に書いたんだけど、操作を間違えたのか9/2になってました

無料で使える3DCGソフトBlender。その操作をマクロとして記憶してくれるアドオン Macros Recorder Macros Recorder (blender.org) 同（github）これに少しパッチあてて、記憶したマクロをボタン一発で動作できるようにしてみました*1以下 めっちゃ ざっくり…

Pythonで記号処理、数式処理をする場合はSymPyを使うのが定番かと思います。Mathematicaみたく、代数的な微分積分とか、微分方程式を解くことが出来る すごいソフトです。 前回のコードだとlambda地獄になるので、SymPyにご活躍願って、条件式などを（もうち…

前回の記事の続き。条件分岐の条件式をSymPyで記述しようと思ったのですが、必要な分づつマネして実装してみることに。

昨日のつづき。ちょっとだけ進化させて、デコレータを使ってC言語のswitch 〜 case文みたく書けるようにしてみます (まだまだ名前空間が汚染してますが、一足飛びにやらずに、まず１ステップだけ進めてみます) 条件式の境界テストと、関数の中身の単体テスト…

というわけで、考え方の具体例を書いてみました。お題はみんな大好き FizzBuzz です。Fizz Buzz (WikiPedia) このままじゃアレだし名前空間汚しまくりなので、ここから もうちょっとわかりやすくクラス化して、書きやすく、テストしやすく メガ進化させる必…

PythonでLispのcondっぽくパターンマッチングしてみるのコーナー その１ （その２は無いかも） 世間ではエヴァＱのテレビ放映で盛り上がってる時刻ですが、都合で録画し終わってからしか見られないのでちょいとお遊び。 Pythonでの条件分岐は if文たのみ （s…

Ｃ言語のような文法の言語でも書けますけれども、条件分岐ではなく、lispにおけるcondのような「パターンマッチングによる関数呼び出しのオーバーライド」→状態遷移図と考えることにより、 条件のチェック 関数の中身のチェック を分離することで、プログラ…

数学的帰納法 （の逆さま）になりますが、 円盤が１枚のときは終了することが自明 円盤がＮ枚のとき、Ｎが正の整数ならば、再帰呼び出しによってＮ−１の場合が２回呼び出される (...（（Ｎ−１）−１）... −１)を繰り返せば １になるので、これも終了する よっ…

ハノイの塔についてはググって頂くとして。 ハノイの塔 wikipedia 棒１に刺さっている円盤の一番上のものを、棒２へと移動するとき (1.2)のように表現する たとえば、棒 1に刺さっている３枚の円盤を、棒2へと移動することを考えたときその手順は以下のよう…

自分、こういうの苦手なのですが、、、、 計算可能性理論において停止(性)問題（ていしせいもんだい・ていしもんだい、halting problem）は、あるチューリング機械（≒コンピュータプログラム・アルゴリズム）が、そのテープのある初期状態（≒入力）に対し、…

「猿の惑星 創世記」でチンパンジーがハノイの塔を解いてました。自分、あのパズルが苦手で解いたことなかった→サルに負けた、、、、というわけで、チンパンジーに対抗心を燃やして「ハノイの塔」を題材に、任意のプログラムが終了する（＝無限ループでない…