首页 > ACM题库 > UVA > Uva-11021-Tribles-概率计算[解题报告]C++
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
 

题意:

有k只兔子,每只活一天就会死亡。每只在临死前生出i只的概率为P[i].

由于每只兔子是独立的,只需求一开始只有一只,m天后全部死亡为 ans[m]. 则最终结果为 ans[m]^k

根据递推关系:

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     :
// Copyright   : www.acmerblog.com
// 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/ […]

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。