3-SATを解く、Schoeningのアルゴリズムという乱択アルゴリズムを実装した。 変数はアルファベット１文字のみ。否定は~。 未検証。(a|~b|~c)&(b|c|~d) のように入力を与える。文字同士の間に空白は入れない。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cctype> #</cctype></string></algorithm></vector></iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/58/5872.pdf二つの四則演算のみの式a,bが与えられる。a=bであるかどうか判定せよ。 変数の値を乱数で適当に決めて、1000回判定をした。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cctype> #include<map> using n</map></cctype></string></algorithm></vector></iostream>…

モンテカルロ法で図形の面積を求めることができる。x*x/4+y*y=1 の式で示される楕円の面積をモンテカルロ法で求める。乱数 0≦x≦2 , 0≦y≦1 を2×1の長方形の中に均一に落とす。 1/4の楕円の中に入った乱数の数をr 落とした乱数の総数をn 1/4の楕円の面積をSと…

モンテカルロ法で円周率を求めるプログラムを簡単に書いてみた。 円周率の計算にはもっとよい方法があるのでこの方法は使われていない。1辺の長さが1の正方形とそれに内接する4分の1円(扇形)がある。正方形の面積 : 扇形の面積 = 1 : π / 4この正方形のなか…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2274 0と1だけの列をランダムに作って条件を満たしていたら出力した。読んだもの http://d.hatena.ne.jp/jetbead/20110912/1315844091 http://www.slideshare.net/iwiwi/ss-13293754解説 h…