ZJU 2494 Coins of Luck

 

题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2949
题目描述:

 

Luck is the key to life. When I have to decide something, I will make my decision by flipping a coin. And then, I have two things to do. First, I have the decision made. Second, I go to the nearest church and donate the coin.

But there are always too many things I have to decide. For example, what should I eat today for lunch? OK, now we are talking about a decision, so let us assume that I have two kinds of food: quick-served noodle A and quick-served noodle B.

I just have bought N bowls of noodle A and N bowls of noodle B. If I have some space to make a decision (i.e. having two kinds of quick-served noodle to choose from), then I will flip a coin to decide which kind of noodle to eat.

My question is, before I eat up all 2 * N bowls of quick-served noodle, what is the mathematical expectation of the number of coins I will have to donate.

Input

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 1000) which is the number of test cases. And it will be followed by T consecutive test cases.

Each test case contains an integer N (1 <= N <= 1000).

Output

Results should be directed to standard output. The output of each test case should be a single real number, which is the mathematical expectation of the number of coins I have to donate. The result should be accurate to two digits after the fractional point.

Sample Input

2
1
2

 

Sample Output

1.00
2.50
 
该题目的思路很明确,就是概率题,尝试了两种解法,一种是用递推,另一种是直接利用组合公式
递推法:
//solution 1
以P[i][j]表示状态, i代表A种面条剩下的数量,j代表B种面条的数量。
P[i][j] = P[i - 1][j] * 0.5 + P[i][j - 1] * 0.5 (i - 1 != 0 && j - 1 != 0, i为0或者j为0则为终结态)
Result = 
 
#include <iostream>
#include 
<queue>
#include 
<cmath>
using namespace std;
#define MAXN 1100
double P[MAXN][MAXN];




    
double dVal;
double dResult[MAXN + 100];

