南京赛J题 - 人品房间(Xiaoxingxing)
[题目描述]
小新来到一个大房间，这个房间就是“人品房间”。房间里有若干个门，每个门后都有一条道路，其中有些门是通往房间外的，然而有些门后的道路会绕一圈后又回到这个房间。小新的记忆不是很好，他记不住自己走过哪些门，所以如果他不幸走进一个门以后又回到了这个房间，那么下一次选择走哪个门是随机地。这就是所谓的人品，小新有可能永远也走不出这个房间！现在的问题是，如果小新有一个正常的人品的话，请问他要走多久才能走出这个房间？
输入多组测试数据，第一行包含两个整数p,q(0<=p,q<=1000)，p表示通往外面的道路数目，q表示返回到这个房间的道路数目。第二行包含p+q个数，分别是各条路的长度。（通往外面的路也有一定长度）输入以p=q=0结束。
假设小新的速度为1，请输出小新走出房间总共的时间。（保留3为小数）
-------------------------------------------------------------------------------------------------------
[分析]
思路一:
这个题目很类似高中的时候学的概率问题当中很典型的“钥匙开门”问题。
最初的思路是想，计算第一次走出房间的概率×走出去的平均路程＋第二次走出的概率×平均路程＋第三次概率×平均路程……因为如果小新人品败坏的话，可能永远也走不出这个房间，所以要一直加到无穷大。
设第i次走出房间的概率为Fi，则F1=p/p+q , F2=p*q/(p+q)2 , F3=p*q2/(p+q)3 … Fn=p*qn-1/(p+q)n ，递推公式Fi=(1-Fi-1)*F1。
设第i次才走出房间的平均路程为Si，则 Si=(1/p)*LEN_out+((i-1)/q)*LEN_back 其中LEN_out和LEN_back分别是出去和回来的路程之和。递推公式 Si=Si-1+LEN_back/q。
接下来的工作是计算∑Si*Fi (i->∞)。想到这里我觉得进入了一个数学的迷宫，应该有一个更简练的方法解决这个问题。于是这个计算工作暂且放下，我们另辟蹊径。
思路二:
我们首先从一些简单的概率问题入手。
1.投硬币平均几次出现一次正面？
解：因为投一次平均出现1/2次正面，所以平均投2次出现一次正面。（以下省略“平均”二字）
2.现在有2个黑球，3个白球，每次随机选取一个，几次才能选中黑球？
解：和上一题一样，选一个球出现2/5个黑球，所以出现一个黑球要取2.5次。
3.在上一题的基础上，如果每个白球有一个权值wi，黑球权值为0，选中黑球时停止取球，那么最终取得的总权值是多少？
解：选中每个白球的概率是相同的，那么可以用“权值总数/白球数量”w0代替每个白球的权值。2.5次中，1次选中黑球，那么其余1.5次选中白球，则总权值为1.5*w0。
4.如果每个黑球也有一个权值，那么最后取得的总权值是多少？
解：同理，总权值为“选中黑球的次数”ד黑球的平均权值”＋“选中白球的次数”ד白球的平均权值”。因为一旦选中黑球就停止，所以选中黑球的次数一定是1。
好了，做到这里已经和我们要解决的问题非常接近了。现在回到我们的问题，令“走出房间的平均距离”为D1，“返回房间的平均距离”为D2。这两个量是很好计算的。然后计算“走出房间的平均次数”T，则T=(p+q)/p。所以由第四题的结论得，“走出房间的平均距离”S=1*D1+(T-1)*D2。
[总结]
通过这个题目，我们应该注意积累基础学科知识，数学永远是老大。在解题的过程中也要有探索精神，如果思路不清晰，可以从简单情况入手，逐步接近原来的问题。在省赛解体报告那本书里，在解决2005 Problem A – A piece of cake 的时候也是用了这样的解题思路。
[说明]今天突然想到的解决方案，可能有不对的地方，欢迎大家指出^^
|
|
1楼
评论时间：2007年6月25日 19时28分 |
我很怕概率的问题~~虽然考试能拿高分，但是这种题目想对了就很简单，但是如果方向错了就会晕掉，而且自己根本不清楚自己是错是对。 你的解法我感觉应该有问题，没有仔细看，出期末考卷出到疯掉，不能思考这么复杂的问题。。。说下我的思路。思路来源是 算法中随机算法时间复杂度的计算，具体细节可以参考算法书。 设某一次走出去的概率为pout，走不出去的概率为pin，pout=p/(p+q),pin=1-pout,某一次走出去的平均行走距离和走不出去的平均行走距离直接对数据求平均即可，分别记为din，和dout 设所求为X，则X=pout*dout+pin*(din+X)，然后把X解出来。有用到递归的思想，走出来那段很好理解，走不出来的话，行走距离为本次没有走出来的距离加上走出来需要走的距离。 我也不知道对不对，大家参考吧。 |
| |
|
|
2楼
评论时间：2007年6月26日 13时45分 |
X=pout*dout+pin*(din+X)这个方程的含义理解,X表示的是"平均走出房间时的总路程"?怎么得出这个方程的啊? 如果变形一下,成这样:X=(pout*dout+pin*din)/(1-pin)不就一次就求出来了? 怎么递归的..  |
| |
|
|
3楼
评论时间：2007年6月27日 1时20分 |
|
是直接解出来啊，我是说用到递归的思想，没说程序要递归。递归之处在于，本来左边就是计算的要走出来需要的路程，但是右边又用到了这个值，也就是用到了自己。
之所以得这个方程是因为每次选择都是独立的，所以走不出去的话，其实又变成了原问题本身，不过要加上选择了走不出去的门后导致的步行距离。
越说越觉得对。。。。。。除非谁告诉我哪里不对。
|
| |
|
|
4楼
评论时间：2007年6月27日 12时48分 |
哇哈哈哈哈~~~~~~ 我推了一下,我们俩的方程是一样的~!!用了不同的思路~ 真是经典啊  |
| |
|
|
5楼
评论时间：2007年6月27日 14时59分 |
先看看你的^^: X=(pout*dout+pin*din)/(1-pin) ∵1-pin=pout pout=p/(p+q) pin=q/(p+q)
∴X=dout+(pin/pout)*din
=dout+(q/p)*din
再看看我的~:
S=1*Dout+(T-1)*Din
其中 T=(p+q)/p
∴T-1=q/p
S=Dout+(q/p)*Din
X==S 证毕~ |
| |
|
|
6楼
评论时间：2007年6月27日 17时33分 |
|
好像是概率分布的问题，有公式可以直接用。
具体是哪种分布模型已经忘掉了，太久没做过概率分布，好像是伽玛分布？也可能是威伯分布？应该是一种负指数分布
不过按照你的思路1应该能做出来
已经推出了概率函数Fn=p*qn-1/(p+q)n
求0到正无穷的定积分
除以正无穷求极限就可以得到平均次数概率
然后再按照你的次数函数算出来就OK啦
|
| |
|
|
7楼
评论时间：2007年6月29日 13时30分 |
|
原来一样。。。看来很有可能对哦，就等他们给我们方式提交了~~~~~
楼上那个方法貌似有点复杂。。。不过看上去比较专业。。。
|
