コインの表裏の問題について

Question

c言語です！
コインをn回振った時に、連続した表の最大数がm
回以上の確率を書き出せ。
n=4の出力を、提出するソースコードの末尾に注釈として挿入せよ。

例)n=3の時
m, m回以上連続で表となる確率
0, 100.0%
1, 87.5%
2, 37.5%
3, 12.5%

という問題が出たのですがどなたか教えていただきたいです。
手も足も出ないです。。

Comments

[fana]

> c言語です！

であれば質問のタグもCにすべき．

[fana]

nの値の範囲に条件が設けられていたりしますか？
それとも，そういう条件とかは全くなくて，例えば「n=7億回」とか言われたら7億と1行の出力をしろ，という話なのですか？
（※てきとーにふざけてるとかじゃなくて，それ次第で取り得るアプローチが違ってくる可能性がありそうだから尋ねているんだよ）

[ionto369]

ｎの範囲は設けられていません。

[fana]

（…となると，頑張ってパターンを列挙して数えるような方法だとダメなのかも．何らかの計算でぱぱっとできる方法が存在するってことなのかな？）

[jimbe]

本当に手も足も出ないのでしょうか。
main 関数は書けませんか?
n=0 の時だけの表示は出来ませんか?
n=1 の時だけはどうでしょうか?
組み合わせて n=4 までを if で分岐させて表示することは?

とりあえず幾つかの固定状態を作って見て、そこからルールを見出すというのも方法です。

Answer 1

数学的性質を利用した解だとこうなると思います。

#include <stdio.h>

double coin(int n, int m) {
    if (m == 0) return 1;
    int pattern = 1 << n;
    int count = (2 << (n - m)) - 1;
    return (double)count / pattern;
}

int main(void) {
    int n = 4;
    for (int i = 0; i <= n; ++i) {
        printf("%d, %1.2f%%\n", i, 100 * coin(n, i));
    }
}

Comments

[fana]

実行してみたら n=4,m=2 の値が 43.75% と表示されましたが，これって違くないですか？
全16パターンを手作業で分類すると
0 : 1パターン
1 : 7パターン
2 : 5パターン
3 : 2パターン
4 : 1パターン
なので，m=4,n=2 のときは 100.0*(5+2+1)/16 = 50[%] ではないでしょうか．

Answer 2

簡単にDFS解を示しておきます．

#include <stdio.h>
#include <stdlib.h>

int max(int a, int b) {
    return a > b ? a : b;
}

void dfs(int n, int depth, int cnt, int mx_cnt, int bin, int *M) {
    if (n == depth + 1) {
        for (int i = 0; i <= mx_cnt; ++i) M[i]++;
        return ;
    }
    dfs(n, depth + 1, 0, mx_cnt, 0, M);
    dfs(n, depth + 1, (bin ? cnt : 0) + 1, max(mx_cnt, (bin ? cnt : 0) + 1), 1, M);
}

int main(void){
    int n = 4;
    int *M = (int*)calloc(sizeof(int), n + 1);
    dfs(n, 0, 0, 0, 0, M);
    dfs(n, 0, 1, 1, 1, M);
    for (int i = 0; i <= n; i++) {
        printf("%d, %.1lf\n", i, 100.0 * M[i] / (1 << n));
    }
    return 0;
}

見てわかる通り，時間/空間計算量共にO(2^N)です．

これがもし学校の課題である場合，教師側としては掛け算も習ってない小学生が掛け算をいきなり使い出したみたいな気分になると思うので，ちゃんと自力で書かれることを推奨します．

コメントでjimbeさんがおっしゃている通り，if文を使って順に

• n = 0におけるm = 0のとき
• n = 1におけるm = 0のとき，m = 1のとき
• n = 2におけるm = 0のとき，m = 1のとき，m = 2のとき
• n = 3におけるm = 0のとき，m = 1のとき，m = 2のとき，m = 3のとき
• n = 4におけるm = 0のとき，m = 1のとき，m = 2のとき，m = 3のとき，m = 4のとき

のようにして全列挙し，法則性を探して解析を進めることが大事です．

おそらく問題の出題意図はこの「全列挙し，法則性を探して解析をできるかどうか」にあると思われます．残念ながら私の回答は出題者の意図に沿わないものになっている可能性があること注意してください．

Answer 3

ありそうなビット扱い。 N は longビット数まで。

#include <stdio.h>

#define N 4

int longestSequenceOf1(long v) {
  int max = 0;
  for(int c=0; v>0; v>>=1) if(v&1) max=max<++c?c:max; else c=0;
  return max;
}
void research(long *a, long vmax) {
  for(int v=0; v<vmax; v++) {
    int max = longestSequenceOf1(v);
    for(int i=0; i<=max; i++) a[i]++;
  }
}
int main(void){
  long vmax = 1 << N;
  long a[N+1] = {0};
  research(a, vmax);
  printf("m, m回以上連続で表となる確率\n");
  for(int i=0; i<=N; i++) printf("%d, %.1f%%(%ld)\n", i, 100.0*a[i]/vmax, a[i]);
}

m, m回以上連続で表となる確率
0, 100.0%(16)
1, 93.8%(15)
2, 50.0%(8)
3, 18.8%(3)
4, 6.2%(1)

Answer 4

nの値が小さいなら，全パターンを調べてカウントすれば良いかと…
（↓のコードはとりあえず n=0,1,2,3,4 では動作テストしました）

int Next( unsigned char *Ptn, size_t n )
{
	for( size_t i=0; i<n; ++i )
	{
		if( Ptn[i]==0 ){	Ptn[i]=1;	return 1;	}
		Ptn[i] = 0;
	}
	return 0;
}

int Count( unsigned char *Ptn, size_t n )
{
	int c = 0;
	int r = 0;
	for( size_t i=0; i<n; ++i )
	{
		if( Ptn[i] )++c;
		else
		{
			if( r<c )r=c;
			c = 0;
		}
	}
	return ( r<c ? c : r );
}

void Test( size_t n )
{
	printf( "0 : 100%%\n" );
	if( n == 0 )return;

	size_t *Counter = (size_t*)calloc( sizeof(size_t), n );
	unsigned char *Ptn = (unsigned char*)calloc( sizeof(unsigned char), n );

	while( Next( Ptn, n ) )
	{
		++Counter[ Count(Ptn,n)-1 ];
	}

	for( size_t i=0; i<n-1; ++i )
	{
		for( size_t k=i+1; k<n; ++k )
		{	Counter[i] += Counter[k];	}
	}

	double nAllPtn = pow( 2.0, n );
	for( size_t i=0; i<n; ++i )
	{
		printf( "%u : %f%%\n", unsigned int(i+1), 100*Counter[i] / nAllPtn );
	}

	free( Ptn );
	free( Counter );
}

int main(void)
{
	Test( 4 );
	return 0;
}

ただ，問題について私が確認のために問うたところ，

nの値の範囲に条件が設けられていたりしますか？
それとも，そういう条件とかは全くなくて，例えば「n=7億回」とか言われたら7億と1行の出力をしろ，という話なのですか？

という問いに対して，

ｎの範囲は設けられていません。

とのことですので，こんな方法だとどこかで限界がくるだろうと思います．

Comments

[fana]

あと，出力がてきとーに printf( "%f" ); になってるので，これだと

> 1, 87.5%

みたく，必要な桁だけが出力される形にはならない（ "87.50000" という形になる）．

[fana]

（こんな「数える」話じゃなくて，ちゃんと確率がどうのこうのいう数学な方法でやれや，という話なのだろうと思うけど……そっちは手も足も出ないっす…）