int main()
{

    
int iCaseTimes;
    
int k, i, j;
    
double dVal;


    scanf(
"%d"&iCaseTimes);
    
for(k = 0; k < iCaseTimes; k++)
    
{
        scanf(
"%d"&iNum);
        dRet 
= 0;
        P[iNum 
+ 1][iNum] = 1;
        P[iNum][iNum 
+ 1= 1;
        
for(i = iNum; i >= 0; i--)
        
{
            
for(j = iNum; j >= 0; j--)
            
{
                
if(i + 1 >= 1 && j >= 1)
                    P[i][j] 
+= P[i + 1][j] * 0.5;
                
if(i >= 1 && j + 1 >= 1)
                    P[i][j] 
+= P[i][j + 1* 0.5;
                
if(i == 0 || j == 0)
                
{
                    dRet 
+= P[i][j] * (iNum * 2 - i - j);
                }

            }

        }


        
        printf(
"%.2lf\n", dRet);
    }

    
return 0;
}
很明显,算上总的Case数量,这种方法的时间复杂度为O(n^3), 所以,超时是必然的
这时转换下思路,想想能不能一下子就把1000规模的打好表呢?在上述表示情况下,打表是不行的,因为每次进行计算的时候,都需要将P[iNum][iNum]
设置为概率1,所以,当直接打好1000的规模,其子问题仍然没法计算出来。
//solution 2
换一状态表示方法
我们令P[i][j]来代表状态,其中的i, j代表A类面条吃了i碗,B类面条吃了j碗,这样我们可以这样得到答案:
 
再观察这时候的子结构,假设先计算好规模为1000的表,此时的输入为iNum,我们可以看到,到数量为iNum - 1的结果都是对的,而数量为iNum的结果
是错误的,因为1000大于iNum,在1000的规模下,到iNum时没有进行终结,而当单类面条吃到iNum碗时,应该是结束态,所以,我们只能利用到规模为
iNum - 1数量的结果,并利用其推出最后答案。
//solution 1 O(n^2)
#include <iostream>
#include 
<cmath>
using namespace std;
#define MAXN 1100

double dRet[MAXN][MAXN];

int main()
{
    
int i, j;
    
int iNum, iCaseTimes;
    
double dResult;

    memset(dRet, 
0sizeof(dRet));
    dRet[
0][0= 1;
    
for(i = 0; i <= 1000; i++)
    
{
        
for(j = 0; j <= 1000; j++)
        
{
            
if(i == 0 && j == 0continue;
            
if(i - 1 >= 0)
                dRet[i][j] 
+= dRet[i - 1][j] * 0.5;
            
if(j - 1 >= 0)
                dRet[i][j] 
+= dRet[i][j - 1* 0.5;
            
//dRet[i][j] += 1;
        }

    }


    scanf(
"%d"&iCaseTimes);
    
while(iCaseTimes--)
    
{
        scanf(
"%d"&iNum);
        dResult 
= 0;

        
for(i = 0; i <= iNum - 1; i++)
        
{
            dResult 
+= dRet[iNum - 1][i] * (iNum + i) * 0.5;
        }

        dResult 
*= 2;
        printf(
"%.2lf\n", dResult);
    }

    
return 0;
}
 假如直接利用组合公式能否计算呢?
因为该事件发生的概率不是等可能事件,也就是说,假设有2 * iNum 碗面条,2 ^ (iNum + 1)并不是其样本空间,因为其中一些序列是不可能发生的
那么假设抛硬币事件一定发生(有点像条件概率,我具体想不明白:( ), 那么,可以得到下面的公式:
总的样本空间为2^K,因为抛了K次硬币,每次两种选择;而在这长度为K的串中,最后一碗必定是固定的(肯定为吃完的那种),
所以只要在剩下的K - 1碗中选出iNum - 1个位置便可。乘以二代表有两类面条吃完的对称情况,乘以K是转换成期望。
//solution 2 O(n^2)
#include <iostream>
using namespace std;
#define MAXN 2100

double C[MAXN][MAXN - 1000];

int main()
{
    
int i, j;

    memset(C, 
0sizeof(C));
    C[
0][0= 0.5;
    C[
1][0= 0.25;
    C[
1][1= 0.25;
    
for(i = 2; i <= 2000; i++)
    
{
        C[i][
0= C[i - 1][0/ 2.0;
        
for(j = 1; j <= 1000; j++)
        
{
            C[i][j] 
= (C[i - 1][j] + C[i - 1][j - 1]) / 2.0;
        }

    }

    
    
int iNum;
    
int iN;
    
double dRetVal;
    
    scanf(
"%d"&iNum);
    
while(iNum--)
    
{
        scanf(
"%d"&iN);
        dRetVal 
= 0;
        
for(i = iN; i <= iN * 2 - 1; i++)
        
{
            dRetVal 
+= C[i - 1][iN - 1* i;
        }

        printf(
"%.2lf\n", dRetVal * 2);
    }

    
return 0;
}
主要的思路是将组合数进行打表,更需要注意的是将2^k次也融入到整个组合数的表中,也就是说,在利用杨辉三角进行递推的时候就将除二操作加进去。
这里要注意double类型的精度问题,由于题目只要求精确到小数两位,所以利用double还是可以满足的。
对于上述方法,虽然时间复杂度是O(n^2),但是其空间复杂度也为O(n^2),观察到每两个f(K)函数之间也有递推关系,我们只要计算出第一个之后,再
乘上一个式子,除以一个式子,就可以得到下一个值,所以,再实现一个空间复杂度更小的O(n^2)的方法:
 
//solution 3
#include <iostream>
using namespace std;

int main()
{
    
int i, j;
    
    
int iNum;
    
int iN;
    
double dRetVal;
    
double dPreVal;
    
double dStartValue;
    
    scanf(
"%d"&iNum);
    
while(iNum--)
    
{
        scanf(
"%d"&iN);
        dRetVal 
= 0;
        dStartValue 
= 1;
        
//(iN - 1, iN - 1) 
        for(i = iN; i >= 1; i--) dStartValue /= 2.0;
        
        dRetVal 
= dStartValue * iN;
        dPreVal 
= dStartValue;
        
for(i = iN + 1; i <= iN * 2 - 1; i++)
        
{
            dRetVal 
+= (double) dPreVal * (i - 1/ (i - iN) * i / 2;
            dPreVal 
= dPreVal * (i - 1/ ((i - iN) * 2);
        }

        printf(
"%.2lf\n", dRetVal * 2);
    }

    
return 0;
}

通过对该题的解决,可以看到,概率类的题目基本上两个方向:1.直接用组合公式解决。但是这种方法容易产生精度问题,而且不一定能够简单的推出来
2.用递推公式解决。这种方法比较容易想清楚方法,但是面临的问题便是时间与空间的限制。

posted on 2009-03-08 19:32 Philip85517 阅读(952) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2022年5月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

统计

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