最小回数で応答を得るには
- 送信側が得られる受信の情報は、関数ask(・)から返される値である。
- 送信側は、受信側4人それぞれの情報を獲得したい。
- 送信側は最小何回で受信側A～Dのそれぞれの情報を知ることができるか？
- ベストアンサー
最小回数で応答を得るには
次のような問題を考えます。 送信側：1人，受信側：4人（A，B，C，D）いる。 送信側は、受信側4人それぞれの情報を獲得したい。 受信側は、応答として、0、1で返答し、1がYES、0がNoを表すものとする。 送信側が得られる受信の情報は、関数ask(・)から返される値である。 関数ask(・) 入力：4人のだれに聞くか N1,N2,N3,N4（例：N1=1,N2=0,N3=1,N4=0）1で聞く，0で聞かない 出力：入力で指定した受信側の応答のOR情報（一人でもYESだったら、1が返される） 但し、1回目：A，2回目：B，3回目：C，4回目：Dという聞き方はなしとし、初回は4人全員に聞く ものとする。 いま、A=1，B=1，C=1，D=1であるとして、送信側は最小何回で受信側A～Dのそれぞれの 情報を知ることができるか？ いま、自分が考えている方法は、 1回目：入力 N1=1、N2=1、N3=1、N4=1（対象全員） 出力 1 送信側は、4人のだれかがYESと言っていることを確認。 2回目：入力 N1=1、N2=1、N3=0、N4=0（対象A,B） 出力 1 送信側は、4人のうち、A,BがYESと言っていることを確認。 しかし、そうなると、C,DもYESの可能性がある。 3回目：入力 N1=0、N2=0、N3=1、N4=1（対象C,D） 出力 1 送信側は、4人のうち、C,DがYESと言っていることを確認。 4回目：入力 N1=0、N2=1、N3=1、N4=0（対象B,C） 出力 1 送信側は、4人のうち、B,CがYESと言っていることを確認。 5回目：入力 N1=1、N2=0、N3=0、N4=1（対象A,D） 出力 1 送信側は、4人のうち、A,DがYESと言っていることを確認。 ですが，あまり効率的であると思えません。ORをとっているので、上記でもし、1回目に1、 2回目に0が返されれば、3回目以降は、C,Dのみに聞けばよいと思い、この方法にしましたが、 A～D全員が1である状況なので、この方法では効果がないと感じています。 実際には、A～Dは4人より多い場合も想定できるようにしたいですが、今回は 擬似的な問題として、上記のような問題を考えています。 何か他によい方法はないでしょうか？ ご教授頂きたくお願い申し上げます。
- nnsvm
- お礼率16% (39/239)
- 数学・算数
- 回答数5
- ありがとう数2
- みんなの回答 （5）
- 専門家の回答
質問者が選んだベストアンサー
関数ASK(*)がORで値を返すかぎり、複数に問い合わせるなら人数分以上の回数聞く必要があると思いますし、不定（決まらない）ことが起こります。 例示されているシーケンスだと１回目（全員に聞く）は、2回目以降に影響を与えないため不要と思われますが、例示の問い合わせだけではＡ～Ｄの送信を確認できていません。 例えば、２回目はＡＢ両者がＹＥＳではなくＡ，ＢまたはＡＢがＹＥＳです。例えばＡがＮＯ（Ａ＝０、Ｂ＝１、Ｃ＝１、Ｄ＝１）でも例示の方法では全てＹＥＳが帰ってきます。（ＡorＢ＝１、ＣorＤ＝１、ＢorＣ＝１，ＡorＤ＝１） このケースでは、Ａ以外が１のためＯＲで複数に聞くとＡの送信内容が判りません。 同様にＡ＝Ｃ＝０、Ｂ＝Ｄ＝１でもＡＣ以外の組み合わせではORは全て１が帰ってきます。 したがって、効率的な検索方法以前に関数ASK_AND(*)のようなANDで値を返すものを合わせて用意する必要があると思います。（複数同時に聞くという条件を満たすため） 以下、ＡＮＤ/ＯＲが実装されたとした場合・・・・ もし、一人ずつ聞くより同じか少ない回数でＡ～Ｄの状態をOR等の関数を使うことで知ることができるか？ということならできないと思います。（ＡＮＤとＯＲの回答がまとめて１回で聞けても個別情報を分離するのに人数より多い回数を必要としそうです） ＡＢＣＤが１０１０のケースだと １）ＡＢ：ＡＮＤ＝０，ＯＲ＝１ ２）ＢＣ：ＡＮＤ＝０、ＯＲ＝１ ３）ＣＤ：ＡＮＤ＝０、ＯＲ＝１ ４）ＡＤ：ＡＮＤ＝０、ＯＲ＝１ ５）ＡＣ：ＡＮＤ＝１、ＯＲ＝１ Ａ＝Ｃ＝１が確定 ６）ＢＤ：ＡＮＤ＝０、ＯＲ＝０ Ｂ＝Ｄ＝０が確定 ＢＤという問い合わせとＡＣという問い合わせの組み合わせがあるまで確定できない ３つ以上合わせて聞いても全てが同じという幸運を期待するもので無い限り、回数を減らすためとしては聞く意味がないと思われます。 例えば上記の例で、どの３つの組み合わせの問い合わせを入れても任意の２つ以上の問い合わせと交換することができない（等価ではない）です。（例えば、ＡＢＣという問い合わせと＃５，＃６と入れ替えられない。ＡＢＣＤ＝０１０１でもＡＢＣＤ＝１０１０と同じ返り値） 以上は、普遍的に１００％判別するのに必要な最小問い合わせ数（最悪のケース）の話であって、現実の運用では聞く順番を入れ替えるとそれより少ない回数でできることもあります。上記の例だと＃５，＃６と２回聞けば答えがわかります。（ＹＥＳ，ＮＯが３つ有るようなケースだと３回、全てＹＥＳかＮＯなら２回）これらを考慮しても平均は大体４回ちょっとになりそうですね。
その他の回答 (4)
- stomachman
- ベストアンサー率57% (1014/1775)
A,B,C,Dの答がYESなのかNOなのかを(1=YES, 0=NOとして)<Aの答 Bの答 Cの答 Dの答>と表しますと、 <0000> <0001> <0010> ... <1111> の16通りあります。また質問の仕方を(N1 N2 N3 N4)で表しますと、これは (0001) (0010) ... (1111) の15通り。 16通りの答がどれも同じ確率p=1/16で生じると仮定すると、そのうちの一つが選ばれるという事象の持つ情報量は、どの答が実現した場合でも4 Shannonです(4 = -log p ただしlogの底は2)。また、質問の仕方をどう工夫しても、YESかNOかの1bitしか出力がないのだから、1回の質問で得られる情報量は1 Shannon以下です。(情報量が1 Shannonになるのは、YESとNOがどちらも確率1/2になるように質問を選んだ場合。）質問回数をnとすれば、得られる情報量はn Shannon以下ということです。 なので、「16通りの答がどれも同じ確率で生じる」という仮定の下では、どんなに上手に質問しても、質問回数の期待値を4未満にすることは不可能です。 一方、16通りの答が生じる確率に偏りがある場合には、情報量の平均値 -Σp[j] log p[j] (logの底は2、Σはj=<0000>～<1111>についての総和） が4未満になりますから、質問の仕方を工夫することで質問回数の期待値を4未満にできる可能性があります。 ところで、<1111>, <0111>, <1011>, <1101>, <1110> の5つがどれも発生確率p＞0である場合、質問回数は4以下になりません。なぜなら、<1111>と<0111>を比べてみると、質問(1000)に対しては出力が違いますが、他のどんな質問に対しても出力が同じになります。だから、<1111>と<0111>を区別するためにはどうしても質問(1000)をする必要があります。同様に <1111>と<1011>を区別するためには質問(0100) <1111>と<1101>を区別するためには質問(0010) <1111>と<1110>を区別するためには質問(0001) が必要です。言い換えれば「<1111>ではない」と断言するだけのために、少なくとも4回の質問(1000)(0100)(0010)(0001)が不可欠です。
- nag0720
- ベストアンサー率58% (1093/1860)
＃２、＃３で指摘されているとおり、OR情報だけでは４人の情報を確定することはできません。 では、＃３さんの提案したORとANDの両方を受信できるとした場合はどうかというと、 「初回は4人全員に聞くものとする」という条件のもとでは最大５回、その条件がなければ最大４回で十分です。 考え方は、 例えばA=1,B=0,C=1,D=0のケースを単に1010と書くことにすると、 ４人の状態は、0000,0001,0010,0011,0100,・・・・,1111の１６通りあります。 一方、質問の仕方は、個別質問を除くと11通りあり、 受信のパターンは、OR=0,AND=0、OR=1,AND=0、OR=1,AND=1の３通りあります（OR=0,AND=1はありえない）。 初回に4人全員に聞くと、 OR=0,AND=0 → 0000 OR=1,AND=0 → 0001,0010,0011,・・・,1110 の14通り OR=1,AND=1 → 1111 のケースに分かれます。 最悪の回答を想定してOR=1,AND=0となった場合、２回目の質問の対象をABにすると、 OR=0,AND=0 → 0001,0010,0011 OR=1,AND=0 → 0100,0101,0110,0111,1000,1001,1011,1011 OR=1,AND=1 → 1100,1101,1110 同様に最悪の回答を想定してOR=1,AND=0となった場合、３回目の質問の対象をCDにすると、 OR=0,AND=0 → 0100,1000 OR=1,AND=0 → 0101,0110,1001,1011 OR=1,AND=1 → 1100,1011 というように常に最悪の回答になった場合のケース数が少なくなるように質問していけば５回で確定できます。 初回に４人全員に聞くという条件がなければ４回で十分です。 ５人以上の場合でも、人数分の回数で確定できるでしょう。 １回の質問でORかANDの片方しか受信できないとした場合は、初回に4人全員に聞くという条件があっても８回で確定できます。
- gohtraw
- ベストアンサー率54% (1630/2966)
だれか一人がＮＯの場合（例えばＡとします）でも 全員⇒出力は１ ＡとＢ⇒ＢはＹＥＳなので出力は１ ＣとＤ⇒出力は１ ＢとＣ⇒出力は１ ＡとＤ⇒ＤはＹＥＳなので出力は１ となるので全員ＹＥＳの場合と区別できません。
- Cupper-2
- ベストアンサー率29% (1342/4565)
最小回数ですか。 １回 入力：N1=1,N2=1,N3=1,N4=1 出力：０ 返事がない。まるで屍のようだ…以上！ こんなケースも考える必要があります。
関連するQ&A
- AIZU ONLINE JUDGEについて
明らかに正常なコードなのに答えが間違っているとされます。 #include<stdio.h> int main(void) { int a, b, c, N, i; scanf("%d",&N); for (i = 0; i < N; i++) { scanf("%d %d %d", &a, &b, &c); int A = a*a; int B = b*b; int C = c*c; if ((A + B == C) || (B + A == C )|| (C + A == B)) { printf("YES\n"); } else { printf("NO\n"); } } return 0; } これはvisual studio では通りました。 ちなみにこのコードは自分のものと酷似していますが、これはAIZU的にはOKだそうです。 #include <stdio.h> int main(void) { int a, b, c, n, i; scanf("%d",&n); for (i = 0; i < n; ++i) { scanf("%d %d %d", &a, &b, &c); if ((a*a + b*b == c*c) || (b*b + a*a == c*c) ||( c*c + a*a == b*b)) printf("YES\n"); else printf("NO\n"); } return 0; } この違いはなんでしょうか？
- ベストアンサー
- C・C++・C#
- 4-18 研究 高校数学の漸化式
a[1]=2,b[1]=1の時 a[n+1]=2a[n]+5b[n] b[n+1]=a[n]+2b[n]によって定まる分数a[n]/b[n]は√5の近似値であることを示せ 回答 a[n+1]=2a[n]+5b[n] b[n+1]=a[n]+2b[n]という条件から 2a(n+1)-5b(n+1)=4an-5an=-an 5b(n+1)=2a(n+1)+an a[n+2]=2a[n+1]+5b[n+1]=2a(n+1)+2a(n+1)+an a(n+2)=4a(n+1)+an λ^2-4λ-1=0 →λ=2-√5, 2+√5 →α=2-√5, β=2+√5 a(n+2)-αa(n+1)=β{a(n+1)-αa(n)}(1) a(n+2)-βa(n+1)=α{a(n+1)-βa(n)}(2) ふたたび a[n+1]=2a[n]+5b[n]と b[n+1]=a[n]+2b[n]という条件から得られる a[n+2]=2a[n+1]+5b[n+1] を(1)(2)に代入して 2a[n+1]+5b[n+1]-αa(n+1)=β{2a[n]+5b[n]-αa(n)}(1)' 2a[n+1]+5b[n+1]-βa(n+1)=α{2a[n]+5b[n]-βa(n)}(2)' α=2-√5, β=2+√5を代入して 2a[n+1]+5b[n+1]-(2-√5)a(n+1)=β{2a[n]+5b[n]-(2-√5)a(n)}・・・(1)'' 2a[n+1]+5b[n+1]-(2+√5)a(n+1)=α{2a[n]+5b[n]-(2+√5)a(n)}・・・(2)'' (1)''⇔√5a(n+1)+5b[n+1]=β{√5a[n]+5b[n]}・・・(1)''' (2)''⇔√5a(n+1)-5b[n+1]=α{√5a[n]-5b[n]}・・・(2)''' これはともに等比数列の漸化式 わかりにくければ置き換えて c[n]=√5a[n]+5b[n]=√5(a[n]+√5b[n]) d[n]=√5a[n]-5b[n]=√5(a[n]-√5b[n])とおいて (1)'''⇔c(n+1)=βcn・・・(1)'''' (2)'''⇔d(n+1)=αdn・・・(2)'''' [これはともに等比数列の漸化式］ (1)'''',(2)''''をβ^(n+1),α^(n+1)でわれば c(n+1)/β^(n+1)=c(n)/β^n=....=c[1]/β={√5a[1]+5b[1]}/β=(2√5+5)/β =√5(2+√5)/β=√5 d(n+1)/α^(n+1)=d(n)/α^n=....=d[1]/α={√5a[1]-5b[1]}/α=(2√5-5)/α =√5(2-√5)/α=√5 とあったのですが、c(n)/β^n=....=c[1]/βですが何故これらが等しいのですか？ 後最後のd(n+1)/α^(n+1)=d(n)/α^n=....=d[1]/α={√5a[1]-5b[1]}/α=(2√5-5)/α =√5(2-√5)/α=√5 ここからどうやってa[n]/b[n]は√5の近似値であることを示せるのですか？
- ベストアンサー
- 数学・算数
- 至急で、C言語の問題で解答解説お願いします。
１実数を３つ（a,b,c）を読み込み3辺とする三角形ができるか判定（ｄ（d-a)(d-b)(d-c)>0のとき三角形となる）しできなければ、三角形ではありません！というメッセージを表示し、できる場合は以下のヘロンの公式を用いて三角形の面積を求めるプログラムをC言語で答えてください。ｄ＝(a+b+c)/2 s=√{d(d-a)(d-b)(d-c) 2maxの整数値（≧１）をキーボードから入力し、その値に対応した図形を出力するプログラムをC言語で答えてください。 例 max1 max2 max3 * ** *** * ** *** * ** *** ** *** *** 3整数ｎをキーボード入力しｎの値に応じて以下の図形を表示するプログラムをc言語で答えてください。 n=3 n=4 n=5 3 4 5 45 56 67 678 789 89０ 0123 1234 56789 4整数ｎ（≧0)を入力し歯科の計算を実行するC言語プログラムを答えてください。2つの自然数ｎとｍを読み込みｎ個の中からｍ個を取り出すときの組み合わせの数を計算せよ。ただし、n!を計算する関数long fact (int n)を定義し必ずそれを用いること。 ５ １つのscanfで２つの１０進数を入力し８進数と１６進数で表示するプログラムをC言語で答えてください。 ６ 実数aを入力し少数第1位で四捨五入する関数g(a)をマクロ定義で入力した値の少数第1位を四捨五入して出力するプログラムをC言語で答えてください。 ７ ４つの実数w,x,y,zを読み込みその最大値を出力するプログラムをC言語で答えてください。ただし、２つの実数の大きいほうを求める関数 double my may (double x,double y)を定義し、その関数を用い、if文を用いないでｃ言語で答えてください。
- 締切済み
- その他（学問・教育）
- 組み合わせ
aに100、bに20や2を入力すると プログラムが停止します。 計算できるように御指摘お願いします。 以下のプログラムです。 #include<stdio.h> int factrical(int n){ if(n>0){ /*printf("%d\n",n);*/ return (n*factrical(n-1)); } else{ return(1);} } int combination(int n ,int r){ return(factrical(n)/(factrical(n-r)*factrical(r))); } int main (void){ int a,b,c; printf("二つの数を入力してください。\n"); do{ printf("大きい方の数を入力してください。\n"); scanf("%d",&a); scanf("%d",&b); }while(a<b); c=combination(a,b); printf("%d",c); return(0);}
- 締切済み
- 情報工学
- 確率
一個のサイコロをn回振る 1)n≧2のとき、1の目が少なくとも1回出て、かつ2の目が少なくとも1回出る確率 2)n≧3のとき、1の目が少なくとも2回出て、かつ2の目が少なくとも1回出る確率 事象A 1の目が一回も出ない B 2の目が 〃 C 1の目が1回だけ出る ←ここがよくわかりません。少なくとも2回の否定は0 or 1 ではないのでしょうか、それともn≧3のとき、ベン図で考えて1が出ないことはn(A)で考えられているので、Cはこのようになるのでしょうか。 １）A… n回とも2,3,4,5,6の目が出る n(A)=5のn乗 B 1,3,4,5,6 (B)=〃 A∩B 3,4,5,6 (C)=4のn乗 よって 1-n(A)+n(B)-n(A∩B)/n(u)=1-2・5のn乗-4のn乗/6のｎ乗 2)n≧3のとき 1の目が少なくとも2回出て、かつ2の目が少なくとも一回出る確率は 1）と同様に考えて C…n回中、1の目がちょうど1回出て、他のn-1回は2,3,4,5,6の目が出る n(C)=nC1・5のn-1乗＝n・5のn-1乗 B∩C＝n回中、1の目がちょうど一回出て、他のn-1回は、3,4,5,6の目が出る n(B∩C)=nC1・4のn-1乗＝n・4のn-1乗 1-n(A)+n(B)+n(C)-n(A∩B)-n(B∩C)/n(u) =1-(10+n)・5のn-1乗-（4+ｎ）・4のn-1乗/６のn乗 回答お願いします。
- ベストアンサー
- 数学・算数
- 数字の並び換えの最適手順
Ｎ個の異なる数字があります。これを大小の順にならべ換えます。 最適手順数は計算上はＬｏｇ（Ｎ！）／Ｌｏｇ（２）です。 その最適手順の一般化は可能でしょうか。 例１：Ｎ＝４のとき Ａ、Ｂ，Ｃ，Ｄと４個の数字があって １回目 ＡとＢを比較 結果Ａ＞Ｂが判明 ２回目 ＣとＤを比較 結果Ｃ＞Ｄが判明 ３回目 ＡとＣを比較 結果Ａ＞Ｃが判明 ４回目 ＢとＣを比較する Ｂ＞Ｃのときは、Ａ，Ｂ，Ｃ，Ｄとなって並び替え終了。 こういう都合の良い結果での並び換え終了は手順からはずします。 Ｃ＞Ｂのとき ５回目 ＢとＤを比較する Ｂ＞Ｄのとき Ａ、Ｃ，Ｂ，Ｄ で終了 Ｄ＞Ｂのとき Ａ，Ｃ、Ｄ、Ｂ で終了 例２：Ｎ＝５のとき Ａ、Ｂ，Ｃ，Ｄ、Ｅと４個の数字があって １回目 ＡとＢを比較 結果Ａ＞Ｂが判明 ２回目 ＣとＤを比較 結果Ｃ＞Ｄが判明 ３回目 ＡとＣを比較 結果Ａ＞Ｃが判明 ４回目 ＥとＣを比較 ５回目 Ｅ＞ＣのときＥとＡを比較、Ｃ＞ＥのときＥとＤを比較 ６回目 ここから場合わけひどくなります。 例としてＡ＞Ｅ＞Ｃ＞ＤのときＢとＣを比較 ７回目Ｂ＞ＣのときＢとＥを比較、Ｃ＞ＢのときＢとＤを比較 例３：Ｎ＝６であれば１０回、Ｎ＝７であれば１３回でした。 これらはＮ＝５の手順のあと６個目、７個目の位置決めするだけ。
- 締切済み
- 数学・算数
- サイコロをｎ回振ったときの最大・最小目
サイコロをｎ回振った時、最大値をa、最小値をbとする（a＞b） 最大値がaとなるのは、ｎ回ともa以下の目が出る場合から ｎ回とも(a-1)以下の場合を引けばよい よって最大値がaとなる確率は｛a^n - (a-1)^n}/6^n 最小値がbとなるのは、ｎ回ともb以上の目が出る場合から ｎ回とも(b+1)以上の場合を引けばよい よって最小値がbとなる確率は｛(6-b+1)^n - (6-b)^n}/6^n ここで最大値がaかつ最小値がbとなる確率は ｎ回とも(b,b+1,b+2,・・・,a)の場合から、ｎ回とも(b,b+1,b+2,・・・,a-1)の場合と ｎ回とも(b+1,b+2,・・・,a)の場合を除けばよい A：ｎ回ともb～a B：ｎ回ともb～a-1 C：ｎ回ともb+1～a とすると求める確率はP(A)-P(B∪C） P(B∪C)=P(B)+P(C)-P(B∩C) B∩C：ｎ回ともb+1～a-1であるから P(B∪C)=｛2(a-b)^n - (a-b-1)^n}/6^n 以上より求める確率は {(a-b+1)^n + (a-b-1)^n -2(a-b)^n}/6^n としたのですがこれは正しいのでしょうか？ どなたか添削お願いします。
- ベストアンサー
- 数学・算数
- 五の四 高校数学の場合の数です
1から2nまでの2n個の整数がある 次の二つの性質(A),(B)をもつ4つの整数a,b,c,dをこの2n個の整数から選ぶ選び方は何通りあるか、ただしn>=2とする（A)1<=a<b<c<d<=2n (B)a+d=b+c 回答d-aを固定してkは自然数として(1)d-a=2k+1のときはa,dの決め方はa=1～2n-(2k+1)の2n-(2k+1)通りでb,cの決め方はk通り (2)d-a=2(k+1)のときはa,dの決め方がa=1～2n-2(k+1)の2n-2(k+1)通りでb,cの決め方はk通り したがって求める場合の数はΣ[k=1→n-1]{2n-(2k+1)}k+Σ[k=1→n-1]{2n-2(k+1)}k =Σ[k=1→n-1]{(4n-3)k-4k^2}=n(n-1)(4n-5)/6 (注）(B)は数直線上でaとdの中点とbとcの中点が同じという条件でこの中点の位置を固定するのがよく例えばn=4のとき中点が3.5と4の場合は各3C2通り、中点が5.5と5の場合も各3C2通りと考えて 4Σ[k=3→n](k-1)C2+nC2=4×nC3+nC2 となっていたのですがまず(1)と(2)でd-a=2k+1とd-a=2(k+1)の場合で分ける理由がわかりません a,dの決め方が(1)でa=1～2n-(2k+1)の2n-(2k+1)通り、(2)でa=1～2n-2(k+1)の2n-2(k+1)通りとなるのもよくわからないです (1)と(2)でb,cの決め方はk通りと同じになるのも何故なのかわかりません Σ[k=1→n-1]{2n-(2k+1)}k+Σ[k=1→n-1]{2n-2(k+1)}kとかのkがn-1までなのが何故なのかわかりません 注の所はn=4の時2n＝８ですから中点って4.5じゃないんですか？何故3.5と4の場合とか5.5と5の場合とかで考えるのがわからないのと3C2というのが何で出てくるのかと最後の4Σ[k=3→n](k-1)C2+nC2=4×nC3+nC2見たいな式が何で出てくるのか、とにかくサッパリわかりません
- ベストアンサー
- 数学・算数
