BNUOJ 44578 Monty Hall problem

原创 陈 浩翔  2015-11-29 12:33  阅读 91 次

蒙提霍尔问题,亦称为蒙特霍问题或三门问题(Monty Hall problem),是一个源自博弈论的数学游戏问题.
这个游戏的玩法是:参赛者会看见三扇关闭了的门,其中一扇的后面有一辆汽车,选中后面有车的那扇门就可以赢得该汽车,而另外两扇门后面则各藏有一只山羊。当参赛者选定了一扇门,但未去开启它的时候,知道门后情形的节目主持人会开启剩下两扇门的其中一扇,露出其中一只山羊。主持人其后会问参赛者要不要换另一扇仍然关上的门。问题是:换另一扇门会否增加参赛者赢得汽车的机会率?
——wikipedia

现在我们来研究n扇门的蒙提霍尔问题:一共有n扇关闭了的门。只有一扇门后是汽车,其他n-1扇门后是山羊。参赛者选定一扇门后,知道门后情形的节目主持人会开启剩下n-1扇门的其中n-2扇,露出n-2只山羊。主持人其后会问参赛者要不要换另一扇仍然关上的门。求参赛者换门之后获得汽车的概率。

Input
第一行为一个整数T,代表数据组数,T>=1000。
接下来T行,每行一个正整数n,3>=n>=10^18。n的含义如题意所示。

Output
答案要求输出最简分数形式:p/q (p,q互素) 。表示参赛者换门之后获得汽车的概率。

Sample Input
1
3
Sample Output
2/3

这里解释一下那个2/3怎么来的:
假设你永远都会转换选择,这时赢的唯一可能性就是选一扇没有车的门,因为主持人其后必定会开启另外一扇有山羊的门,消除了转换选择后选到另外一只羊的可能性。因为门的总数是三扇,有山羊的门的总数是两扇,所以转换选择而赢得汽车的概率是2/3,与初次选择时选中有山羊的门的概率一样。
补充说明:
第一次选的空门1(概率1/3),之后主持人开另一个空门,换门,得到汽车。 事件总概率 1/3
第一次选的空门2(概率1/3),之后主持人开另一个空门,换门,得到汽车。 事件总概率 1/3
换门后得到汽车总概率:2/3。

#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
       long long n;
       long long a,b;
       scanf("%lld",&n);
       a=n;
       b=n-1;
       do{
           a=a%b;
           long long tt;
           tt=a;
           a=b;
           b=tt;
       }while(b!=0);
        cout << ( n -1 )/a << '/' << n/a << endl;
    }
    return 0;
}

anyShare分享到:
本文地址:http://chenhaoxiang.cn/2015/11/29/bnuoj-44578-monty-hall-problem/
关注我们:请关注一下我们的微信公众号:扫描二维码会Java的公众号,公众号:程序编程之旅
版权声明:本文为原创文章,版权归 陈 浩翔 所有,欢迎分享本文,转载请保留出处!

发表评论


表情