日記「芦」
神話は歴史より説得力がある。[...]愛は死より強い。（ロバート・フルガム著「気がついた時には、火のついたベッドに寝ていた」） NAND回路 2011/6/27(Mon.)1年の時に情報で習った内容なので（特に用語が）うろ覚えシリーズ。 電気回路は2つの入力(IN1, IN2)に対し、1つの出力(OUT)で返す。入出力は1/0である。 NAND回路は下の表のようになる。NANDはNotAndの意味。AND回路とかNOT回路とか、OR回路とかもあるけれど、 NAND回路を組み合わせることで(出力を別のの入力にしたり、複数の入力に使ったり) 全て再現できるらしい。 出力は2^4=16通りだけど16通り全部再現できるんだっけ？ というわけでその回路（NANDの組み合わせ）を模索するプログラムを書いた。 3時間くらいかかった。
遊び方。 IN1,IN2,OUTの表のOUTの0/1を設定する。 右下のselectからANDとかを選ぶとOUTを勝手に設定する。 「スタート」ボタンを押すと、回路を解こうとする。 その左のselectは解くスピード。たぶん「高速」でいいと 思うけど、他のプログラム使いながらだと、パソコンの負担 になりうるので、一応遅めのスピードにも設定でいる。 下に式を表示して、ああ、頑張ってるなあと見れる。 式の最後にFINISH!と表示されたら、終わり。 式の見方。 解き方は別に大したこと無くて、乱択です。 まず、NAND回路を3つ～20つくらい（実際には1以上の自然数個） を用意して、0,1,2..と順に数字を振ります。 それぞれの出力をout0,out1..という変数で表します。 一つのNAND回路の働きをnandという関数で表現しており、 例えば、入力としてIN1とout0を取るNANDの2番の出力out2を nand(IN1, out0) と書く。 上の式では out2=nand(IN1, out0); と書いてる。 最後にOUTに出力して終わり。
感想とか。 さらっと書いたつもりだけど、乱択アルゴリズムです。理論的には ずーっと解けない可能性もあるし、一瞬で解けるかもしれない。 NOTはNAND1つ。ANDは2つ、ORは3つでXORは4つが必要。 まあ、大体、かかる時間はこの通り。 ただ2つと3つとの間にすごい時間の隔たりを感じます。 単純に必要なNANDの個数だけじゃなくて、その回路を再現する バリエーションの個数も関係するだろうけど、グラフを書いてみたら きっと面白いだろう。 まず、ランダムにNANDを用意する。それをランダムにつなげて 解になってるかを確かめる。 必要以上にNANDを用いた回路を答えとして出す可能性もある。 NANDの個数は1以上の∞未満の自然数だけど、たぶん3コくらいだろう、と 勝手に推測してたので、確率的には3コになりやすいようにしこんでる。 そういえばNANDを組み合わせてXORをつくりなさい、って課題が 1年の時に出たのを思い出した。自分で考えるのを初めから放棄 して、あとでググろうと思って、結局クラスの人に見せてもらったｗ #memo : <select>タグを使ったの、初めてだ！ 追記 : 式が重複してるのとか消さないとな、ってずっと思ってたので やっと改良した。意外と手間取った。式一つ一つを配列に入れておいて 重複を見つけてから最後にjoinすればいいじゃん。って思ってたんだけ ど、何故か上手くいかない。原因は分からないけど取り敢えず文字列 として扱って重複を消す作業にした。(2011/6/29)
コメ(0) | トラ(0)