杰 & C++ & Python & DM

POJ Scout YYF I 解题报告

/*
*   Pro(i)表示不遇到雷的情况下,到达i步的几率,那么
*       Pro(n) = Pro(n-1) * p + Pro(n-2) * (1-p)
*   首先求递推公式,由特征方程 x^2 - p*x -(1-p) = 0 求得特征根: p-1 和 1
*   所以Pro(n) = C1 + C2*(p-1)^n
*   将Pro(1)=1 Pro(2)=p代入,求得待定系数C1 = -1/(p-2), C2 = 1/(p-2)
*   故Pro(n) = -1/(p-2) + 1/(p-2)^n
*
*   假设在位置k首次遇到雷,那么到达位置k-1的几率是 Pro(k-1)
*   经过雷后存活的几率是 Pro(k-1) * (1-p)
*   将这个值即为a
*   
*   假设又经过t步第二次遇到雷,那么到达t-1步的几率是 a*Pro(t-1)
*   经过雷后存活的几率是 a * Pro(t-1) * (1-p)
*
*   以此类推
*/

#include <iostream>
#include 
<algorithm>
#include 
<cmath>
using namespace std;

int main()
{
    
const int SIZE = 15;
    
int iMineNum;
    
double p;
    
int pMinePos[SIZE];     //记录雷的位置 
    double pRes[SIZE];      //pRes[i]表示经过雷i后存活下来的几率 
    
    
while(scanf("%d%lf",&iMineNum,&p) != EOF)
    
{
        
*(pMinePos+0= 0;              //  为了统一后面的计算 
        for(int i=1; i<=iMineNum; ++i)
            scanf(
"%d", (pMinePos+i));    
                    
        sort(pMinePos,pMinePos 
+ iMineNum + 1);     //对雷的位置进行排序 
           
        pRes[
0= 1;                    //  为了统一后面的计算  
        
        
for(int i=1; i<=iMineNum; ++i)
        
{
            
/*计算遇到雷之前,存活的几率*/ 
            pRes[i] 
=  -1/(p-2+ 1/(p-2* pow((p-1),pMinePos[i]-pMinePos[i-1]-1);
            
            
/**/
            pRes[i] 
*= (1-p) * pRes[i-1];
        }
       
        printf(
"%.7lf\n",pRes[iMineNum]);        
    }
    
    
return 0;    
}

posted on 2009-09-12 21:36 jaysoon 阅读(167) 评论(0)  编辑 收藏 引用 所属分类: ACM/ICPC


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

收藏夹

C++

搜索

最新评论

阅读排行榜

评论排行榜