ange1のブログスマートフォン用の表示で見るange1のブログこの広告は、90日以上更新していないブログに表示しています。divmodアルゴリズムと数値出力Brainf**kはじめに前回で一通り、処理の制御を終わりましたBrainf**k講座、今回からは応用として、良く使う典型的な処理を紹介していきたいと思います。ideoneオンラインのIDE環境で、bffという処理系が使えます。この講座は基本的にこのbffに対応したものです。Brainf**kインタープリタあじさんという方が作られたブラウザ上で動くインタプリタです。細かい挙動の調整や、途中のセルの状態のダンプができたり、重宝しています。終端」を「-1」と設定すると、bffと同じ挙動になります。今回の話題divmodアルゴリズムdivmodとは、ご存じの通り除算・剰余算をまとめて行うものです。実は、割り切れることが予め分かっているのであれば、除算は次のように簡単に書けます。a[---->b+<]これは、a÷4の値をbに加算する例です。aをループ変数として、4減らす間にbを1増やすことで、結果的に割り算を行っています。これでは余りが出ることに対応できません。マイナスの値に突入していつまでも抜け出せないからです。2通りありますが、一方は被除数のバックアップを同時に取るだけの違いなので割愛しますと、次のようなコードになります。ndrqXYn[n->d-[>r+>>X]>Yr?[r+[-<d+>]>q+>>Y]Y<<<<<n]最初に用意しておくのは、次の数です。d処理が完了した時、各セルは次のようになります。途中セルの位置がずれています。X,Yはセルの位置調整用のブランクセルです。処理内容をRubyで書いてみると、次のようになります。endend各セルの動きを図示すると次のようになります。増やしていくということを行っています。バックアップでもあり、divmod終了時に余りを保持するものでもあります。divmodアルゴリズム自体は良く使うものなのですが、特に何が嬉しいかというと、10進数での数値出力ができるようになる、というところです。これまでは、セルの数値が1桁の場合に限り、48を足して文字コードに変換することができました。これでは10以上の数値に対応できません。繰り返すことで、10進数表記での各桁を作っていくということを考えます。大きいというループ持続条件のもと、スライド型のループで各桁を作っていきます。>d[-]>>qn]このコードの動作は次の図のようになります。残っていくことになります。3セル置きになります。不要なので、ループの最後でクリアしています。divmodと数値出力の実例それでは、divmodと数値出力の実例として次のような足し算問題を考えます。1行毎に数値が2行分入力されるとき、その合計を出力するこれに対するBrainf**kのコードは次のようになります。スライド型ループで入力の解釈、続いて加算を行った後、divmodの繰り返しで10進数の桁を作っていきます。インクリメントしているのは、10進数の終端としてブランクセルを使っているためです。なった時に、終端のブランクセルと区別がつかないとまずいので、一時的にインクリメントしておき、出力の時にその分デクリメントして使います。アルゴリズムは、本当に良く使うので、これで対応できる問題の幅がかなり広がるものと思います。次回でBCD演算を取り上げ、最後にしようと思います。)月別アーカイブはてなブログをはじめよう!ange1さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。