C言語とC++言語コミュの確率を求めるプログラミング(2)

ランダムに入力し
0：○○％
1：△△％
の時、

出力
AND：○％
OR：△％
NAND：×％
NOR：◎％
EXOR：☆％
EXNOR：▽％

でいいのか？
これじゃ、確率の問題とも言えないか・・・
日本語って難しいね

>２すみません
入力は０（１）となる確率のみでした。
論理ゲートは何個、なにを使っても対応できるものにしなければならないです。

１）入力の数も定まっていません。

２−１）各入力に対して、０（１）となる確率は１/２とします。
２−２）全ての入力の組み合わせで出力の０と１の確率を出します。

論理ゲート毎にコードを書き直すことはしません。

前のトピックは削除したの?

前のトピックはまだ読んでる途中だったけど、
削除したのかな？　残念…

>4
そうすると確率の問題というより、計算機を作る問題に近いんじゃないか。

論理回路の表現方法は、あらかじめ決められてないのかな。
各自で自由に決めていいのかな？

> パンチ監督

んで、俺がその条件でほとんど正解なコードを前のトピックに書いてたのに
わけもわからず消したの？

馬鹿野郎。
そんなやつは単位落としてしまえ。

入力の数が多くなると、前のトピに書いてあったような方法ではいつまでたっても終わんなくなるよ。

各ゲートの出力の分布を順番に計算して伝播させていく方法はありそうだけど、
ツリーには適用できてもDAGだと簡単じゃないね。

>4
出力は１つになるんだろうか？

#include <stdio.h>

int f_and (int i, int n) {return (i & 1) & ((i >> 1) & 1);}
int f_or (int i, int n) {return (i & 1) | ((i >> 1) & 1);}
int f_user(int i, int n) {
   int j, in[n], out;
   for (j = 0; j < n; j++) in[j] = (i >> j) & 1;
   out = in[0] & in[1] & in[2];
   return out;
}

int main()
{
   struct {int (*f)(int, int); int n; char *s;} g[] = {
      {f_and, 2, "AND"}, {f_or, 2, "OR"}, {f_user, 3, "USER"},
   };
   int i, j, h, m;
   for (j = 0; j < sizeof(g) / sizeof(g[0]); j++) {
      for (i = 0, h = 0, m = 1 << g[j].n; i < m; i++) h += g[j].f(i, g[j].n);
      printf("%s: %f\n", g[j].s, (double) h / m);
   }
   return 0;
}

# この「回答」には一部ジョークが含まれています。

>0 と掛けて…

=====「回答」開始======

このようなプログラムをお望みでしょうか？
(プログラム略)

--使用法--

まず、論理回路のすべての入力に1から連番をふってください。
また、回路内の各論理ゲートの出力にも1から連番をふってください。
次に、回路内の各論理ゲートの出力の真理値表を作ってください。
そして、プログラムの指示に従って真理値を入力してください。

--動作例--
入力数は? 3
ゲート数は? 2
IN1=0,IN2=0,IN3=0 の時 ゲート1の出力は? 1
IN1=1,IN2=0,IN3=0 の時 ゲート1の出力は? 1
IN1=0,IN2=1,IN3=0 の時 ゲート1の出力は? 0
IN1=1,IN2=1,IN3=0 の時 ゲート1の出力は? 0
IN1=0,IN2=0,IN3=1 の時 ゲート1の出力は? 0
IN1=1,IN2=0,IN3=1 の時 ゲート1の出力は? 0
IN1=0,IN2=1,IN3=1 の時 ゲート1の出力は? 1
IN1=1,IN2=1,IN3=1 の時 ゲート1の出力は? 0
ゲート1の出力が「0」の確率は 0.625、「1」の確率は 0.375 です。

IN1=0,IN2=0,IN3=0 の時 ゲート2の出力は?
(以下略)

--注意--
入力数やゲート数が増えてくると真理値表を作るのも入力するのも大変でしょうけれど、頑張ってくださいね。

ちなみに、このアルゴリズムは「平均」と呼ばれています。

ところで「0(1)となる確率を入力」と「0(1)の確率は1/2」は矛盾していますね。

その場合「重み付き平均」というアルゴリズムがあります。

なお、これで解けるのは「任意の組み合わせ論理回路」であって「任意の論理回路」でないのはご承知置きください。

「任意の論理回路」でトンデモ領域を呼び寄せてしまったことにはお気づきでしょうか？

