阿里云的一个笔试题解决思路

阿里云的一个笔试题
一个骰子，6面，1个面是 1， 2个面是2， 3个面是3，问平均掷多少次能使1,2,3都至少出现一次！
貌似要求期望，好久没摸都忘了，麻烦指点指点！！

------解决方案--------------------
知道的人都不说，非要我自己想，哎，终于搞定了

首先要知道这个题求什么，最先直接没理解

这题可以翻译为，一个骰子，6面，1个面是 1， 2个面是2， 3个面是3，随机扔骰子，在第x次时3个数都出现，求这个x的期望（也就是扔无数次，x的平均值是多少）

思路：
第一二次肯定不可能出现这种情况
第x(x > 2)次三个都出现的情况分三种（x ^ y 表示 x 的 y 次方）

1：第x次出现 1，那么前面出现的必然是 2 和 3 ，且至少出现一次
出现1的概率为 1 / 6，前面x-1次不出现1的概率为(1 - 1 / 6) ^ (x - 1)，但是其中包含全是 2 和全是 3 的情况，去掉全 2 的概率 (1 / 2) ^ (x - 1)，全部为3的概率(1 / 3) ^ (x - 1)，那么情况 1 的概率为 ((1 - 1 / 6) ^ (x - 1) - (1 / 2) ^ (x - 1) - (1 / 3) ^ (x - 1)) * (1 / 6)

2：第x次出现2，那么前面出现的必然是 1 和 3 ，且至少出现一次
同样，概率为 ((1 - 1 / 3) ^ (x - 1) - (1 / 2) ^ (x - 1) - (1 / 6) ^ (x - 1)) * (1 / 3)

3：第x次出现3，那么前面出现的必然是 1 和 2 ，且至少出现一次
同样，概率为 ((1 - 1 / 2) ^ (x - 1) - (1 / 3) ^ (x - 1) - (1 / 6) ^ (x - 1)) * (1 / 2)

p(x)就为上面三种情况的和

那么，根据期望公式，平均值就等于从x = 3 到 n（无穷）求(x * p(x))的和

利用错位相减法计算极限值，附代码

C/C++ code


#include "stdio.h" 
#include "math.h"

const int MAX_TRY = 10000;

double funBase(double x)
{
    return x * x * (3 + x / (1 - x));
}

double funOne(double x)//每种情况的极限
{
    x = 1 - x;
    return funBase(x) - funBase(1 - x);
}

double funThree(double x1, double x2, double x3)
{
    return funOne(x1) + funOne(x2) + funOne(x3);//三种情况的极限和
}

double funTimeBase(double x, int n)
{
    return x * pow((1 - x), n) - (1 - x) * pow(x, n);
}

double funTimeOne(double x1, double x2, double x3, int n)
{
    return funTimeBase(x1, n) + funTimeBase(x2, n) + funTimeBase(x3, n);
}

double funTimeAll(double x1, double x2, double x3, int start, int n)
{//简单的变化
    double total = 0;
    for (int i = start; i < n; ++i)
    {
        double look = funTimeOne(x1, x2, x3, i);
        total += (i + 1)* look;
    }
    return total;
}

double funDirectOne(double x1, double x2, double x3, int n)
{
    double ret = 0;
    ret += x1 * (pow((1 - x1), n) - pow(x2, n) - pow(x3, n));
    ret += x2 * (pow((1 - x2), n) - pow(x1, n) - pow(x3, n));
    ret += x3 * (pow((1 - x3), n) - pow(x2, n) - pow(x1, n));
    return ret;
}

double funDirectAll(double x1, double x2, double x3, int start, int n)
{//按各种情况直接求和
    double total = 0;
    for (int i = start; i < n; ++i)
    {
        double look = funDirectOne(x1, x2, x3, i);
        total += (i + 1) * look;
    }
    return total;
}


int main() 
{
        //后面的start = 2表示第三次的概率
    double ret = funTimeAll(1.0 / 6, 1.0 / 2, 1.0 / 3, 2, MAX_TRY);
    printf("%f ", ret);
    ret = funThree(1.0 / 6, 1.0 / 2, 1.0 / 3);
    printf("%f ", ret);
    ret = funDirectAll(1.0 / 6, 1.0 / 2, 1.0 / 3, 2, MAX_TRY);
    printf("%f\n",ret);
    return 0;
}

阿里云的一个笔试题解决思路

相关推荐