| | |
|
岱瀛
(deving)
| |
| | |
|
| | |
|
 组别 | 经略使 |
| 级别 | 左将军 |
| 好贴 | 1 |
| 功绩 | 2293 |
| 帖子 | 1370 |
| 编号 | 55810 |
| 注册 | 2005-12-22 |
| 来自 | 人间 |
| 家族 | 慕容世家 |
| |
| | |
|
|
|
|
周大神算，果然如姑姑如言，周大最会算来算去了.
(P.S:这在古代称为术数，所以早在慕容家的天下各路高手分析中早已注明周大擅奇门遁甲之术. )
-------------------------------------------------------------------------------------------------------------------------------------------------------------
周大的算法思路是一种利用尝试次数和球数这两个变量，求可测算楼层的最大化，即最优战术可测算的最高楼层，即最优解.
本题运用的是动态规划的方法。
首先，无论采用哪一种尝试战术，最后都必然面临着剩一次机会的情况。
那么，根据题意，在N个球的情况下(N>0)，只有一次机会下，最优解只能是1层。
这里有一个性质，就是F(x,y)，当X>Y时，F(x,y)=F(y,y). （X为球数，Y为尝试次数）
所以，Y是规划问题复杂度的量。
而在剩两次的机会下，最优解，必然是包含了1次机会的最优解，即在X不变的情况下，
F(x,2)的战术中必然包括F(x,1)和F(x-1,1)
1次机会下的最优解，是2次机会下最优解的子集，所以此题满足了最优化原理。
再来看，任何一次小球的出手，必然只有两种结果，一种是碎，一种是不碎。
比如F(2,2),如果第一次出手，球破了，那么剩一球，一次，显然只有F(1,1)是最优的。
球不破，那么剩2球，一次，F(2,1)是最优的。而F(2,1)=F(1,1)。
所以F(2,2)的战术，必然是F(1,1)和F(2,1)采用的战术的终合。
F(2,2)=1+F(1,1)+F(2,1)
这里面，题目有个特殊点，就是1~K层的尝试和K+1~M层的尝试，只要K层的性质等同于0层的性质，那么两个区间内的尝试
是等价的。
所以，对于x<y的情况下，F(x,y)必然可先有第一试，分出破与不破两个区间，不同情况然后采用相应战术。
推出： F(x,y)=1+F(x-1,y-1)+F(x,y-1)
而x>=y的情况下，F(x,y)=F(y,y)=1+F(y-1,y-1)+F(y,y-1)
举3个球尝试9次的例子。F(3,9)=1+F(3,8)+F(2,8)
=2+F(3,7)+F(2,7)+F(2,8)
=3+F(3,6)+F(2,6)+F(2,7)+F(2,8)
=4+F(3,5)+F(2,5)+F(2,6)+F(2,7)+F(2,8)
=5+F(3,4)+F(2,4)+F(2,5)+F(2,6)+F(2,7)+F(2,8)
=6+F(3,3)+F(2,3)+F(2,4)+F(2,5)+F(2,6)+F(2,7)+F(2,8)
=7+F(3,2)+F(2,2)+F(2,3)+F(2,4)+F(2,5)+F(2,6)+F(2,7)+F(2,8)
=8+F(3,1)+F(2,1)+F(2,2)+F(2,3)+F(2,4)+F(2,5)+F(2,6)+F(2,7)+F(2,8)
=9+F(2,1)+F(2,2)+F(2,3)+F(2,4)+F(2,5)+F(2,6)+F(2,7)+F(2,8)
=9+1+3+6+10+15+21+28+36
=129
此时采用的战术是什么呢?显然就是从F(2+8)+1层开始试啊。即37层开始试.
碎了，就在层内1~36层采用F(2,8)战术，
不碎，就在38~129层这92层里采用F(3,8)战术 。(题目是100层，在此区间内)
----------------------------------------------------------------------------------------------------------------------------------------------------------
再看新问题，等价分布和高斯分布，同样都必须面临相同的最后选择，剩下一次机会的时候你能试多少层楼。
答案应该是肯定的，一次机会同样是一层楼。哪怕第一层的碎的概率是0.0000001%，你都必然得去试，
而碎与不碎的结果仅可判断第一层的结果。
那么再看累加的集。F(2,2)。在2个球，2种机会下。投出一个球，依然会回到F(2,1)或者F(1,1)的窘境，
而F(2,1)是的答案又等同于F(1,1).而前面已经得到，哪怕只有0.0000001%的概率，F(1,1)=1.
所以，题目如果要有不同，显然必须从F(2,2)入手。那么，第一个球显然是往最高碎的概率点投去的，不然概率的存在没有意义。
但是无论概率多少，出手后的结果却是一样，也是碎和不碎。
碎与不碎，只能确定投的那一层，然后转入两个区间内的运算，必然最终又回到F(2,1)和F(1,1)求解的问题。
因为，即使第N层有99.999999%概率会碎，
然后投完没碎，仅仅代表那层没碎，N+1的可能概率依然没有变化，或者说无法另N+1层以上的某层概率归一。
碎了的话， 仅仅代表那层会碎, N-1层的可能概率也没有变化，或者说无法另N-1层以下的某层概率归一。
所以，本题看不出和概率有什么相关性。规划战术应用过程中，总是在选择最佳战术，是有百分之百的把握的战术，因为题目要求球出手完是必然要得到一个绝对结果而不允许得到一个可能结果的。
如果题目允许N个球都破，但是不能得出哪一层肯定碎或者最高层都不碎的答案，而是一个可能百分比，那么概率的设置才有意义。
因为这个时候，F(1,1)就不等于1了。
或者也可以有这种假设，比如说如果N层为99.99%的地方碎了，那么在N层下，98%以上的地方也必然碎，如果没碎，则N层上98%的层为不碎之类的前提条件，使反向一边的概率会从你尝试点处的概率推算出新的概率变化并且最终归一的话,那么概率分布对战术选择才会有影响吧。
[ 本帖最后由 岱瀛 于 2007-1-15 23:13 编辑 ]
|
|
|
|