「任意の論理回路」だとフィードバックループもありなので、ある種のメモリーが作れてしまい、現在の入力に加えて過去の(場合によっては無限の過去の)入力も考慮しなければならなくなります。

=====「回答」終了======

…と解く

しかないような…
回路図は不明ですからね (^_^;)

恐らくですが，こういう物を求めているのではないでしょうか？
1つの論理ゲートの入力は必ず2入力を取り，
また論理ゲートの接続が無ければ1/2の確率で0,1が入力されるとする．
(1/2とあるので２入力以外ありえない．ただし入力を必要とする論理ゲートは複数存在するので入力の数は決まっていないと回答された？）

どういうことか具体的な例を挙げると，
2つのandがorに接続されている場合
andに関しては1/2の入力が入り，その結果の確率をorの入力とする．
入力(1/2,1/2)はandの出力では(3/4,1/4)となるので，
orへの入力は(3/4,1/4)と(3/4,1/4)で出力を求める．
(9/16,7/16)が最終的な結果？

またandがorに接続されている場合では
andに関しては1/2の入力で求め，その結果をorの入力とし，
もう一つの入力は1/2として求める．
orへの入力は(3/4,1/4)と(1/2,1/2)で出力を求める．(3/8,5/8)
ただ
>入力を０(１)となる確率と論理回路全体を示すものとし
の意味が今一分かりません．

まあ本人は相変わらず文章力が残念で
いったい何がやりたいのかわかんないし




ご丁寧に大学名と学部名まで情報乗っけてるわけだし
課題を出した教員にメールで問い合わせてみればいいのでは？
まさに外道（AA略

>>15
同意。
んでこんな関数作ればいいと思うんだよね。

バイナリゲートの入力値をそれぞれA, Bとする。
Aが1の確率をx, Bが1の確率をyとすると、

1) A=0, B=0 : (1-x) * (1-y)
2) A=0, B=1 : (1-x) * y
3) A=1, B=0 : x * (1-y)
4) A=1, B=1 : x * y

たとえばANDなら4)がそのまま答え。
XORなら 2) と 3) のときに1になるのだから、その確率を足せばいい。
カルノーグラフ書いて1になるやつだけを
んでその確率を繋いでいけばよい。

むしろツリーの表現がめんどくさいわけで、
引数をポーランド記法で与えて標準出力に確率吐き出すような感じでいいんじゃないの？
こんな感じで
./hoge AND 0.5 XOR 0.6 0.7

あとはこれをスタックに積み上げて逆方向に評価していけばおｋ

私はSPICEの論理回路版を作れというイメージを持ちましたが，
勝手にいろいろエスパーすると，違っていた場合が面倒なので，
不明点を付きつけるに止めておきます．


＞パンチ監督さん
以前のトピックを消したからには，そこに書かれた情報は参照できません．
そのことも踏まえて，問題（プログラム）についての仕様を明確にして下さい．
これまでの話題から
・プログラムに何を入力させるのか．入出力データ例があるとなお良し．
・O(1)の確率の入力とは何か？
・各論理ゲートの入力数はいくつか？
あたりの情報は他人に伝わっていないことが分かります，
また，入出力については，どのレベルの（プログラムに対する／回路に対する／
ゲートに対する）入出力なのかもハッキリしないと混乱のもとになります．

これらの点について特に注意し，問題文を整理したものをレスしてください．
流石に次は新トピックを立ち上げる必要はありません．

どのみち自力でやる気がないのなら、整理しようとしないで、
問題文を一字一句そのまま書きましょう。
質問先として教員のメールアドレスもあれば尚良し。

トピ主の4の記述からエスパーすると、これじゃダメ?

>2つのandがorに接続されている場合
out = (in[0] & in[1]) | (in[2] & in[3]);
{f_user, 4, "USER"},

>またandがorに接続されている場合では
out = (in[0] & in[1]) | in[2];
{f_user, 3, "USER"},


でも、
>論理ゲート毎にコードを書き直すことはしません。
>任意の論理回路でも対応できるようなものにしなくてはならない
これを信じると17や18のような可能性もあるしなぁ。

でもでも、状況から考えてそんな高いハードルを与えられているようにも思えないんだけどなぁ。

とりあえず4>で

>２−１）各入力に対して、０（１）となる確率は１/２とします。
>２−２）全ての入力の組み合わせで出力の０と１の確率を出します。

