Coding Memorandum

プログラミングに関する備忘録

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ICFPC 答え合わせ

早速,解法について書かれていたので参照させて頂きました。

ありゃ?ゲートの解析までは全く同じ考え方のようです。

ゲートはカルノー図で表される(ステートレス)であろうと想定し,入力と出力の組み合わせが分かっているので,カルノー図の全通りで探索すれば良いと「3^9=19683(片ピンのカルノー図パターン数)の二乗(L,Rピンの組み合わせ)×3(ループ接続したピンの初期値:0/1/2)」で探索をかけたのですが・・・解が見つかりませんでした。上の記事によればカルノー図でいけそうですね???

どうやらcircuit構文の解釈に間違いがあった・・・ようですが,まだよく分かっていません。なにせ,同じ入力シーケンスでありながら異なる出力値が出るという結果を得てしまっていましたので。もう少し,色々な方の記事をウォッチしてみます。

結局,ゲート解析の結論として「ゲートは何かレジスタを持ったステートマシンだ」という方向に走ってしまいました。これが敗因のようです。いま冷静に考えると,ここまで問題を難しくされることももないのかなぁとも思います。


7/7追記

どうやら,circuit構文の'X'の解釈を完全に間違えていたようです。
'X'表記のゲートは「a special "external" gate」だと誤解してました・・・。「'X'はspecial gateの接続点を示す」が正解だったようです。 この解釈でゲート解析を実行したら無事にカルノー図を得られました。

しかし・・・key circuitの例を見れば,自分の間違いに気づいてもよさそうですが。そのときは,'X'はNCを示すと思い込んでしまっていました。

このため,直列に接続したと思い込んでいた回路は実際にはフィードバックを含む回路となっていて,先の記述の通り「同じ入力シーケンスでありながら 異なる出力値が出る」という事態を起こしていました。

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://msirocoder.blog35.fc2.com/tb.php/55-10c55986
この記事にトラックバックする(FC2ブログユーザー)

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。