一尘不染

画家难题-估计

algorithm

这个问题是基于2001年的Joel
Spolsky的一个难题

一个人 “找到了一份街头画家的工作,在路中间画了虚线。” 在第一天,他完成了300码,在第二天达到了150码,在第三天则更少。老板很生气,要求解释。

__那家伙说: “我 无能为力。” “每天我都离油漆罐越来越远了!”

我的问题是,你能估计他第三天的距离吗?

链接线程中的注释中的一个确实得出了精确的解决方案,但是我的问题是关于足够精确的估计(例如10%),这很容易从一般原则中得出。


阅读 237

收藏
2020-07-28

共1个答案

一尘不染

这里有很多未知数-他的步行速度,绘画速度,刷子中的油漆能持续多久…

但是显然这里有两个过程。一个是平方的-是在油漆罐和油漆点之间来回走动。另一个是线性的-这是绘画的过程本身。

考虑到第10天甚至第100天,很明显,线性分量可以忽略不计,并且该过程几乎变为二次方-几乎所有时间都在走动。相反,在第一天的前几分钟内,它接近线性。

因此我们可以说,时间 t 作为距离 s 的函数,遵循幂定律 t〜s ^ a ,其变化系数 a = 1.0 … 2.0
。这也意味着 s〜t ^ b,b = 1 / a

应用[

增长分析](http://en.wikipedia.org/wiki/Analysis_of_algorithms#Empirical_orders_of_growth)

经验顺序

第1天和第2天之间的 b 系数近似为

b(1,2) = log (450/300) / log 2 = 0.585        a(1,2) = 1/0.585 = 1.71

正如预期的那样,该系数低于2。对于介于第2天和第3天之间的时间段,我们可以将其大约设置为介于 1.712.0 之间的中间值,

a(2,3) = 1.85        b(2,3) = 0.54          450*(3/2)**0.54 = 560 yards

因此,第三天的距离可以估计为560 - 450 = 110码。

如果 a 系数已经具有最大可能值 2.0 怎么办(这是不可能的)?然后,450*(3/2)**0.5 = 551码。而对于另一个极端,如果是相同的 1.71 (这显然是不可能的,要么), 450*(3/2)**0.585 = 570

这意味着110码的估计值是合理的,任一侧的误差均小于10码。

2020-07-28