2537.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"stdio.h"

double ans[100][10];

int main()
{
	int k,n,i,j;
	double s,answer;

	while( scanf( "%d %d", &k, &n ) == 2 )
	{
		
		for( s=1,i=0; i<n; i++ )
			s *= (k+1);

		for( j=0; j<=k; j++ )
			ans[0][j] = 1/s;

		for( i=1; i<n; i++ )
		for( j=0; j<=k; j++ )
		{
			ans[i][j] = ans[i-1][j];
			if( j ) ans[i][j] += ans[i-1][j-1];
			if( j<k ) ans[i][j] += ans[i-1][j+1];
		}
		
		answer = 0;
		for( j=0; j<=k; j++ )
			answer += ans[n-1][j];

		printf( "%.5lf\n", answer*100 );
	}

	return 0;
}