2013
12-11

# Uva-11021-Tribles-概率计算[解题报告]C++

### Tribbles

You have a population of k Tribbles. This particular species of Tribbles live for exactly one day and then die. Just before death, a single Tribble has the probability Pi of giving birth to i more Tribbles. What is the probability that after m generations, everyTribble will be dead?

Input
The first line of input gives the number of cases, NN test cases follow. Each one starts with a line containing n (1<=n<=1000),k (0<=k<=1000) and m (0<=m<=1000). The next n lines will give the probabilities P0P1, …, Pn-1.

Output
For each test case, output one line containing “Case #x:” followed by the answer, correct up to an absolute or relative error of 10-6.

 Sample Input Sample Output 4 3 1 1 0.33 0.34 0.33 3 1 2 0.33 0.34 0.33 3 1 2 0.5 0.0 0.5 4 2 2 0.5 0.0 0.0 0.5 Case #1: 0.3300000 Case #2: 0.4781370 Case #3: 0.6250000 Case #4: 0.3164062 

ans[i] = P[0] + P[1] * ans[i-1] + P[2]*ans[i-1]^2 + P[3] * ans[i-1]^3 + … + P[n-1]*ans[i-1]^n-1

//============================================================================
// Name        : uva_11021.cpp
// Author      : coder
// Version     :
// Description : 概率计算 结合 递推公式, Ansi-style
//============================================================================
#include <stdio.h>
#include <math.h>
int c,n ,k, m;
const int M = 1001;
double parr[M], ans[M];
int main() {
//freopen("in.txt", "r", stdin);
scanf("%d", &c);
for(int i=1; i<=c; i++){
scanf("%d%d%d", &n, &k, &m);
for(int j=0; j<n; j++) scanf("%lf", &parr[j]);
ans[0] = 0;
ans[1] = parr[0]; //一个都不生的概率 即 第一天全部死亡
for(int j=2; j<=m; j++){
ans[j] = 0;
for(int l=0; l<n; l++)
ans[j] += parr[l] * pow(ans[j-1], l);
}
printf("Case #%d: %7lf\n", c, pow(ans[m], k));
}
return 0;
}

1. […] 如果此题没有要求 相对位置不变，可以参考文章：http://www.acmerblog.com/interview-9-2427/ […]