ってなってるから、
２入力の場合、出力の確率は４分の０〜４、３入力の場合は８分の０〜８に
なりそうだけれども、

>１）入力の数も定まっていません。

>論理ゲート毎にコードを書き直すことはしません

の２点はやっかいだねぇ。

求めたい論理回路毎にソース書き直してもらった方が、
造る側としては簡単でいいんだけれどね。
基本的なコードだけ作ればいいから。

>15
そうそう、そんな感じでツリーになっているときは簡単なんだけど、任意の回路だと
ある入力からワイヤをたどって、出力につながるパスが複数通りある場合があるじゃん。
そうなると、大変だと思うんだよ。前トピの14あたりにあったと思うけど

bool f(bool in)
{
return in & !in;
}

みたいな回路で1/2になると困るし

>論理ゲートは何個、なにを使っても対応できるものにしなければならないです。

論理ゲートに対する出力は入力に対して決まってるけど、
「何個、なにを使っても対応」って所ですべてぶち壊してる気がする...。
不定回路って事ですよね....
入力数、ゲート種別を認識する方法ぐらいは定義してほしい気はします。

前回の話じゃないけど1/2とするみたいな結果なの....？

もう、いい加減トピ主は仕様を明確にできないんだから
質問の仕方を考えてもらわないといかんと思います。

結局、アルゴリズムを考えるトピックじゃなくて、
エスパー合戦になるのは正直、辛い。

いくら議論を進めても、また削除されるんじゃないの?

>エスパー合戦になるのは正直、辛い。

>0: 入力を０(１)となる確率と論理回路全体を示すものとし、
>4: 入力は０（１）となる確率のみでした。

で、「論理回路全体を示すもの」は入力できなくなった上、

>0: 任意の論理回路でも対応できるようなものにしなくてはならない
>4: 論理ゲート毎にコードを書き直すことはしません。

