题目描述
Problem B: Tight words
Given is an alphabet {0, 1, … , k}, 0 <= k <= 9 . We say that a word of length n over this alphabet is tight if any two neighbour digits in the word do not differ by more than 1.
Input is a sequence of lines, each line contains two integer numbers k and n, 1 <= n <= 100. For each line of input, output the percentage of tight words of length n over the alphabet {0, 1, … , k} with 5 fractional digits.
输入
暂无
输出
暂无
样例输入
4 1
2 5
3 5
8 7
样例输出
100.00000
40.74074
17.38281
0.10130
参考代码
#include <stdio.h>
double x[100][10];
double s;
main()
{
int i,j,k,n;
while (2 == scanf("%d%d",&k,&n))
{
k++;
for (i=0;i<n;i++) for (j=0;j<k;j++) x[i][j] = 0;
for (i=0;i<k;i++) x[0][i] = 100.0/k;
for (i=1;i<n;i++)
{
for (j=0;j<k;j++) x[i][j] += x[i-1][j]/k;
for (j=1;j<k;j++) x[i][j] += x[i-1][j-1]/k;
for (j=0;j<k-1;j++) x[i][j] += x[i-1][j+1]/k;
}
for (s=i=0;i<k;i++) s += x[n-1][i];
printf("%0.5lfn",s);
}
}
解析
暂无
