标题: 从伽利略丢铁球联想到的题目。 [打印本页]
作者:
天宫公主 时间: 2007-1-12 09:44 标题: 从伽利略丢铁球联想到的题目。
你有两个玻璃球和一个１００层的大高楼，你想测出最低在那一层将玻璃球丢下，玻璃球便会破碎。用什么样的战术可以确保得到结果（i.e. 你的战术不能出现两个球都碎了，还找不到答案的情况），并且总共丢球的次数最小化？
如果你有 N 个玻璃球，你的战术会是什么？
作者:
周瑜 时间: 2007-1-12 10:49
第一个从10、20、30、……、100往下扔，直到摔碎。
假设在10*k层摔碎，第二个从10*(k-1)+1、10*(k-1)+2、……、10*(k-1)+9往下扔，直到摔碎或者9层都摔不碎。
最糟糕的情况是99或者100层摔碎，需要试验19次。
N个球的情况请楼下接着想。
作者:
岱瀛 时间: 2007-1-12 10:59
想到了二分法。不知道对不对。
对于两个球的，显然是先从第二层试，如果碎了，那么另外一个在球在第一层试。
如果没碎，那么转到第四层。
没次往上翻的间距为2。
对于N个球。从2^N-1的位置开始试，每次翻越的层距为2^N-1次。如果哪个点碎了，
则开始折返到1/2处试。
比如上面的两个球，代入就是2^2-1=2^1=2.所以是从2层开始试。
举个实例：
假如是4个球，代入就是2^4-1=2^3=8.从第8层开始试。
如果第8层没碎，则转到第16层。
如果16层碎了，则到16-(16-8)/2=12层处试。 （一个球没了）
如果12层处碎了，那么转到12-(12-8)/2=10层处试。 （两个球没了）
如果10层处碎了，那么转到10-(10-8)/2=9层处试。 （三个球没了）
如果第9层碎了，（第四个球没了），则答案是第9层，如果没碎就是第10层。
上面的，如果16层碎，12层没碎，则转到16-(16-12)/2=14层处试了。道理和上面的
一样，反正都是二分法。
想到的就是这个，不知道对不对。各位看看。
二分法，N个球时，选择从第2^(N-1)处开始试，没次不碎翻转的距离为2^(N-1).
如果K+2^(N-1)>100,则从100处开始。
（其中K是初始值，一开始是0，当你试过一次2^(N-1)没碎后，k+=2^(N-1)）
作者:
天宫公主 时间: 2007-1-12 11:09
周瑜：N = 2 的 case 你还没有达到最小。
岱瀛：你这个方法也。。。如果32层没碎，64层碎了。剩下的一个球，岂非要从 33, 34, 35, ... 一个一个往上来？
给个提示：当 N > log_2 (100) 的时候，二分法的确是正确的。当 N = 1 的时候，一层率一次是正确的。当 N 不大不小的时候，你们想法把这两个 case 折衷一下吧。
[ 本帖最后由 天宫公主 于 2007-1-12 11:11 编辑 ]
作者:
reynolds_wwy 时间: 2007-1-12 11:18 标题: 回复 #4 天宫公主 的帖子
第一个在14,27,39,50,60,69,77,74,90,95,99扔
别的和周瑜一样
这样14次就可以了
13次应该不行的吧，没仔细想过
作者:
周瑜 时间: 2007-1-12 13:05
假设N为玻璃球个数，x为尝试次数，最高能确定的层数为F(N,x)
定义域
N>=1, x>=1
边际条件
F(1,x)=x
F(N,1)=1
递推关系
F(N,x)=F(N-1,x-1)+F(N-1,x-2)+...+F(N-1,1)+x
通项公式
if x<=N
F(N,x)=2^x-1
if x>N and N is odd
F(N,x)=C(x+1,N)+C(x+1,N-2)+C(x+1,N-4)+...C(x+1,1)-1
if x>N and N is even
F(N,x)=C(x+1,N)+C(x+1,N-2)+C(x+1,N-4)+...C(x+1,0)-1
知道最高层数和玻璃球个数，查表可求出尝试次数。
作者:
岱瀛 时间: 2007-1-12 15:19
周大算了，我是去研究了下二分和分组的特点．手工算了下面这一组解,还不知道对不对
N=3 11次
20 10 1~9
38 29 21~28
54 46 38~45
68 61 55~61
80 74 69~73
90 85 81~84
98 94 91~93
100 99
N=4 9次
24 12 6 1~5
45 35 30 31~34
63 54 50 51~53
78 71 67 68~70
90 84 81 82~83
99 95 93 92
100
N=5 8次
32 16 8 4 1~3
60 46 39 36 37~38
84 72 66 63 64~65
100
N=6 8次
48 24 12 6 3 1~2
91 70 59 54 51 52~53
100
作者:
周瑜 时间: 2007-1-12 22:02
死抱着二分法干什么，把我的递推公式看明白一切都迎刃而解了。
F(3,8)=92
F(3,9)=129
3个球9次即可
F(4,7)=98
F(4,8)=162
4个球8次即可
F(5,6)=62
F(5,7)=119
5个球7次即可
F(6,6)=63
F(6,7)=126
6个球7次即可
作者:
whws 时间: 2007-1-13 16:55
似乎存在两种思考角度。一种是极值最优，应该可以简化为线性规划问题。一种是期望最优，未必能够简化为线性问题。楼上考虑的似乎都是极值条件下的最优，但是好像并没有给出最优证明。周瑜的递推公式依赖于具体算法，本身并不能证明自己是最优。不过猜测一下，reynolds_wwy和周瑜给出的划分方法的确可能是线性条件下的最优划分，至少在N＝2时应当是的。
[ 本帖最后由 whws 于 2007-1-13 17:10 编辑 ]
作者:
天宫公主 时间: 2007-1-15 05:37
reynolds + 周瑜的答案正确。其实周瑜的那个 algorithm 仔细分析一下，不难给出一个严密的证明。
whws: 我的题目是 worst case optimization, 本来也可以出 average case optimization 的，但我们对实验失败（全部球都碎了，还是没有找到答案）给什么样的惩罚算最合理呢？
作者:
whws 时间: 2007-1-15 15:47
我觉得这个题目之所以有趣，是因为它有很现实的应用背景。它的算法完全可以拿到有损检测的项目设计中去。而对于有损检测的成本估计会存在两种情况：一是最坏条件下的估计，即最大成本估计；一是预期条件下的成本估计。注意，两种估计都是在项目设计能够完成项目需求的情况下作出的，即不可能在所有工件都损坏的情况下，仍然得不出项目要求的结论，那样就是项目设计的失败。在保证项目成功的情况下，我们可以分别依据上面的两种估计来作出最优规划。而在大多数情况下，一般是依据第二种估计来作出项目规划的，因为它很可能更省钱。
针对这个题目而言，为了方便叙述，我们先来规定几个物理量。我们假定我们需要用实验测得的小球坠毁的最低楼层数为W，对于给定小球数N的情况下，我们为了测出W而作出的实验设计方案称为p。如果我们把某个小球设计掷下的楼层数排列成数列，并表示为一维向量的话，则p最终可以表达为一个N阶张量a_j~i1i2i3……iN，其中_j表示下标，~i1i2i3……iN表示上标。而且张组成量中的所有标量元素与W的定义域构成一一映射的关系。而对于确定的N，其所有可能的方案{p}构成一个张量空间P。
我们假定当W＝w0时，在小球数N和方案p下，测出W所需的实验次数为X(w0)。设a_j0~i01i02i04……i0N=w0，则X(w0)＝sum_k(i0k)+j0。
所谓极值最优，也即考虑在定义域[w1,w2]内，在张量空间P内寻找一个方案p，使得 Xmax＝max{X(W)|w1<=W<=w2}最小。
但是，如果我们假定W在[w1,w2]上有一个预期的分布f(w)，从而导致X也存在一个预期的分布g(x)，那么就存在一个预期次数EX＝sum_x(x*g(x))=sum_w(X(w)*f(w))。
所谓预期最优，也即考虑在定义域[w1,w2]内，在给定预期分布f(w)的情况下，在张量空间P内寻找一个方案p，使得 EX＝sum_w(X(w)*f(w))最小。
举个具体的例子，在定义域[1,100]内，在N＝1时，张量空间只有唯一的元素p，在该方案p下，{a_100~1}={1,2,3,……,99,100}。方案p的其最大测验次数Xmax＝X(100)=100。其预期测验次数依赖于w可能的概率分布状况。在w按均匀分布的情况下，方案的预期测验次数EX＝50.5。
最后，我们对这个题目作一个微小的改动，大家再来看看这个题目该怎么做。
你有两个玻璃球和一幢一百层大楼。你想测出最低在哪一层丢下会把玻璃球摔碎。假定这个待测的层数为w。我们设想w存在某个可能的概率分布f(w)。假定f(w)分别满足以下两种可能分布：
（1）均匀分布，即小球最低从任何一层坠下会摔碎的可能性相同。
（2）高斯分布，即小球最有可能最低从某一层坠下摔碎。假定这个最可能的楼层是第50层，并且在正负10层的误差范围内达到置信概率95％。
用什么战术可以确保得到结果，并且使预期的测量次数最少？如果用计算机搜索，请给出搜索算法。
[ 本帖最后由 whws 于 2007-1-15 16:03 编辑 ]
作者:
岱瀛 时间: 2007-1-15 22:51
周大神算，果然如姑姑如言，周大最会算来算去了.
(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 编辑 ]
作者:
KYOKO 时间: 2007-1-16 02:11
数学家就是这样,非得一个水龙头放水,澡盆底一个洞漏水,然后算多少时候澡盆能满.其实你堵上那个洞不就得了?
如果玻璃球换成伽利略的铁球...
作者:
reynolds_wwy 时间: 2007-1-16 09:00 标题: 回复 #13 KYOKO 的帖子
别把小学算术应用题和数学扯在一起好不好-_-b
作者:
whws 时间: 2007-1-17 16:50
原帖由
岱瀛 于 2007-1-15 22:51 发表
周大神算，果然如姑姑如言，周大最会算来算去了.
(P.S:这在古代称为术数，所以早在慕容家的天下各路高手分析中早已注明周大擅奇门遁甲之术.
)
-------------------------------------------------- ...
你的解释中的第一部分非常精彩，帮我弄清楚了许多我原先并没有真正明白的部分。谢谢你。
你解释中的第二部分显然是不正确的。我们来具体算一算结果就知道了。以题设给出的正态分布条件为例。各楼层概率分布的计算及其结果列表附在后面，以免影响大家阅读。
给出以下两个方案p1，p2：
p1:第一个小球预计投下的楼层数为[14,27,39,50,60,69,77,84,90,95,99]
第二个小球预计投下的楼层数为[1:13]
[15:26]
……（后面省略）
这就是reynolds_wwy给出的方案。
p2:第一个小球预计投下的楼层数为[27 39 45 50 54 60 69 77 90]
第二个小球预计投下的楼层数为[1:26]
[28:38]
……（后面省略）
方案p1、p2显然都能保证得到结果。但是其效率是不同的。
在极值最优的条件下，显然p1更为合理：p1的最大投掷次数为：Xmax＝14；而p2的最大投掷次数为：Xmax＝27。
但是在期望最优的条件下，却是p2更为合理：p1在正态分布下的预期投掷次数为平均9.3625次。p2在正态分布下的预期投掷次数为平均6.5797次。
实际上，在题设给出的正态分布条件下，方案p2更有可能用最少的实验次数得到结果。当然万一出现最差情况，p2也能保证得到结果，只是耗费的次数比p1多得多，但这种概率很小。说明一下，p2并不一定是该概率分布下期望值最优的方案。它只是对p1的一个简单修正。
期望投掷次数的计算公式为：EX＝sum_w(X(w)*f(w))，可以参见我上一次的回复帖。
在非均匀概率分布的情况下，为什么会出现这种情况？打个简单的比方吧：如果一块地板下面有一个鼠洞，你要通过打洞的办法找到它。在什么都不知道的情况下，也即按均匀概率分布进行估计的情况下，你只能平均每隔一段距离打一个洞。但是如果你知道鼠洞的大概位置，你必然会在鼠洞可能存在的地方多打几个洞，而在其它地方少打一些。
事实上，无论在什么概率分布下，当我们只剩下一个球的时候，我们都不可避免地要在上一个球最后划定的区间内一层接一层地试下去。但是如果某个区间所包涵概率可能性小一些，我们不妨把这个区间所包涵的楼层数划的多一些，从而使其它区间所包涵的楼层数少一些。因为结果落在这个区间的可能性很小。一旦我们不需要测量这个区间，而只需测量其它区间，那么我们可以大大节省我们必须测试的楼层数。当然，结果落在这个小概率的区间的可能性不是没有，万一是这样，只能说我们赌博失败，于是我们不得不一层一层地测量许多层，从而多耗费更多的时间。不过这样的可能性很小。最终，我们可以求得一个期望下的平均值来作为我们决定策略的依据。
事实上，大多数工程，不会以极值作为优化策略的依据，而只会把极值作为一个给定的限制条件，只要在极端条件下不超出工程所能承受的能力，我们还是会以期望最优来建立我们的策略。于是上面那个题目还可以进一步限制为：在最坏条件下测量次数不能超过20次，请给出期望最优的方案设计。
附：题目给定的高斯分布下，各个楼层的概率值列表及其计算方法。
简单计算可知，正态分布函数的参数为：均值mu＝50；均方差sigma＝10/Fai(0.475)＝10/1.96＝5.1020。查表很麻烦，可以用matlab的normcdf函数来计算。为了离散化，我们把第n层的概率表达为[n－0.5，n+0.5]的积分，第一层和第一百层的概率表达为(-inf,0.5]和[99.5,+inf)的积分。利用高斯分布的对称性可以得到各层的概率值。下面是经计算得到的各层概率列表：
9.9068e-022 5.4009e-021 3.3308e-020 1.9769e-019 1.1293e-018 6.2081e-018 3.2846e-017
1.6726e-016 8.1966e-016 3.8659e-015 1.7548e-014 7.6662e-014 3.2232e-013 1.3043e-012
5.0793e-012 1.9037e-011 6.8672e-011 2.3840e-010 7.9655e-010 2.5614e-009 7.9271e-009
2.3611e-008 6.7683e-008 1.8673e-007 4.9580e-007 1.2670e-006 3.1161e-006 7.3758e-006
1.6803e-005 3.6840e-005 7.7736e-005 1.5787e-004 3.0856e-004 5.8042e-004 1.0508e-003
1.8309e-003 3.0703e-003 4.9553e-003 7.6970e-003 1.1506e-002 1.6555e-002 2.2924e-002
3.0551e-002 3.9185e-002 4.8372e-002 5.7468e-002 6.5710e-002 7.2312e-002 7.6587e-002
7.8068e-002 7.6587e-002 7.2312e-002 6.5710e-002 5.7468e-002 4.8372e-002 3.9185e-002
3.0551e-002 2.2924e-002 1.6555e-002 1.1506e-002 7.6970e-003 4.9553e-003 3.0703e-003
1.8309e-003 1.0508e-003 5.8042e-004 3.0856e-004 1.5787e-004 7.7736e-005 3.6840e-005
1.6803e-005 7.3758e-006 3.1161e-006 1.2670e-006 4.9580e-007 1.8673e-007 6.7683e-008
2.3611e-008 7.9271e-009 2.5614e-009 7.9655e-010 2.3840e-010 6.8672e-011 1.9037e-011
5.0793e-012 1.3043e-012 3.2232e-013 7.6662e-014 1.7548e-014 3.8659e-015 8.1966e-016
1.6726e-016 3.2846e-017 6.2081e-018 1.1293e-018 1.9769e-019 3.3308e-020 5.4009e-021
8.4285e-022 1.4782e-022
[ 本帖最后由 whws 于 2007-1-17 16:54 编辑 ]
作者:
whws 时间: 2007-1-17 17:13
其实对于周瑜的通式，可以提出这么一个问题，在给予x（w）以特定的权函数f（w）的情况下，这个第推关系该怎样改造。
作者:
岱瀛 时间: 2007-1-18 17:18
明白了,你是要求所有可能尝试平均起来最优的,在最坏情况下可以,这个周末有空我就想下.
不过我的概率学的就是高中普通水平,有点
作者:
chrondolf 时间: 2007-2-19 00:44
原帖由 reynolds_wwy 于 2007-1-12 11:18 发表
第一个在14,27,39,50,60,69,77,74,90,95,99扔
别的和周瑜一样
这样14次就可以了
13次应该不行的吧，没仔细想过
這個也對？？ 如果從14丟下就破了， 那第二個在幾樓扔？
作者:
chrondolf 时间: 2007-2-19 00:49
你們這個題出的太牛了， 我一個老師就是專門搞這個研究的
作者:
chrondolf 时间: 2007-2-19 00:52
原帖由 chrondolf 于 2007-2-19 00:44 发表
這個也對？？ 如果從14丟下就破了， 那第二個在幾樓扔？
對不起， 剛才看錯了
作者:
KYOKO 时间: 2007-2-19 19:35
谁来解释下公主的Firenze是虾米意思?
作者:
reynolds_wwy 时间: 2007-2-19 22:22 标题: 回复 #21 KYOKO 的帖子
翡冷翠，或佛罗伦萨，更喜欢前面那个翻译
作者:
kongbu 时间: 2009-9-24 23:34
原帖由 周瑜 于 2007-1-12 13:05 发表
假设N为玻璃球个数，x为尝试次数，最高能确定的层数为F(N,x)
定义域
N>=1, x>=1
边际条件
F(1,x)=x
F(N,1)=1
递推关系
F(N,x)=F(N-1,x-1)+F(N-1,x-2)+...+F(N-1,1)+x
通项公式
if x< ...
递推公式基本明白了， 请问 通用公式 如何推导出来的？
作者:
toushion 时间: 2009-9-25 23:09
感觉这道题和“n个球中有一个坏球，用不带砝码的天平最少称几次才能称出来”有点相似
作者:
phoenixdaizy 时间: 2010-9-18 12:39
原帖由 toushion 于 2009-9-25 23:09 发表
感觉这道题和“n个球中有一个坏球，用不带砝码的天平最少称几次才能称出来”有点相似
这个感觉没有最优解法。
因为有一个不确定的因素，损失的球最少。
作者:
phoenixdaizy 时间: 2010-9-18 12:41
如果要求摔碎最少的话？？从100层开始测试就可以了~~~~最多摔碎一个。
如果追求试验次数的话，二分法应该是一个好的解决方案。
[ 本帖最后由 phoenixdaizy 于 2010-9-18 12:44 编辑 ]
作者:
phoenixdaizy 时间: 2010-9-18 12:48
最后一个球必须逐级下探测试。因此2个球还保留一个球的话应该是10X10的方案。
如果是N个球100开N次根取整就可以了。
作者:
dimeterio 时间: 2010-9-18 15:47
我认为5楼和9楼的思路正确，追求极值最小化不是目的，目的应该是追求平均值最小化。
作者:
周瑜 时间: 2010-9-19 03:07
最近，这个题目已经出现了升级版，大家来做一下。
位于甲地的经销商需要向位于乙地的客户提供某种商品，但是不知道几天能到达。
于是向客户保证，X天之内会到达。如果X天之内没有到达，会收到客户投诉；如果按时或提前到达不会收到客户反馈。
已知商品寄送时间是固定的，在1天到100天之间。通过多次向客户提供不同的预计到达时间可以确定商品寄送时间。
如果限制最多收到两次客户投诉，最坏情况下最少需要花多少天才能确定商品寄送时间。
注：确定上一批商品是否按时到达后才可以发送下一批商品。
[ 本帖最后由 周瑜 于 2010-9-24 10:02 编辑 ]
作者:
阿尔法孝直 时间: 2010-9-19 03:34
随便猜猜吧。
最坏的情况是：
先定50天，接到投诉；
再定75天，再接到投诉；
接着100、99、98、……76
一共需要27天才能确定。
作者:
墨叶 时间: 2010-9-19 07:49
有多少件商品。每次邮寄时规定的到达时间是否相同？
作者:
墨叶 时间: 2010-9-23 19:48
原帖由 周瑜 于 2010-9-19 03:07 发表
最近，这个题目已经出现了升级版，大家来做一下。
位于甲地的经销商需要向位于乙地的客户提供某种商品，但是不知道几天能到达。
于是向客户保证，X天之内会到达。如果X天之内没有到达，会收到客户投诉；如果按时或提前到达不会收到客户反馈。
已知商品寄送时间是固定的，在1天到100天之间。确定上一批商品是否按时到达后才可以发送下一批商品。
如果最多限制收到两次客户投诉，最坏情况下最少需要花多少天才能确定商品寄送时间。
以退为进。令最大寄送时间X时需要花费的总时间F（X），最大寄送时间X时第一次的保证时间为G（X），G（X）可能有2个值。
G（1）=0，F（1）=0；
G（2）=1，F（2）=1；
G（3）=2或1，F（3）=3；
当G（3）=2时，收到投诉可以确定时间为3，没有投诉则还需要F（2）。
G（4）=2，F（4）=5；
若G（4）=2，收到投诉还需要再邮寄一件商品时间为3，没有投诉则还需要F（2）。此时F（4）=2+3=5
若G（4）=3，收到投诉可以确定时间为4，没有投诉则还需要F（3）。此时F（4）=3+3=6。
G（5）=3，F（5）=7；
若G（5）=2，收到投诉，则寄送时间可能为3、4、5，还需要再邮寄两件商品时间为3+4；
没有投诉则还需要F（2）。此时F（5）=2+3+4=9。
若G（5）=3，收到投诉，则寄送时间可能为4、5，还需要再邮寄一件商品时间为4；
没有投诉则还需要F（3）。此时F（5）=3+4=7。
[ 本帖最后由 墨叶 于 2010-9-24 23:00 编辑 ]
作者:
周瑜 时间: 2010-9-24 21:58
思路基本正确，有两处笔误，接下来应该求出递推公式了。
作者:
墨叶 时间: 2010-9-24 22:59 标题: 回复 #33 周瑜 的帖子
谢谢提醒。
递推公式麻烦着。
作者:
eastbreeze 时间: 2012-9-15 18:38 标题: 相当佩服
我只说你们的数理都学得很好，对于我来说很惭愧。期待着你们将这些应用到mod游戏中，衷心支持。
作者:
李斯啊 时间: 2012-9-17 17:30 标题: 1
1
| 欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/) |
Powered by Discuz! 5.0.0 |