なので、後はプログラムに回路図を「念」で送るしかありません… (^_^;

エスパー能力は必須でしょう。

>いくら議論を進めても、また削除されるんじゃないの?

確かにこれも辛いですよね.....
立てたからにはそれなりの管理責任をお願いしたいですね。

前のトピックはホントに無駄死になっちゃったわけですからねぇ....
（いろんな意味で。）

>>22
課題かどうか定かではないのですが，恐らくそうだろうということで，
比較的簡単なレベルという観点で解釈してみました．
任意というのはまぁある程度の組み合わせ回路でと．
もし仮に出力が入力云々というのがあるのなら，
FlipFlop のような場合もありなど書かれているかなと．
ただ，課題の内容がこれだとすると引数について制約条件がある気はします．
ですので正しいとは思っていません．

目的はエスパー合戦ではなく，
トピ主に対して，自分のやりたいものに近い形を選択して貰おうというものです．
（仮に課題ではないとしても，何かしらの意図はあるでしょうから）
説明能力については課題以上に難があると思ったので．

>>18にある通りプログラムの引数と出力例を出してもらえるのが一番良いのですが，
それが出来るなら最初からそうしているのでは？とも考えられますし．
（例：これが実は課題ではなくトピ主の思いつきだった場合）

間違えなく課題でしょ･･･
仕事や趣味でやる人間ならGUIで回路図作れるようにして結果を求められるくらい
こだわらないとコード書いていて面白くないし。

論理回路に対する入力じゃなくて
プログラムに対する入力はどんな形式なんでしょう？

例えば
-------------------------------------------------
入力ゲート:P1 P2 P3 P4 P5 ・・・・・・ Px
論理ゲート:and or nand nor exor exnor
こんな入力用文字列を定義して

プログラムへの入力例：
(((P1 and P2) or ((P3 nand P4) nor P5)) exor P6) exnor P7
↑
この文字列を解析して確率を計算できるプログラムを作れば
仕様に合うのかしら？
-------------------------------------------------

トピ主が将来プログラマにならない事を祈るばかりだ･･･

括弧の解釈とかメンドイしポーランドで十分

答えがわかりませんと言う学生のかなりの部分は実は答えではなくて問題を理解していない。
問題が何を問うているのかを解説して理解させた時点で、あとは教えなくても答えを思いつく→1〜2割割
それまでの勉強をさぼりすぎて問題を理解できるレベルに達していない→３〜４割
てな感じか？

たとえば、「任意の論理回路」ってのが実は先生の書いた問題文では「任意の組み合わせ回路」と書いてあった、なんてオチだったりしない？。

質問者がプロフィールでウソをついていなければ大学3〜4年生だから、そんな難しい課題のわけないんだけどな。大学院生だったら、「ランダムなテストパターンと機能カバレッジを利用したシステムＬＳＩの論理回路機能検証」・・・とかいった課題に取り組まされている可能性もあるけど。

エラーチェックなし、骨組みだけ。

#include <stdio.h>

enum {cmd_and, cmd_or, cmd_p, cmd_end};
int sp;
int s[1000];
int push(int i) { return s[sp++] = i; }
int pop(void) { return s[--sp]; }

int circuit(int i, int *cmd)
{
  int n, *c = cmd;
  while (*c++ != cmd_end);
  for (c--, sp = 0; c >= cmd; c--) {
    switch (*c) {
      case cmd_p:
        n = *(--c);
        push((i >> (n - 1)) & 1);
        break;
      case cmd_and:
        push(pop() & pop());
        break;
      case cmd_or:
        push(pop() | pop());
        break;
    }
  }
  return pop();
}


int main(int argc, char* argv[])
{
  int v;
  int cmd[1000];
  int *c = cmd;
  int i, h, n, np;
  char *p;
  double r;

  if (argc < 4) {
    fprintf(stderr, "usage: %s AND P1 OR P2 P3...\n", argv[0]);
    return 1;
  }
  np = 0;
  while (--argc) {
    if (!strcmp(*(++argv), "AND")) {
      *c++ = cmd_and;
    } else if(!strcmp(*argv, "OR")) {
      *c++ = cmd_or;
    } else if(**argv == 'P') {
      v = (int) strtol(*(argv) + 1, &p, 0);
      if (!*p && v > 0) {
        *c++ = v;
        *c++ = cmd_p;
        if (v > np) np = v;
      } else {
        fprintf(stderr, "invalid port number\n");
        return 1;
      }
    } else {
      fprintf(stderr, "unknown command\n");
      return 1;
    }
  }
  *c = cmd_end;
  for (i = 0, h = 0, n = 1 << np; i < n; i++) h += circuit(i, cmd);
  r = (double) h / n;
  printf("%f\n", 1 - r);
  printf("%f\n", r);
  return 0;
}

>ただださん

このプログラムだと(読み違いでなければ)入力の重複を許す論理ゲートのツリーしか表現できませんね。

論理ゲートの重複、たとえば論理ゲートAの出力が、論理ゲートBと論理ゲートCの入力につながっているような場合はどう表現しますか？

あと、かなりの方が誤解されているようですが、

「論理ゲートごとの０と１の確率」というのは、

「n個の論理ゲートで作られた論理回路では、n組の確率を出力する」の意味で間違いないと思います。

皆さん真面目にトピ主のことを心配していらっしゃるようで反省しています。

こんなところでしょうか？

>>0: 入力を０(１)となる確率と論理回路全体を示すものとし、
>>4: 入力は０（１）となる確率のみでした。
>
>で、「論理回路全体を示すもの」は入力できなくなった上、

「入力」を(コマンドラインを含む)コンソールやファイルからの入力と仮定して、

>>0: 論理ゲート毎にコードを書き直すことはしません。
>>4: 任意の論理回路でも対応できるようなものにしなくてはならない
>
>なので、後はプログラムに回路図を「念」で送るしかありません… (^_^;

コードを書き換えてはいけない⇒データなら書き換えてよい、と解釈すると、

「論理回路全体を示すもの」はプログラム中にデータとして持たせることはできる。
ただし、論理回路が変わってもデータ以外のプログラム構造を変更してはいけない。

================================
#include <stdio.h>

enum node_type {IN,NOT,AND,NAND,OR,NOR,EXOR,EXNOR};

struct port {
　enum node_type type;
　double p0;
} ports[] = {
　{IN,0.5},
　{IN,0.5},
　{IN,0.5},
　{IN,0.5},
　{IN,0.5},
　{IN,0.5},
　{IN,0.5},
　{IN,0.5},
};

/* syntax sugar */
#define P(n) ((struct gate *)&ports[n])
#define G(n) (&gates[n])
#define port_num(x) ((struct port *)(x) - ports)

struct gate {
　enum node_type type;
　int num_inputs;
　struct gate *input[8];
} gates[] = {
#include "logic-circuit"
};

long in_stat;

int gate_status(struct gate *gate)
{
　int i, j;
　if (gate->type == IN) {
　　i = port_num(gate);
　　return in_stat >> i & 1;
　}
　j = gate_status(gate->input[0]);
　for (i = 1; i < gate->num_inputs; i++) {
　　switch (gate->type) {
　　case AND:
　　case NAND:
　　　j &= gate_status(gate->input[i]); break;
　　case OR:
　　case NOR:
　　　j |= gate_status(gate->input[i]); break;
　　case EXOR:
　　case EXNOR:
　　　j ^= gate_status(gate->input[i]); break;
　　}
　}
　return j ^ (gate->type & 1);
}

int main(int argc, char *argv[])
{
　int i, j;
　int num_inputs=0, num_stats;

　for (i = 0; i < sizeof(gates)/sizeof(gates[0]); i++) {
　　for (j = 0; j < gates[i].num_inputs; j++) {
　　　if (gates[i].input[j]->type == IN) {
　　　　int n = port_num(gates[i].input[j]);
　　　　if (n > num_inputs) num_inputs = n;
　　　}
　　}
　}
　num_inputs++;
　num_stats = 1 << num_inputs;

　for (i = 0; i < sizeof(gates)/sizeof(gates[0]); i++) {
　　double op = 0.0;
　　for (in_stat = 0; in_stat < num_stats; in_stat++) {
　　　double p = 1.0;
　　　for (j = 0; j < num_inputs; j++) {
　　　　if (in_stat >> j & 1)
　　　　　p *= 1-ports[j].p0;
　　　　else
　　　　　p *= ports[j].p0;
　　　}
　　　if (gate_status(&gates[i])) op += p;
　　}
　　printf("gate%d: p0=%f p1=%f\n",i,1-op,op);
　}

　return 0;
}
================================

で、"logic-circuit" の中身はこんな感じです、

鰻さん回路1
/*G0*/ {OR,2,G(1),G(2),},
/*G1*/ {AND,2,P(0),P(1),},
/*G2*/ {AND,2,P(2),P(3),},

鰻さん回路2
/*G0*/ {OR,2,G(1),P(2),},
/*G1*/ {AND,2,P(0),P(1),},

2入力NANDゲード4つを使って作ったEXOR
/*G0*/ {NAND,2,G(1),G(2),},
/*G1*/ {NAND,2,G(3),P(0),},
/*G2*/ {NAND,2,G(3),P(1),},
/*G3*/ {NAND,2,P(0),P(1),},

とりあえず、回路全体、各ゲート共に8入力までの任意の組み合わせ論理回路には対応できるはず。
#「『任意の論理回路』のはずがない」という点でおおむね意見は一致しているようですから

エラーチェックは一切なし。例えば回路中にループ／閉路があるとスタックをひたすら食いつぶします。

>２−１）各入力に対して、０（１）となる確率は１/２とします。
とは矛盾しているのですが、

>入力は０（１）となる確率
を「(プログラムの)入力は(論理回路のそれぞれの入力が)０（１）となる確率」と想定して、準備だけはしてあります。

# 個人的には入力ノードの処理部分がまだ気持ち悪いのですが、プロトタイプということで… (^_^;

>34
なるほど。このコードを見た後に初心に戻ってお題を読むと、一番それっぽいですね。それにしても、本当にこんなレベルを課されているのだろうか･･･

>35 ただださん
「『論理回路全体を示すもの』を外から入力してもよい」はきっとあったはず。
「制限を設けてもよいが、可能なら100入力や200入力であろうと対応できるように」も、もしかしたらあったのかも。

もっとも、そんな回路をこのプログラムに食わせたら、生きているうちには結果は得られませんけど。

まさかそれを体感させるのが課題の最終目的とか？

宿題丸投げのコミュか何かあった気がするんだけど・・・
なんでそっちを利用しないのかな。

大学の、しかも院生さんなんですよね？
とりあえず、所属されている北九州市立大学にでも連絡して差し上げてみては如何でしょう？

出題されているかたが、こういった「丸投げ」を是としているのであれば、それはそれで…とは思いますが。

>大学の、しかも院生さんなんですよね？

職業欄の選択肢が「大学生・院生」しかないからだと思います。
#30 saitohさんがおっしゃっておられるように、年齢からするとまだ大学生。

そういえば、利用規定によれば15歳以上となっているのに、「高校生」が無いのはなぜなんでしょう？

昔読んだ時には18歳以上になっていた記憶はあるのですが…

課題の提出期限切れてる気がするんだが