首页 > ACM题库 > HDU-杭电 > hdu 2201 熊猫阿波的故事-概率-[解题报告]C++
2014
01-04

hdu 2201 熊猫阿波的故事-概率-[解题报告]C++

熊猫阿波的故事

问题描述 :

凡看过功夫熊猫这部电影的人都会对影片中那只憨憨的熊猫阿波留下相当深的印象,胖胖的熊猫阿波自从打败了凶狠强悍的雪豹泰龙以后,在和平谷的地位是越来越高,成为谷中第一的功夫大师。并因此他父亲经营的面馆的生意也越来越好,店里每天都会有许多慕名而来吃面和想拜阿波为师的人。
一日,阿波收到了一张请柬,请柬里说在遥远的美国将召开全球比武大会,特邀请阿波过去做嘉宾。阿波当然很高兴,因为自己长这么大都还没出过和平谷,更何况是出国去那遥远的美国。于是他托人买了当晚的机票,阿波来到机场发现其他乘客们正准备按机票上的号码(1,2,3,…..,n)依次排队上飞机,由于阿波是第一次坐飞机,所以他想先一步登机,因此他插队第一个登上了飞机,并且他也不看机票,随机的选择了一个座位坐下了。乘客们都很气氛,他们想:既然阿波都不遵守规定,那么我为什么要遵守呢?因此后面所有的人也都随意地找了位置坐下来,并且坚决不让座给其他的乘客。
现在的问题是这样的:在这样的情况下,第i个乘客(除去熊猫阿波外)坐到原机票位置的概率是多少?

输入:

输入包含多组测试数据,每组数据占一行,包含两个整数,分别是n和m(n>=m),n表示共有n个乘客(包括阿波),m表示第m个乘客。

输出:

输入包含多组测试数据,每组数据占一行,包含两个整数,分别是n和m(n>=m),n表示共有n个乘客(包括阿波),m表示第m个乘客。

样例输入:

2 1
11 3

样例输出:

0.50
0.09

前M-1个人是关于N-1个位置的全排列的情况下,M个人就能够做到他自己的位置了,而所有的请情况是M个人对于N位置的全排列的。用样本数除以样本空间就能够得到概率了。

代码如下:

#include <cstdlib>
#include <cstdio>
#include <cstring> 
using namespace std;

int main()
{
    int N, M;
    while (scanf("%d %d", &N, &M) == 2) {
        printf("%.2lf\n", 1.0/N);
    }
    return 0;
}

解题转自:http://www.cnblogs.com/Lyush/archive/2012/05/11/2496583.html


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。