f********w
发帖数: 10 | 1 有一个藥罐子，最初里面放了100颗整颗药，每颗药能掰成两个半颗。
每次从药罐子里随机取出一片药，如果是整颗药，就掰成两半，吃掉半颗，放回半颗。
如果是半颗，就吃掉这半颗。
现在求第n次取药的时候娶到半颗的概率
double halfChance(int n)
我的一点思路
如果取到的是整颗，那罐子里的总数是不变的，极端情况n次都正好是取到整颗，那n轮
后罐子里还是100颗药，此时包涵了n个半颗和（100－n）个整颗
如果取到的是半颗，总数会－1，极端情况n次都是先取整颗，再取半颗，那n轮后罐子
里还有100-n/2颗药，如果n是偶数，那现在罐子里没有半颗，如果n是奇数，那现在罐
子里只有一个半颗
感觉得怎么递归一下？ |
k****s
发帖数: 16 | 2 既然是写程序的话，估计就不是用巧方法算的。
暴力法
建个二叉树， 把每个分支的概率都标上，最后把叶子节点的概率加一下。 |
l**********7
发帖数: 55 | 3 我猜一下，感觉是1-(n-1)!/100**(n-1)
【在 k****s 的大作中提到】
: 既然是写程序的话，估计就不是用巧方法算的。
: 暴力法
: 建个二叉树， 把每个分支的概率都标上，最后把叶子节点的概率加一下。
|
l**********7
发帖数: 55 | 4 又想了下，是不是应该算取不到半颗的几率是多少？
【在 l**********7 的大作中提到】
: 我猜一下，感觉是1-(n-1)!/100**(n-1)
|
e***l
发帖数: 710 | 5 感觉解析式比较难，是多个不同概率事件发生次数的和 |
k*******a
发帖数: 772 | 6 假设 p（n, k) 是n次以后有k个half pill的概率
如果n次以后是k， 那么n-1次的时候要么是k-1, 要么是k+1
这样，对这个vector可以做个递归 p(n, k) = f(n-1, k-1)*p(n-1, k-1) + (1-f(n-1,
k+1))*p(n-1, k+1)
其中 f(n, k)表示取到整科的概率，很容易可以得到
这样可以通过循环或者递归来得到结果 |
d********t
发帖数: 9628 | 7 明显DP肥概率。
【在 f********w 的大作中提到】
: 有一个藥罐子，最初里面放了100颗整颗药，每颗药能掰成两个半颗。
: 每次从药罐子里随机取出一片药，如果是整颗药，就掰成两半，吃掉半颗，放回半颗。
: 如果是半颗，就吃掉这半颗。
: 现在求第n次取药的时候娶到半颗的概率
: double halfChance(int n)
: 我的一点思路
: 如果取到的是整颗，那罐子里的总数是不变的，极端情况n次都正好是取到整颗，那n轮
: 后罐子里还是100颗药，此时包涵了n个半颗和（100－n）个整颗
: 如果取到的是半颗，总数会－1，极端情况n次都是先取整颗，再取半颗，那n轮后罐子
: 里还有100-n/2颗药，如果n是偶数，那现在罐子里没有半颗，如果n是奇数，那现在罐
|
e***l
发帖数: 710 | 8 算出来第100次是0.5321961583405941，有没有人对一下答案 |
l**********7
发帖数: 55 | |
l**********7
发帖数: 55 | |
|
|
h********3
发帖数: 2075 | 11 绕来绕去无非就是在conditional probability上打转。
【在 f********w 的大作中提到】
: 有一个藥罐子，最初里面放了100颗整颗药，每颗药能掰成两个半颗。
: 每次从药罐子里随机取出一片药，如果是整颗药，就掰成两半，吃掉半颗，放回半颗。
: 如果是半颗，就吃掉这半颗。
: 现在求第n次取药的时候娶到半颗的概率
: double halfChance(int n)
: 我的一点思路
: 如果取到的是整颗，那罐子里的总数是不变的，极端情况n次都正好是取到整颗，那n轮
: 后罐子里还是100颗药，此时包涵了n个半颗和（100－n）个整颗
: 如果取到的是半颗，总数会－1，极端情况n次都是先取整颗，再取半颗，那n轮后罐子
: 里还有100-n/2颗药，如果n是偶数，那现在罐子里没有半颗，如果n是奇数，那现在罐
|
l**********7
发帖数: 55 | 12 做出来才是硬道理。
这是我的代码，参考了http://www.feynmanlectures.info/solutions/half_pills_sol_2.pdf
速度很慢对于100个pill取100次。
//http://www.feynmanlectures.info/solutions/half_pills_sol_2.pdf
// w is number of whole pills
// h is number of half pills
float pill(int w, int h, int d) {
float p=0.0;
if (w<0 || h<0) return 0.0;
if (w==0 && h==2) return 1.0;
if (d <= 0) return 1.0*h/(w+h);
if (w>0) p += 1.0*w/(w+h)*pill(w-1, h+1, d-1);
if (h>0) p += 1.0*h/(w+h)*pill(w, h-1, d-1);
return p;
}
int main() {
int n, d;
scanf("%d", &n); // total number pills
scanf("%d", &d); // nth day >= 1
printf("%f n",pill(n, 0, d-1));
}
【在 h********3 的大作中提到】
: 绕来绕去无非就是在conditional probability上打转。
|
f********w
发帖数: 10 | 13
1,
【在 k*******a 的大作中提到】
: 假设 p（n, k) 是n次以后有k个half pill的概率
: 如果n次以后是k， 那么n-1次的时候要么是k-1, 要么是k+1
: 这样，对这个vector可以做个递归 p(n, k) = f(n-1, k-1)*p(n-1, k-1) + (1-f(n-1,
: k+1))*p(n-1, k+1)
: 其中 f(n, k)表示取到整科的概率，很容易可以得到
: 这样可以通过循环或者递归来得到结果
|
f********w
发帖数: 10 | 14 Sorry no Chinese on this pc, but could you elaborate? How to calc f(n, k)?
And given that we have P(n, k) how to derive the probability to get an half
pill at round n? How do we know the total number at the moment?
1,
【在 k*******a 的大作中提到】
: 假设 p（n, k) 是n次以后有k个half pill的概率
: 如果n次以后是k， 那么n-1次的时候要么是k-1, 要么是k+1
: 这样，对这个vector可以做个递归 p(n, k) = f(n-1, k-1)*p(n-1, k-1) + (1-f(n-1,
: k+1))*p(n-1, k+1)
: 其中 f(n, k)表示取到整科的概率，很容易可以得到
: 这样可以通过循环或者递归来得到结果
|
k*******a
发帖数: 772 | 15 因为半颗的个数/2 加上 整颗的个数 = 100 - n/2
所以可以知道整科颗的个数
所以取到整科的概率为 f(n, k) = (100-n/2-k/2)/(100-n/2+k/2)
half
【在 f********w 的大作中提到】
: Sorry no Chinese on this pc, but could you elaborate? How to calc f(n, k)?
: And given that we have P(n, k) how to derive the probability to get an half
: pill at round n? How do we know the total number at the moment?
:
: 1,
|
f********w
发帖数: 10 | 16 Sorry again for no Chinese on the PC and thanks! This one looks correct to
me
A bit modification with a stupid 3D buffer, should be faster, a better (Java
) way might be using a custom class with modified hashCode... And we would
need to compare d and h, say we have 5 halves left, the probability we get a
half in the 10th day would be 0.
// starting from state w(hole) and h(alf), the probability we take a half
pill on day d
double halfProb(int w, int h, int d, double[][][] back) {
if (back[w][h][d] > 0)
return back[w][h][d];
if (d == 1) {
return (double) h / (w + h);
} else {
if (w == 0) {
if (h >= d)
return 1;
else
return 0;
}
double p = 0;
p += (double) w / (w + h) * halfProb(w - 1, h + 1, d - 1, back);
if (h > 0)
p += (double) h / (w + h) * halfProb(w, h - 1, d - 1, back);
back[w][h][d] = p;
return p;
}
}
public static void main(String[] args) {
System.out.println(new Solution().halfProb(5, 0, 9,
new double[100 + 1][100 + 1][200 + 1]));
}
【在 l**********7 的大作中提到】
: 做出来才是硬道理。
: 这是我的代码，参考了http://www.feynmanlectures.info/solutions/half_pills_sol_2.pdf
: 速度很慢对于100个pill取100次。
: //http://www.feynmanlectures.info/solutions/half_pills_sol_2.pdf
: // w is number of whole pills
: // h is number of half pills
: float pill(int w, int h, int d) {
: float p=0.0;
: if (w<0 || h<0) return 0.0;
: if (w==0 && h==2) return 1.0;
|
f********w
发帖数: 10 | 17 0.5321961583405944
【在 e***l 的大作中提到】
: 算出来第100次是0.5321961583405941，有没有人对一下答案
|
T*****u
发帖数: 7103 | 18 2d birth-death markov model？ |
l****h
发帖数: 1189 | 19 你的半颗个数是不对的，半颗数可以是从0到n的任何数。应该没有解析解。
【在 k*******a 的大作中提到】
: 因为半颗的个数/2 加上 整颗的个数 = 100 - n/2
: 所以可以知道整科颗的个数
: 所以取到整科的概率为 f(n, k) = (100-n/2-k/2)/(100-n/2+k/2)
:
: half
|
f******n
发帖数: 279 | |
h****d
发帖数: 485 | 21 N(n+1)/N(n)=1-(1/(200-n-N(n))
其中N(n)是取完n次后整数颗药的期望值，N(0)=100
【在 f********w 的大作中提到】
: 有一个藥罐子，最初里面放了100颗整颗药，每颗药能掰成两个半颗。
: 每次从药罐子里随机取出一片药，如果是整颗药，就掰成两半，吃掉半颗，放回半颗。
: 如果是半颗，就吃掉这半颗。
: 现在求第n次取药的时候娶到半颗的概率
: double halfChance(int n)
: 我的一点思路
: 如果取到的是整颗，那罐子里的总数是不变的，极端情况n次都正好是取到整颗，那n轮
: 后罐子里还是100颗药，此时包涵了n个半颗和（100－n）个整颗
: 如果取到的是半颗，总数会－1，极端情况n次都是先取整颗，再取半颗，那n轮后罐子
: 里还有100-n/2颗药，如果n是偶数，那现在罐子里没有半颗，如果n是奇数，那现在罐
|
