oppo 9.2笔试-影像算法
第一题暴力了80%多，第三题AC了，第二题做了好久没搞出来，考完后发现是个计算问题：
问题：有k个小鸟，n个鸟洞，一只鸟进鸟洞概率均等，现要求至少有一个鸟洞中有两只鸟的概率大于等于概率p的最小k值？
示例：n=365, p=0.5, 求得k=23
概率模型很好推出为：，重点为求概率时，不能直接全部算法乘法后再除，很容易就会超限，引以为戒！
修改后代码如下：
#include <iostream>
using namespace std;
double fun1(int n,int k) {
double ans = 1;
int t = n;
for (int i = 0; i < k; i++) {
ans *= ((double)t--/ (double)n);
}
return ans;
}
int main() {
int n;
double p;
cin >> n >> p;
int k = 2;
while (true) {
double x = 1 - fun1(n, k);
if (x >= p) {
cout << k;
return 0;
}
++k;
if (k > n) {
cout << k;
return 0;
}
}
}
类似资料：